文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >数据结构排序算法详解（2）——选择排序（附动图）

数据结构排序算法详解（2）——选择排序（附动图）

作者头像
用户11983512
发布于 2026-01-09 14:52:57
发布于 2026-01-09 14:52:57
690
举报
文章被收录于专栏：用户11983512的专栏用户11983512的专栏

前言

嗨٩(๑❛ᴗ❛๑)۶，今天我们继续来了解排序，本篇来讲几种选择排序——直接选择排序和堆排序，让我们来了解他们吧！

四、选择排序

1、直接选择排序

（1）概念及实现

概念： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 我们可以通过这个图来更加清晰了解过程 

请添加图片描述
请添加图片描述

这样效率太低了，我们来稍微改变一下，同时找最小和最大的，最小和前面交换，最大与后面交换 我们这里先写一个交换函数

代码语言：javascript
复制
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

再实现功能

代码语言：javascript
复制
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;

    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }

            if (a[i] < a[mini])
            {
                mini = i;
            }
        }

        Swap(&a[begin], &a[mini]);
        if (begin == maxi)
 			maxi = mini;
        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}

这里我们说一下下面这一段功能

代码语言：javascript
复制
if (begin == maxi)
 			maxi = mini;

防止最大值再开头，导致最小交换后，后面与最大交换，实际不是最大 测试：

代码语言：javascript
复制
int main()
{
    int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
    SelectSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
   /* TestOP();*/
    return 0;
}

功能正常实现

在这里插入图片描述
在这里插入图片描述
（2）时间复杂度

这个一看就看出来了，遍历n/2次 优化版直接选择排序（同时找最大和最小值）的总比较次数为 ( n + (n-2) + (n-4) + ……)，近似为n2/2，仍属于 O(n2)量级。

（3）特性

1、直接选择排序思考虽然非常好理解，但是因为效率不是很好。实际中我们很少去使用； 2、时间复杂度：O(N ^ 2)； 3、空间复杂度：O(1)。

2、堆排序

（1）概念及实现

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。 需要注意的是排升序要建大堆，排降序建小堆。 我们前面专门讲过，这里就不过多讲解了 传送门《数据结构二叉树之堆 —— 优先队列与排序的高效实现（2）》<-这一篇下面有

在这里插入图片描述
在这里插入图片描述

我们这里直接实现 先实现向下调整建堆，在实现堆排序

代码语言：javascript
复制
//向下调整建堆
void AdjustDown(int* a, int n, int parent)
{
    // 先假设左孩子小
    int child = parent * 2 + 1;

    while (child < n)  // child >= n说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }

        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//堆排序
void HeapSort(int* a, int n)
{
    // 向下调整建堆 O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}

测试 test.c

代码语言：javascript
复制
int main()
{
    int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
    HeapSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
   /* TestOP();*/
    return 0;
}

正确实现

在这里插入图片描述
在这里插入图片描述
（2）时间复杂度

O（n*logn） 《数据结构二叉树之堆 —— 优先队列与排序的高效实现（2）》 这一篇已经讲的很详细啦，这里就不做解释啦

（3）特性
  1. 时间复杂度稳定
O(n \log n)

，空间复杂度

O(1)

；

  1. 适合大规模数据排序，但小规模场景下缓存效率较低。
  2. 堆排序可用于Top-K问题（如找最大的k个元素），无需完全排序，效率更高，时间复杂度为
O(n + k \log n)

。

  1. 排升序要建大堆，排降序建小堆

3、对比插入排序和选择排序

我们这次对比插入排序和选择排序的所有排序 先来10万个数 test.c

代码语言：javascript
复制
#include"Sort.h"
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);/*
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);*/

	for (int i = 0; i < N; ++i)
	{
		// Öظ´²»¶à
		a1[i] = rand() + i;
		// Öظ´½Ï¶à
		//a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		/*a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];*/
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	//PrintArray(a2, N);

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	//QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	//BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	/*printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);*/

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	/*free(a5);
	free(a6);
	free(a7);*/
}
int main()
{
    /*int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
    HeapSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));*/
    TestOP();
    return 0;
}

结果，我们可以看出希尔排序和堆排序都挺快的，插入有点慢，直接选择排序太慢了

在这里插入图片描述
在这里插入图片描述

4、总代码

Sort.h

代码语言：javascript
复制
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
//直接插入排序
void InsertSort(int* a, int n);
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n);
//打印
void PrintArray(int* a, int n);
//交换
void Swap(int* p1, int* p2);
//直接选择排序
void SelectSort(int* a, int n);
//堆排序
void HeapSort(int* a, int n);
//向下调整建堆
void AdjustDown(int* a, int n, int parent);

Sort.c

代码语言：javascript
复制
#include"Sort.h"
//直接插入排序
void InsertSort(int* a, int n)
{
    //  [0, n-1]
    for (int i = 0; i < n - 1; i++)
    {
        // [0, n-2]是最后一组
        // [0,end]有序 end+1位置的值插入[0,end]，保持有序
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            //升序大于>,降序小于
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        // +1保证最后一个gap一定是1
        // gap > 1时是预排序
        // gap == 1时是插入排序
        gap = gap / 3 + 1;

        for (size_t i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
//打印
void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;

    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] > a[maxi])
            {
                maxi = i;
            }

            if (a[i] < a[mini])
            {
                mini = i;
            }
        }

        Swap(&a[begin], &a[mini]);
        if (begin == maxi)
            maxi = mini;
        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}
//向下调整建堆
void AdjustDown(int* a, int n, int parent)
{
    // 先假设左孩子小
    int child = parent * 2 + 1;

    while (child < n)  // child >= n说明孩子不存在，调整到叶子了
    {
        // 找出小的那个孩子
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;
        }

        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
//堆排序
void HeapSort(int* a, int n)
{
    // 向下调整建堆 O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        --end;
    }
}

test.c

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);/*
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);*/

	for (int i = 0; i < N; ++i)
	{
		// Öظ´²»¶à
		a1[i] = rand() + i;
		// Öظ´½Ï¶à
		//a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		/*a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];*/
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	//PrintArray(a2, N);

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	//QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	//MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	//BubbleSort(a7, N);
	int end7 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	/*printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%d\n", end7 - begin7);*/

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	/*free(a5);
	free(a6);
	free(a7);*/
}
int main()
{
    /*int arr[] = { 2,5,3,76,9,10,32,11,2 };
    PrintArray(arr, sizeof(arr) / sizeof(int));
    HeapSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));*/
    TestOP();
    return 0;
}

结束语

嗨ヾ(◍°∇°◍)ﾉﾞ！本篇到这里就结束啦！本篇对选择排序进行实现，并对比选择排序和插入排序的性能，下一篇我们将要接触——交换排序，下一篇将要花大量篇幅讲其中的快排，敬请期待吧！（我也挺期待的(◕ᴗ◕✿)）让我们下一篇再见吧！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-25，如有侵权请联系 cloudcommunity@tencent.com 删除
数据结构
int
sizeof
排序
排序算法

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据结构
int
sizeof
排序
排序算法
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 前言
  • 四、选择排序
    • 1、直接选择排序
      • （1）概念及实现
      • （2）时间复杂度
      • （3）特性
    • 2、堆排序
      • （1）概念及实现
      • （2）时间复杂度
      • （3）特性
    • 3、对比插入排序和选择排序
    • 4、总代码
  • 结束语
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论