文章目录
一、排序的概念及应用
💦 排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排
序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
💦 排序的运用
❗ 现实中排序的运用非常广泛，无处不在 ❕
好一个凡尔赛
💦 常见的排序算法
二、常见排序算法的实现
// 排序实现的接口 // 插入排序 void InsertSort(int* a, int n); // 希尔排序 void ShellSort(int* a, int n); // 选择排序 void SelectSort(int* a, int n); // 堆排序 void AdjustDwon(int* a, int n, int root); void HeapSort(int* a, int n); // 冒泡排序 void BubbleSort(int* a, int n) // 快速排序递归实现 // 快速排序hoare版本 int PartSort1(int* a, int left, int right); // 快速排序挖坑法 int PartSort2(int* a, int left, int right); // 快速排序前后指针法 int PartSort3(int* a, int left, int right); void QuickSort(int* a, int left, int right); // 快速排序 非递归实现 void QuickSortNonR(int* a, int left, int right) // 归并排序递归实现 void MergeSort(int* a, int n) // 归并排序非递归实现 void MergeSortNonR(int* a, int n) // 计数排序 void CountSort(int* a, int n); }
💦 插入排序
1、直接插入排序
🔑 核心思想 🔑
把待排序的记录按关键码的大小逐个插入到一个已经排好的序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
实际中我们玩扑克牌时，就用了插入排序的思想
❗ 过程：❕
当插入第 i(i>=1) 个元素时，前面的 array[0]， array[1]， … ， array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1]， array[i-2]，… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移
❗ 直接插入排序的特性总结：❕
1️⃣ 元素集合越接近有序，直接插入排序算法的时间效率越高
2️⃣ 时间复杂度：O(N^2)
3️⃣ 空间复杂度：O(1)，它是一种稳定的排序算法
4️⃣ 稳定性：稳定
❗ 动图演示：❕
🧿 实现代码 ：
void InserSort(int* a, int n) { //多趟控制 int i = 0; for (i = 0; i < n - 1; i++) { //单趟控制 int end = i ; int temp = a[end + 1]; while (end >= 0) { //目标数小于其它数时，其它数就往后挪；大于则插入 if (temp < a[end]) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = temp; } }
❓ 插入排序的时间复杂度 ❔
最坏的情况 - 逆序：O(N2)
最好的情况 - 接近有序 ：O(N)
2、希尔排序
希尔排序 (缩小增量排序)
🔑 核心思想 🔑
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成若干个组，所有距离为 gap 的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工## 标题作。当到达 = 1 时，所有记录在统一组内排好序。
人话就是：
1️⃣ 预排序 (接近升序) - gap > 1
2️⃣ 直接插入排序 - gap == 1
❗ 希尔排序特性总结 ❕
1️⃣ 希尔排序是对直接插入排序的优化
2️⃣ 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，其实就是直接插入排序，且数组已经接近有序的了。整体而言，可以达到优化的效果，我们实现后可以进行性能测试的对比
3️⃣ 希尔排序的时间复杂度并不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些数中给出的希尔排序的时间复杂度都不固定，官方给出的时间复杂度是 O(N1.3)
4️⃣ 稳定性：不稳定
👁🗨 知识扩展
🧿 实现代码 ：
代码的核心并不是一组一组的排，而是多组并排
以下只是预排序代码，还需要再调用 InsertSort 进行直接插入排序
void ShellSort(int* a, int n) { int i = 0; int gap = 3; //多组并排 for (i = 0; i < n - gap; i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (temp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = temp; } }
❓ 对于 gap 的值写成固定的并不好 ❔
这里只是建议
void ShellSortPro(int* a, int n) { //gap > 1 预排序 //gap == 1 直接插入排序 int i = 0; //gap的初始值为n int gap = n; while (gap > 1) { //每次循环gap都在减少，直到gap变成1 gap = gap / 3 + 1; //gap /= 2; for (i = 0; i < n - gap; i++) { int end = i; int temp = a[end + gap]; while (end >= 0) { if (temp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = temp; } } }
💦 选择排序
1、直接选择排序
🔑 核心思想 🔑
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
❗ 过程：❕
1️⃣ 在元素集合 array[i] - array[n-1] 中选择关键码最大 (小) 的数据元素
2️⃣ 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3️⃣ 在剩余的 array[i] - array[n-2] (array[i+1]–array[n-1]) 集合中，重复上述步骤，直到集合剩余 1 个元素
❗ 直接选择排序的特性总结：❕
1️⃣ 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2️⃣ 时间复杂度：O(N^2) - 最好 / 最坏
3️⃣ 空间复杂度：O(1)
4️⃣ 稳定性：不稳定
❗ 动图演示：❕
🧿 实现代码 ：
void Swap(int* px, int* py) { int temp = *px; *px = *py; *py = temp; } void SelectSort(int* a, int n) { int i = 0; int begin = 0; while (begin < n) { int mini = begin; //选最小 for (i = begin; i < n; i++) { if (a[i] < a[mini]) { mini = i; } } //交换 Swap(&a[begin], &a[mini]); //迭代 begin++; } }
🧿 实现 SelectSort 的优化代码 ：
遍厉一遍选出最小的和最大的，然后把最小的放在左边，最大的放在右边
void Swap(int* px, int* py) { int temp = *px; *px = *py; *py = temp; } void SelectSortPro(int* a, int n) { int i = 0; int begin = 0, end = n - 1; while (begin < end) { //选最大和最小 int mini = begin, maxi = begin; for (i = begin; i <= end; i++) { if (a[i] > a[maxi]) { maxi = i; } if (a[i] < a[mini]) { mini = i; } } //交换 Swap(&a[begin], &a[mini]); //当a数组里第1个元素是最大值时，此时经过上面的Swap，最大值的位置已经更改了，所以需要修正最大值的位置，让下一个Swap正确交换 if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); //迭代 ++begin; --end; } }
2、堆排序
🔑 核心思想 🔑
堆排序 (Heapsort) 是指利用堆积树 (堆) 这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
关于堆排序详解请转到 ➡ 仅不到五万字轻松了解二叉树和堆
❗ 堆排序的特性总结：❕
1️⃣ 堆排序使用堆来选数，效率就高了很多。
2️⃣ 时间复杂度：O(N*logN)
3️⃣ 空间复杂度：O(1)
4️⃣ 稳定性：不稳定
❗ 动图演示：❕
🧿 实现代码 ：
void Swap(int* px, int* py) { int temp = *px; *px = *py; *py = temp; } void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (a[child] < a[child + 1] && child + 1 < n) { 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) { //建大堆 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } int end = n - 1; //交换并调整 while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } }
💦 交换排序
1、冒泡排序
🔑 核心思想 🔑
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
❗ 冒泡排序的特性总结：❕
1️⃣ 冒泡排序是一种非常容易理解的排序
2️⃣ 时间复杂度：O(N^2)
3️⃣ 空间复杂度：O(1)
4️⃣ 稳定性：稳定
❗ 动图演示：❕
🧿 实现代码 ：
void Swap(int* px, int* py) { int temp = *px; *px = *py; *py = temp; } void BubbleSort(int* a, int n) { int i = 0; int j = 0; for (i = 0; i < n - 1; i++) { for (j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); } } } }
🧿 实现代码 BubbleSort 的优化版本 ：
当遍厉一遍后发现没有 Swap 时，那么说数组就是有序的
时间复杂度：最坏 O(N2)
最好 O(N)
void Swap(int* px, int* py) { int temp = *px; *px = *py; *py = temp; } void BubbleSortPro(int* a, int n) { int i = 0; int j = 0; for (i = 0; i < n - 1; i++) { int flag = 1; for (j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { flag = 0; Swap(&a[j], &a[j + 1]); } } //如果flag等于1说明此时数组是升序 if (flag == 1) break; } }
2、快速排序
🔑 核心思想 🔑
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
❗ 过程：❕
1️⃣ 选出一个关键字 key，一般是头或者尾
2️⃣ 经过一次单趟后，key 放到了正确的位置，key 左边的值比 key 小，key 右边的值比 key 大
3️⃣ 再让 key 的左边区间有序、key 的右边区间有序
❗ 动图演示：❕
一、首次单趟 (注意这三种方法首次单趟后不一定相同)
💨 hoare 版本
❓ 如何保证相遇位置的值小于 key ❔
💨 挖坑版本
💨 前后指针法
二、非首次单趟
🧿 实现代码 ：首次 + 非首次 + 递归版本
void Swap(int* px, int* py) { int temp = *px; *px = *py; *py = temp; } void PartSortHoare(int* a, int left, int right) { int keyi = left; while(left < right) { //左边作key，右边先走找小 while(a[right] >= a[keyi] && left < right) { right--; } //右边找到小，再找左边的大 while(a[left] <= a[keyi] && left < right) { left++; } //交换小大 Swap(&a[right], &a[left]); } //交换key Swap(&a[keyi], &a[right]); //返回分割大小的那个下标 return left; } int PartSortHole(int* a, int left, int right) { int key = a[left]; int hole = left; while (left < right) { //右边找小，填左坑 while (left < right && a[right] >= key) { right--; } a[hole] = a[right];//填坑 hole = right;//新的坑 //左边找大，填右坑 while (left < right && a[left] <= key) { left++; } a[hole] = a[left];//填坑 hole = left;//新的坑 } //将key填最后一个坑 a[hole] = key; return hole; } int PartSortPoint(int* a, int left, int right) { int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { //cur比keyi大时，prev不会++；且排除了自己交换自己 if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } //两种情况cur都要++ cur++; } //交换keyi Swap(&a[keyi], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { //递归的结束条件 if (left >= right) { return ; } //keyi拿到分割大小的下标 - [left, keyi - 1]; [keyi]; [keyi + 1, right] //int keyi = PartSortHoare(a, left, right);//版本1 //int keyi = PartSortHole(a, left, right);//版本2 int keyi = PartSortPoint(a, left, right);//版本3 //递归左 QuickSort(a, left, keyi - 1); //递归右 QuickSort(a, keyi + 1, right); }
❓ QuickSort 的时间复杂度 ❔
🧿 实现 QuickSort 的优化代码 —— 优化有序的情况
三数取中选 key —— left、mid、right 中不是最大也不是最小的数
//三数取中 int GetMidIndex(int* a, int left, int right) { //int mid = (left + right) / 2; int mid = left + (right - left) / 2;//防止溢出版本 if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] < a[right]) { return right; } else { return left; } } else //a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if(a[left] < a[right]) { return left; } else { return right; } } } int PartSortHoarePro(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; while (left < right) { while (a[right] >= a[keyi] && left < right) { right--; } while (a[left] <= a[keyi] && left < right) { left++; } Swap(&a[right], &a[left]); } Swap(&a[keyi], &a[right]); return left; } int PartSortHolePro(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int key = a[left]; int hole = left; while (left < right) { //右边找小，填左坑 while (left < right && a[right] >= key) { right--; } a[hole] = a[right];//填坑 hole = right;//新的坑 //左边找大，填右坑 while (left < right && a[left] <= key) { left++; } a[hole] = a[left];//填坑 hole = left;//新的坑 } //将key填最后一个坑 a[hole] = key; return hole; } int PartSortPointPro(int* a, int left, int right) { int midi = GetMidIndex(a, left, right); Swap(&a[left], &a[midi]); int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { //cur比keyi大时，prev不会++；且排除了自己交换自己 if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } //两种情况cur都要++ cur++; } //交换keyi Swap(&a[keyi], &a[prev]); return prev; } void QuickSortPro(int* a, int left, int right) { if (left >= right) { return; } //int keyi = PartSortHoarePro(a, left, right);//版本1 //int keyi = PartSortHolePro(a, left, right);//版本2 int keyi = PartSortPointPro(a, left, right);//版本3 QuickSortPro(a, left, keyi - 1); QuickSortPro(a, keyi + 1, right); }
❓ QuickSortHoarePro 的时间复杂度 ❔
这里就不会出现最坏的情况 —— 有序，因为有了三数取中算法。
🧿 实现代码 ：首次 + 非首次 + 非递归版本
任何一个递归代码，要改成非递归
1、循环
2、栈 (数据结构) 模拟
显然这里的快排不好直接改成循环，还要借助栈，所以这里复用了之前 C 实现的栈，详解请转 ➡ 爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏
🔑 核心思想 🔑
void QuickSortNonR(int* a, int left, int right) { ST st; StackInit(&st); //先入第一组区间 StackPush(&st, right); StackPush(&st, left); //栈不为空 while (!StackEmpty(&st)) { //取栈顶left，并Pop int begin = StackTop(&st); StackPop(&st); //再取栈顶right，并Pop int end = StackTop(&st); StackPop(&st); //这里就用前后指针版本进行单趟排 int keyi = PartSortPointPro(a, begin, end); //再入区间 [left, keyi - 1]; [keyi]; [keyi + 1, end] //右区间 —— 只有1个值不会入 if (keyi + 1 < end) { StackPush(&st, end); StackPush(&st, keyi + 1); } //左区间 —— 只有1个值不会入 if (begin < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, begin); } } StackDestory(&st); }
❗ 快速排序的特性总结：❕
1️⃣ 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2️⃣ 时间复杂度：O(N*logN)
3️⃣ 空间复杂度：O(logN)
4️⃣ 稳定性：不稳定
