快速排序
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
* 从数列中挑出一个元素，称为 “基准”（pivot）；
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
图解快排
代码实现
快速排序的时间复杂度是O(nlogn)，极端情况下会退化成O(n^2)，为了避免极端情况的发生，选取基准值我这里用了getmidindex三点中值法。
方式一:hoare版本
int getmidindex(int* a, int left, int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) return left; else return right; } else { if (a[left] < a[right]) return left; else if (a[mid] > a[right]) return mid; else return right; } } int partion(int* a, int left, int right) { int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int keyi = left; while (left < right) { while (left<right && a[right]>=a[keyi]) right--; while (left < right && a[left] <= a[keyi]) left++; swap(&a[left], &a[right]); } swap(&a[left], &a[keyi]); return left; } void quicksort(int* a, int left, int right) { if (left >= right) { return; } int keyi = partion(a, left, right); quicksort(a, left, keyi - 1); quicksort(a, keyi + 1, right); }
方式二:挖坑法
int GetMidIndex(int* a, int left, int right) { //int mid = (left + right) / 2; int mid = left + ((right - left) >> 1); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int Partion2(int* a, int left, int right) { // 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况 int mini = GetMidIndex(a, left, right); Swap(&a[mini], &a[left]); int key = a[left]; int pivot = left; while (left < right) { // 右边找小, 放到左边的坑里面 while (left < right && a[right] >= key) { --right; } a[pivot] = a[right]; pivot = right; // 左边找大，放到右边的坑里面 while (left < right && a[left] <= key) { ++left; } a[pivot] = a[left]; pivot = left; } a[pivot] = key; return pivot; }
方式三:前后指针法
int GetMidIndex(int* a, int left, int right) { //int mid = (left + right) / 2; int mid = left + ((right - left) >> 1); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int Partion3(int* a, int left, int right) { // 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况 int mini = GetMidIndex(a, left, right); Swap(&a[mini], &a[left]); int keyi = left; int prev = left; int cur = prev + 1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[prev], &a[keyi]); return prev; }
快速排序的特征总结:
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
图解堆排
代码实现
void Adjustdown(int* a,int n,int parent) { int child = parent * 2 + 1; while (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) { assert(a); for (int i = (n - 1 - 1) / 2; i >= 0; i--) { Adjustdown(a, n, i); } int end = n - 1; while (end >= 0) { swap(&a[end], &a[0]); Adjustdown(a, end, 0); end--; } }
堆排序的特征总结:
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
计数排序
由于篇幅原因我只提供最优化解法,对其不做仔细介绍,想要更深刻了解此算法请参考:一文弄懂计数排序算法！ - 程序员小川 - 博客园
算法步骤:
找出数组中的最大值max、最小值min。
创建一个新数组count，其长度是max-min加1，其元素默认值都为0。
遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
对count数组变形，新元素的值是前面元素累加之和的值，即count[i+1] = count[i+1] + count[i];。
创建结果数组result，长度和原始数组一样。
遍历原始数组中的元素，当前元素A[j]减去最小值min，作为索引，在计数数组中找到对应的元素值count[A[j]-min]，再将count[A[j]-min]的值减去1，就是A[j]在结果数组result中的位置，做完上述这些操作，count[A[j]-min]自减1。
图解计数
代码实现
int main() { int a[] = { 101,109,107,103,108,102,103,110,107,103 }; int length = sizeof(a) / sizeof(int); //找出数组中的最大值和最小值 int max = a[0]; for (int i = 0; i < length; i++) { if (a[i] > max) { max = a[i]; } } int min = a[0]; for (int i = 0; i < length; i++) { if (min > a[i]) { min = a[i]; } } //创建一个新数组count，其长度为max-min+1，其默认值为0 int* count = new int[max - min + 1]; for (int i = 0; i < max - min + 1; i++) { count[i] = 0; } //对计数数组各元素进行赋值 for (int i = 0; i < length; i++) { //A中的元素要减去最小值,再作为新索引 count[a[i]-min]++; } //count变形,新元素的值是前面元素累加之和 for (int i = 1; i < max - min + 1; i++) { count[i] += count[i - 1]; } //创建结果数组 int* result = new int[length]; //遍历a中的元素，填充到结果数组中 for (int i = 0; i < length; i++) { result[count[a[i] - min] - 1] = a[i]; count[a[i] - min]--; } for (int i = 0; i < length; i++) { cout << result[i] << " "; } return 0; }
计数排序的特性总结:
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
桶排序
参考:漫画：什么是桶排序？_CSDN 程序人生的博客-CSDN博客
一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
确定需要排序数组的最大值和最小值 - 循环len次
生成桶数组，并初始化 - 循环bucketLen次
对需要排序数组进行统计，统计结果放入相应的桶中 - 循环len次
循环输出桶，并替换原序列 - 循环bucketLen+len次
图解桶排
代码实现
/*算法：桶排序*/ void bucketSort(int arr[], int len) { // 确定最大值和最小值 int max = INT_MIN; int min = INT_MAX; for (int i = 0; i < len; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // 生成桶数组 // 设置最小的值为索引0，每个桶间隔为1 int bucketLen = max - min + 1; // 初始化桶 int bucket[bucketLen]; for (int i = 0; i < bucketLen; i++) bucket[i] = 0; // 放入桶中 int index = 0; for (int i = 0; i < len; i++) { index = arr[i] - min; bucket[index] += 1; } // 替换原序列 int start = 0; for (int i = 0; i < bucketLen; i++) { for (int j = start; j < start + bucket[i]; j++) { arr[j] = min + i; } start += bucket[i]; } }
桶排序的特性总结:
由算过程可知，桶排序的时间复杂度为O(N+N(logN-logM)) ，其中 M表示桶的个数。由于需要申请额外的空间来保存元素，并申请额外的数组来存储每个桶，所以空间复杂度为O(N+M) 。算法的稳定性取决于对桶中元素排序时选择的排序算法。由桶排序的过程可知，当待排序集合中存在元素值相差较大时，对映射规则的选择是一个挑战，可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象，对算法的时间复杂度或空间复杂度有较大影响，所以同计数排序一样，桶排序适用于元素值分布较为集中的序列。
基数排序
算法描述:把待排序中的元素按照低位先排序,然后收集,再按照高位排序,再收集,直至最高位.①,获取序列中的最大数,然后取得其位数,然后利用计数排序的特点,定义10个元素的数组,分别统计以待排序列元素的每一位为数组的下标的元素的个数,然后再定义一个数组存每个的起始地址.开一个辅助空间,放置元素.再回收这些元素.
图解基数
代码实现
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> #include<string.h> //统计最大元素的位数 int GetMaxValue_BitCount(int *arr,int size){ int i = 0; int count = 1; int ret = 10; for ( i = 0; i < size; i++) { while (arr[i] >= ret) { count++; ret *= 10; } } return count; } void _RadixSort(int *arr,int size,int *temp){ int Max_BitCount = GetMaxValue_BitCount(arr, size); //存每个桶中元素的个数. int count[10] = { 0 }; //存每个桶的起始地址 int start_Addr[10] = { 0 }; int i = 0; int ret = 1; int index = 0; while (Max_BitCount) { //统计个数 for ( i = 0; i < size; i++) { count[arr[i] / ret % 10]++; } //计算地址 for ( i = 1; i < 10; i++) { start_Addr[i] = start_Addr[i - 1] + count[i - 1]; } //放置元素到临时空间中 for (i = 0; i <size; i++){ int Addr = arr[i]/ret% 10; temp[start_Addr[Addr]++] = arr[i]; } //回收元素 //memcpy函数的功能是从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。 //void *memcpy(void *dest, const void *src, size_t n); memcpy(arr,temp,size*sizeof(arr[0])); ret *= 10; Max_BitCount--; } } void RadixSort(int *arr,int size){ int *temp = (int *)malloc(size*sizeof(arr[0])); if (temp==NULL) { assert(0); return; } _RadixSort(arr,size,temp); free(temp); } int main(){ int arr[11] = {198,254,378,852,761,554,581,552,605,479,853}; int size = sizeof(arr) / sizeof(arr[0]); RadixSort(arr,size); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } system("pause"); return 0; }
基数排序的特性总结
1、时间复杂度：O(kn)
2、空间复杂度：O(n+k)
3、稳定排序
4、非原地排序
排序算法复杂度及稳定性分析
基础排序
冒泡排序:效率太低O(N^2)
选择排序:效率较低O(N^2),但经常用它内部的循环方式来找最大值和最小值
插排: 虽然效率低，但是在序列基本有序时,它很快,所以也有其使用范围
希尔(缩小增量排序):是插排的改良，对空间思维训练有帮助
分治法
1.子问题拆分
2.递归求解子问题
3.合并子问题的解
快排: 是软件工业中最常见的常规排序法,其**双向指针扫描**和**分区**算法是核心,
往往用于解决类似问题，特别地partition算法用来划分不同性质的元素.
时间复杂度O(NlgN)，但如果主元不是中位数的话，特别是每次主元都在数组区间的一侧，复杂度将会退化成O(N^2）
工业优化:三点取中法，绝对中值法
快排重视子问题拆分
归并排序：空间换时间——逆序对数
归并重视子问题的合并
堆排序:用到了二叉堆数据结构,是继续掌握树结构的起手式常用于解决topk问题
=插排+二分查找
上面三个都是NlgN的复杂度,其中快排是表现最好的,是原址的不用开辟辅助空间,堆排也是原止的，但常数因子较大，不具备优势
上面都是都是基于比较的排序,可证明他们在元素随机顺序情况下最好是NlgN
非比较排序,在特定情况下会比基于比较的排序要快
计数排序:可以说是最快的:O(N+K)
用它解决问题时必须注意如果序列中的值分布非常广空间将会浪费很多,所以计数排序适用范围
序列的关键字比较集中,已知边界，且边界较小(年龄问题)
桶排序:先分桶，再用其他排序方法对桶内元素排序，按桶的编号依次检出。
用它需注意序列的值是否均匀地分布在桶中
如果不均匀，那么个别桶中的元素会远多于其他桶,桶内排序用比较排序,极端情况下，全部还是不会退化成NlgN
其时间复杂度:O(N+C)，C=N*(lgN-lgM);M是桶的个数
基数排序:是整数数值型排序里面又稳又快的，无论元素分布如何,只开辟固定的辅助空间（10个桶）
因此在实际应用中，对十进制整数来说,基数排序更好用
