前言
🎄在生活中我们必不可少的就是对一组数据进行排序，所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。在处理数据时，我们时常也要对数据进行排序，根据不同的情境使用不同的排序可以达到事半功倍的效果，因此掌握多种排序的算法十分重要，今天就一起来学习一下几个常见的排序方法吧。
插入排序
🎄就像我们在打扑克时候的整牌，我们先固定开始一部分的牌，让他们处于有序的状态，之后再根据大小把后面的排插入的前面的牌里面。这也正是插入排序的基本原理。
🎄 因此，我们需要遍历数组，最开始有序的数列只有一个便默认为有序，之后遇到一个新的数就拿那个新的数跟前面的数比，找到这个数在这个数列里对应的位置插入后，这个数列再次变成了一个新的有序数列。
void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) //从第一个开始往后选择到i一定是有序的 { int end = i; int tmp = a[i + 1]; while (end >= 0) //向前插入 { if (a[end] > tmp) //升序的排法 { a[end + 1] = a[end]; //数据往后挪 end--; } else { break; //不再小于就找到了自己的位置，跳出循环 } } a[end + 1] = tmp; //将数据插入目标位置 } }
希尔排序
🎄希尔排序法又称缩小增量法，是由插入排序发展而来的，当数组里的元素足够大时，插入排序便不占优势，若我们在直接插入排序之前就先对数组进行预处理的话，就可以很大程度上提高性能与效率。
🎄基本思想是：先选定一个整数，把待排序文件中所有记录分成有限个组，所有距离相同的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
// 希尔排序 void ShellSort(int* a, int n) { int gap = n; while (gap > 1) //一组里有gap个元素 { gap = gap / 3 + 1; //每次缩小每组元素的数量，当gap为1时就是插入排序 for (int 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 SelectSort(int* a, int n) { //双指针的思想 int begin = 0; int end = n - 1; while (begin < end) { int max = begin; //找区间内最大最小值 int min = end; for (int i = begin; i <= end; i++) { if (a[i] > a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } swap(&a[begin], &a[min]); //小的放前面 swap(&a[end], &a[max]); //大的放后面 begin++; //缩进区间 end--; } }
堆排序
🎄之前在将堆的实现的时候就讲了堆排序，但堆排序的实现并不需要创建一个堆，只是使用了堆的思想。构建一个大堆之后，堆顶的数据就是数组的最大值，将其放在最后一位，之后再次构建大堆，则第二次堆顶的数据就是数组第二大的值，由此循环便完成排序。
void adjustdown(heaptype* a, int n, int root) //n是数组的大小 { int parent = root; //找到向下调整的初始值 int child = parent * 2 + 1; //往下找其左孩子 while (parent < n) { if (child + 1 < n && a[child] > a[child + 1]) //找孩子里最小的那个 { child++; } if (child < n && a[parent] > a[child]) //父结点大于子结点就交换 { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; //找该结点对应的子结点 } else { break; //小于则停止调整 } } } void HeapSort(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) //从最后一个结点对应的父结点开始建堆 { AdjustDwon(a, n, i); //先构建一个大堆 } int end = n - 1; while (end > 0) { swap(&a[0], &a[end]); //最大的放在最后面 AdjustDwon(a, end, 0); //再次向下调整 end--; //缩进 } }
冒泡排序
🎄冒泡排序可以说是我们接触最早的排序，就像冒泡一样一点一点把数往后推。
// 冒泡排序 void BubbleSort(int* a, int n) { for (int i = 0; i < n-1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } } }
快速排序
hoare版本
🎄这是最早的快速排序算法，基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
🎄说人话就是刚开始以数组里的一个值定义一个 key ，让左右两个指针向中间逼近，右边的指针找比 key 小的，左边的指针就找比 key 大的，二者交换，最后左右指针相遇的位置，就是 key 这个值在数组里面所占的位置。之后根据递归使得每个数都找到他对应的位置。
// 快速排序hoare版本 int PartSort1(int* a, int left, int right) { if (left > right) //区间大小小于等于1结束递归 { return 0; } int l = left; int r = right; int key = left; while (l < r) { while (l < r && a[r] >= a[key]) //右边找比key小的 { r--; } while (l < r && a[l] <= a[key]) //左边找比key大的 { l++; } swap(&a[l], &a[r]); //二者交换 } swap(&a[key], &a[r]); //把key放到左右指针相遇的位置 key = l; PartSort1(a, left, key-1); //左区间排序 PartSort1(a, key+1, right); //右区间排序 }
挖坑法
🎄挖坑法可能跟 hoare 的方法有些不同但万变不离其宗。都是在左边找比 key 小的数，右边找比 key 大的数。只不过这里的坑位是时刻都在变化，而不是左右都找到了才进行交换。
//挖坑法 int PartSort2(int* a, int begin, int end) { if (begin > end) //递归结束的条件 { return 0; } int left = begin; int right = end; int key = a[begin]; int hole = begin; while (left < right) { while (left < right && a[right] >= key) { right--; } swap(&a[right], &a[hole]); //右边找到比key小的就放到坑里 hole = right; //当前位置变成坑 while (left < right && a[left] <= key) { left++; } swap(&a[left], &a[hole]); //左边找到比key大的就放到坑里 hole = left; //当前位置变成坑 } a[hole] = key; //key就放到最后的坑的位置 PartSort2(a, begin, hole - 1); //左区间递归 PartSort2(a, hole + 1, end); //右区间递归 }
前后指针版本
🎄用一前一后的指针来遍历数组，元素大于等于 key 时不做处理，元素小于 key 时便换到 prev 的下一位。由此规律可以得知， prev 之前的元素都应该是小于等于 key 的。最后将 prev 和 key 所指向的值交换，便实现一次递归。
//双指针法 int PartSort3(int* a, int begin, int end) { if (begin > end) { return 0; } int cur = begin+1; int prev = begin; int key = begin; while (cur <= end ) { if (a[cur] >= a[key]) //大于等于key时不做处理 cur++; else //元素小于key时便换到prev的下一位 { prev++; swap(&a[cur], &a[prev]); cur++; } } swap(&a[prev], &a[key]); PartSort3(a, begin, prev - 1); PartSort3(a, prev + 1, end); }
🎄更加简便的话可以这样写。
int PartSort3(int* a, int begin, int end) { if (begin > end) { return 0; } int cur = begin+1; int prev = begin; int key = begin; while (cur <= end) { if (a[cur] < a[key] && ++prev != cur) //根据&&的性质只有前面部分为真才会判断后面部分，因此满足条件prev才会++ { swap(&a[cur], &a[prev]); } cur++; } swap(&a[prev], &a[key]); PartSort3(a, begin, prev - 1); PartSort3(a, prev + 1, end); }
优化
🎄若在上面算法的基础上再加上三数取中，或当递归到小的子区间时，使用插入排序，还可以进一步提升快排的性能。这里就展示一下三数取中。
🎄由于 key 的值只要越靠近这个数组的中间值，那一次递归可以靠近自己对应位置的元素的数量就可以有效地提高。因此每次都在第一个数、正中间的数以及最后一个数之中找到中间值作为 key 运行。
// 三数取中 int getmid(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] < a[mid]) //在第一个数、正中间还有最后一个数之中选择最中间的那个数作为key { if (a[mid] < a[end]) { return mid; } else { if (a[end] > a[begin]) { return end; } else { return begin; } } } else { if (a[mid] > a[end]) { return mid; } else { if (a[begin] > a[end]) { return end; } else { return begin; } } } } int PartSort1(int* a, int left, int right) { if (left > right) //区间大小小于等于1结束递归 { return 0; } int l = left; int r = right; int ret = getmid(a, left, right); swap(&a[ret], &a[left]); int key = left; while (l < r) { while (l < r && a[r] >= a[key]) //右边找比key小的 { r--; } while (l < r && a[l] <= a[key]) //左边找比key大的 { l++; } swap(&a[l], &a[r]); //二者交换 } swap(&a[key], &a[r]); //把key放到左右指针相遇的位置 key = l; PartSort1(a, left, key-1); //左区间排序 PartSort1(a, key+1, right); //右区间排序 }
非递归实现
🎄既要掌握递归，那么非递归实现快速排序自然也需要掌握，让我们想一想，每次递归传递的是什么？是我们要调整的区间。如果我们可以提前将我们接下来要访问的区间提前存储起来，是否就能达到我们想要的目的？之前我们讲过二叉树的层序遍历，是借助队列来辅助实现的。今天我们用栈来实现快排的非递归。
//单次循环 int PartSort(int* a, int left, int right) { if (left > right) { return 0; } int l = left; int r = right; int ret = getmid(a, left, right); swap(&a[ret], &a[left]); int key = left; while (l < r) { while (l < r && a[r] >= a[key]) { r--; } while (l < r && a[l] <= a[key]) { l++; } swap(&a[l], &a[r]); } swap(&a[key], &a[r]); return r; //返回key值 } int quicksortNorR(int* a, int begin, int end) { Stack S; Stack* P = &S; StackInit(P); //初始化栈 StackPush(P, begin); //把头尾压入栈中 StackPush(P, end); while (!StackEmpty(P)) //栈不为空则持续访问 { //确定区间 int right = StackTop(P); //后进先出，先读右边界 StackPop(P); int left = StackTop(P); //再读取左边界 StackPop(P); int key = PartSort(a, left, right); //进行快排的单次排序，返回值是单次的key值 //[left,key-1] key [key+1,right] 一次排序后区间被分成三个部分 if (key + 1 < right) //右区间至少有两个元素才将右区间压入栈中 { StackPush(P, key + 1); //先输入左边界再输入右边界 StackPush(P, right); } if (left + 1 < key ) { StackPush(P, left); StackPush(P, key - 1); } } }
归并排序
🎄在平时的做题中相信大家一定会做到这种题目：将两个有序的数组合并成一个有序的数组，我们通常都是用两个指针一个一个互相比对各各元素大小后选择插入新数组里，最后完成排序。这里用到的正是归并排序的思想。
🎄但这个算法实现的前提就是两个数组必须是有序的。我们平时拿到的数组都是无序的那该怎么排列呢？我们可以将数组里的元素不断划分成一个个小的数组，最小直到每个小数组都只有一个元素，便可认为他是有序的。之后便可两个两个进行归并。而这样涉及的元素越来越多，最后完成整个数组的归并。
void _Mergesort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } //分区间 int mid = (begin + end) / 2; //区间：[begin,mid] [mid+1,end] _Mergesort(a, begin, mid, tmp); _Mergesort(a, mid+1, end, tmp); //归并 int left1 = begin; int left2 = mid + 1; int right1 = mid; int right2 = end; int i = begin; while (left1 <= right1 && left2 <= right2) //一边走完就会结束循环 { if (a[left1] < a[left2]) { tmp[i++] = a[left1++]; } else { tmp[i++] = a[left2++]; } } while (left1 <= right1) //将剩余的数据拷贝到新数组的末尾 { tmp[i++] = a[left1++]; } while (left2 <= right2) { tmp[i++] = a[left2++]; } memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); //将归并完的数据拷贝回原来数组 } void Mergesort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc"); exit(-1); } _Mergesort(a, 0, n, tmp); free(tmp); }
非递归实现
🎄这里通过 rangeN 控制区间来代替递归的使用， rangeN 代表的是一组内数据的个数，每次归并的对象都是两组数据，因此循环每次都要加上 2 倍的 rangeN 。不仅如此最关键的在于 end1 、 begin2 和 end2 都有可能越界。因此需要对三种情况进行判断（都写在代码里了）。
void MergesortNorR(int* a, int n) { int rangeN = 1; //一组内数据的个数 int* tmp = (int*)malloc(sizeof(int) * n); while (rangeN < n) { for (int i = 0; i < n; i += 2 * rangeN) //每次跨越两组的距离 { //划分区间 int begin1 = i; int end1 = i + rangeN - 1; int begin2 = i + rangeN; int end2 = begin2 + rangeN - 1; int j = i; //确保不越界 除了begin1以外其他都有越界的可能需要判断 if (end1 >= n) //end1越界说明begin2和end2都越界 { //只有begin1到n之间是有效区间已经有序无需归并 break; } else if (begin2 >= n) //begin2越界但end1没越界 { //因此有效区间还是只有一组 break; } else if (end2 >= n) //只有end2越界说明有效区间有两组数据 { //需要进行归并，但要控制区间不超过n end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] > a[begin2]) { tmp[j++] = a[begin2++]; } else { tmp[j++] = a[begin1++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); //单次归并完拷贝回原数组 } rangeN *= 2; //调整每组元素的数量 } free(tmp); }
复杂度分析
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 | |
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | 0(1) | 稳定 | |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | |
| 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | |
| 希尔排序 | O(nlogn) ~ O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 | |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn)~ O(n) | 不稳定 | |
🎄好了，这次关于排序的讲解就到这里结束了，如果文章有帮到你还请留下你的三连，关注博主一起进步！！！
