带你学懂数据结构中的八大排序（上）

创始人

2024-05-01 14:00:21

0次

✨个人主页： Yohifo
🎉所属专栏： 数据结构 | C语言
🎊每篇一句： 图片来源

Every challenge, every adversity, contains within it the seeds of opportunity and growth.
每个挑战，每次逆境，里面都藏有机会与成长的种子。

文章目录

📘前言
📘正文
- 📖插入排序
- - 📃直接插入排序
  - 📃希尔排序
- 📖选择排序
- - 📃简单选择排序
  - 📃堆排序
- 📖排序小结
📘总结

📘前言

排序（Sort）是初阶数据结构中的最后一块内容，所谓排序，就是通过某种手段，使目标数据变为递增或递减，排序有很多种方式：插入、选择、交换、归并、映射等等，本文会介绍这些方式下的详细实现方法，因篇幅较长，故分为上下文的形式介绍，本文是上半部分。

下面是通过排序生成的排行榜

TIOBE编程语言排行榜

📘正文

📖插入排序

插入，指将数据插入到合适位置，这个分类中包含了两种排序算法：直接插入与希尔，其中希尔排序又称缩小增量排序，是一种非常快但不稳定的排序，它的时间复杂度计算极为复杂，下面详细来看看这两个排序吧

📃直接插入排序

思路：从第二个数开始，假设此数为 tmp ，逐个往前进行比对，如果前数大于 tmp ，就将前数值赋值到 tmp 处，然后继续往前比对，直到找到小于或等于 tmp 的数（或者比对至数据首）就停止，最后将 tmp 的值赋值到此处就行了

//直接插入排序
void InsertSort(int* pa, int n)
{assert(pa);//从后往前比较，找到合适位置就插入for (int i = 1; i < n; i++){int end = i;int tmp = pa[end];while (end){if (pa[end - 1] > tmp)pa[end] = pa[end - 1];elsebreak;end--;}pa[end] = tmp;}
}

动图展示

时间复杂度：

最坏：数据为一个逆序的等差数列 O(N^2)
最好：顺序有序 O(N)

空间复杂度：

仅仅只需要一个 tmp 变量 O(1)

稳定性：

稳定，当两个相同数相遇时，后者是不会跑到前者前面去的

📃希尔排序

希尔排序是在直接插入排序上进行优化的一种排序，希尔排序分为两步：

1、预排序，使得数据尽可能接近有序
2、直接插入排序，最后调用一次直接插入排序，快速的完成排序

思路：预排序是通过区间划分实现的，假设当前区间为 gap，那么 1、1+gap*n 可以分成一组，同理2、3、4 都可以分，将这些组分别进行直接插入排序（数据少，效率高）。每完成一次分组排序，gap 就会缩小，直到 gap 为1时，进行一次直接插入排序，整个希尔排序就完成了

//希尔排序
void ShellSort(int* pa, int n)
{assert(pa);//思路：在插入排序的基础上，先分为n个区间，使数组尽可能有序（预排序）int gap = n;while (gap > 1){gap = gap / 3 + 1;	//确保gap最后为1for (int i = 0; i < n - gap; i++){int end = i;int tmp = pa[end + gap];while (end >= 0){//此时的end位于tmp之前sif (pa[end] > tmp)pa[end + gap] = pa[end];elsebreak;end -= gap;}pa[end + gap] = tmp;}}
}

动图展示（图太长了，分段展示）
1、预排序

2、直接插入排序

时间复杂度：

希尔的时间复杂度计算是一个极其复杂的过程，需要用到高等数学的知识，这里直接记就行 O(N^1.3)

空间复杂度：

仅仅只需要一个 tmp 变量 O(1)

稳定性：

不稳定，当两个相同数被不同区间选中时，可能会发生交换现象，示例 1 4 2 2 3

📖选择排序

选择排序下也可以分为两种：简单选择与之前学过的堆排序，两者的本质是一样的，都是依赖于不断的比对，选到合适数后进行交换

📃简单选择排序

思路：选到最大的数，然后与 end 值交换；优化：选最大与最小，分别与 end 值和 begin 值交换

void swap(int*pnum1, int* pnum2)
{assert(pnum1 && pnum2);int tmp = *pnum1;*pnum1 = *pnum2;*pnum2 = tmp;
}//简单选择排序
void SelectSort(int* pa, int n)
{assert(pa);//思路：选最小的放前面，选最大的放后面int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;int mini = begin;for (int i = begin + 1; i <= end; i++){if (pa[i] > pa[maxi])maxi = i;if (pa[i] < pa[mini])mini = i;}swap(&pa[begin], &pa[mini]);if (maxi == begin)maxi = mini;swap(&pa[end], &pa[maxi]);begin++, end--;}
}

动图展示：

时间复杂度：

这是一个比较糟糕的排序，因为不管是什么情况都是 O(N^2)

空间复杂度：

仅借助变量辅助交换 O(1)

稳定性：

不稳定，在选择时，可能把相同数中的后者选到前面，示例 1 4 2 2 3

注意：

当交换 min 值与 begin 值后，如果 max 等于此时的 begin ，那么就要将 max 赋为 min，即 max = min

📃堆排序

思路：堆排序用到了堆的知识，如果想排升序的话建大堆，因为大堆中堆顶是最大值，将堆顶值与堆低值交换后，执行向下调整，使其再次变为大堆，就这样反复交换、调整，堆排序就完成了

void swap(int*pnum1, int* pnum2)
{assert(pnum1 && pnum2);int tmp = *pnum1;*pnum1 = *pnum2;*pnum2 = tmp;
}void AdjustDown(int* pa, int n, int parent)
{assert(pa);//大堆，找大孩子，调整int child = parent * 2 + 1;while (child < n){if (child + 1 < n && pa[child + 1] > pa[child])child++;if (pa[child] > pa[parent]){swap(&pa[child], &pa[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}//堆排序
void HeapSort(int* pa, int n)
{assert(pa);//思路：升序建大堆，将堆顶元素沉底，然后再调整int parent = (n - 1 - 1) / 2;	//找父亲for (int i = parent; i >= 0; i--)AdjustDown(pa, n, i);//将堆顶元素沉底后调整int end = n - 1;while (end > 0){swap(&pa[0], &pa[end]);AdjustDown(pa, end--, 0);}
}