【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（一）https://developer.aliyun.com/article/1617280
3.4 选择排序（暴力选数）
基本思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
单趟排序:
void SelectSort(int* a, int n) { int begin = 0,end = n - 1; int max = begin, min = begin; //max为0，已经参与比较当中，这里begin+1防止冗余 for (int i = begin + 1; i <= end; i++)//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 SelectSort(int* a, int n) { int begin = 0,end = n - 1; int max = begin, min = begin; while (end > begin) { for (int i = begin + 1; i <= end; i++)//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--; } }
注意:这里需要注意当最大的数据在首元素，那么当第一次Swap把最大的数据，放在其他地方，导致了第二次Swap中max为下标的数据不是最大的数据。
进行两次交换会导致两个位置的数值所对应的索引发生改变，会对下一次交换产生影响，需要提前判断。
完整版本:
void SelectSort(int* a, int n) { int begin = 0,end = n - 1; int max = begin, min = begin; while (end > begin) { for (int i = begin + 1; i <= end; i++)//i从下一次开始 { if (a[i] > a[max]) { max = i; } if (a[i] < a[min]) { min = i; } } Swap(&a[begin], &a[min]); if (begin == max) { max = min; } Swap(&a[end], &a[max]); begin++; end--; } }
选择排序的特点总结:
- 选择排序思想非常好理解，但是效率不是很好。(实际中很少使用)
- 时间复杂度: O(N2)
- 空间复杂度: O(1)
- 稳定性:不稳定
3.4 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
void HeapSort(int *a,int n) { //O(N*logN) //for(int i=0;i<n;i++) //{ // AdjustUp(a,i); // } //O(N) for(int i=(n-1-1)/2;i>=0;--i) { AdjustDown(a,n,i);//从倒数的第一个非叶子，也就是最后一个结点的父亲 } int end=n-1;//下标--同时调整后，最后一个元素不再改动 //O(N*logN) while(end>0)//利用堆删除思想进行排序 { Swap(&a[0],&a[end]); AdjustDown(a,end,0);//要清楚为什么要向下调整 --end; } }
堆排序的特性总结:
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
3.5 冒泡排序
基本思想:比较两个相邻的元素，当不满足某一条件时，发生相邻元素的交换，直到整个序列有序为止。
原始版本:
int main() { int arr[10] = { 0 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { scanf("%d ", &arr[i]);///输入数据 } int tap = 0; for (int i = 0; i < sz - 1; i++) {//注意只需要sz-1趟就行，最后一次是两个相邻最后的排序 for (int j = 0; j < sz - 1 - i; j++) {//完成一趟，少一个元素参与排序所以-i，-1是下标的原因 if (arr[j] > arr[j + 1])//判断条件 {//进行交换 tap = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tap; } } } for (int i = 0; i < sz; i++) { printf("%d ", arr[i]);//打印数据 } return 0; }
过程解析:序列中两个相邻元素进行比较，当满足条件发生交换操作，导致最小或大元素放到后面位置，不断重复该过程，直到有序。
不足点:目的是直到有序就停下来，但是上面的逻辑是地毯式查找，对此我们需要设置一个标识变量去标识是否有序，如果不需要交换说明有序直接退出。
优化版本:
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> int main() { int arr[10] = { 0 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { scanf("%d ", &arr[i]);///输入数据 } int tap = 0; for (int i = 0; i < sz - 1; i++) { int flag=1; for (int j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { tap = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tap; flag=0; } } if(flag==1) { break; } } for (int i = 0; i < sz; i++) { printf("%d ", arr[i]);//打印数据 } return 0; }
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度: O (N2)
- 空间复杂度: O(1)
- 稳定性：稳定
小总结:选择排序与冒泡排序
选择和冒泡时间复杂度都是N2这个量级，但是还是有区别的
- 选择排序是：n n-2 n-4
- 冒泡排序是：n n-1 n-2
选择排序的每一轮都包含了选择和交换两个操作。虽然交换是实现排序的具体操作，但选择是排序策略的核心。
3.6 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法(属于前序遍历)
基本思想；任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排序都排序在相应位置上为止。（保证相遇位置为最小值，这点会专门验证）
3.6.1 三数取中
一般对于基准值keyi取最左值，但是序列是接近有序的话，可能会导致递归程度太深会栈溢出而程序奔溃。对于相对默认直接以最左值作为基准值，更倾向于采用随机数取值或者三数取中(不是最大最小值)，这里采用三数取中。
关于keyi还是在最左边取，通过三数取中将得到适合的数与keyi交换。
实现三数取中:
int Getmidi(int* a, int begin, int end) { int midi = (begin + end) + 2; if (a[begin] > a[end]) { if (a[midi] > a[begin]) return begin; else if (a[midi] > a[end]) return midi; else end; } else//a[begin] < a[end] { if (a[midi] > a[end]) return end; else if (a[midi] > a[begin]) return midi; else begin; } };
在实现过程中，需要以第一个条件为前提，再进行下一条语句判断。
3.6.2 小区间优化
面使用递归的方法很像满二叉树，关于满二叉树倒数几层节点占整颗满二叉树大部分。对此到一定数据时，可以不使用递归的方式，采用插入排序会更好一些(付出的代价更少点)。
3.6.3 hoare版本(坑多)
void PartSort1(int* a, int begin, int end) { if (begin >= end) { return; } int midi = GetMidi(a, begin, end);//将第一个元素大小取为不大也不小的数 Swap(&a[midi], &a[begin]); int keyi = begin;//得到第一个元素的下标 int left = begin; int right = end; while(right > left)//单趟 { // 右边找小 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]); keyi = left; //这里导致了begin和end的位置，不是最左或者最右 PartSort1(a, begin,keyi-1); PartSort1(a, keyi+1,end); }
过程解析:涉及到二叉树前序遍历方法，使用分治思想将一个整体不断分为两个部分去看待，当所有若干个小部分有序(只存在一个数，一定有序)，则整体有序。在每一阶段递归过程中，将基准值keyi对应数值使用三数取中进行Swap交换语句进行调整。
关于内层循环添加right > left条件判断为了保证在查找数据的时候，导致可能出现left和right超过，导致交换数据位置不理想，同时要求left和right相遇时，需要停止跟a[kayi]交换，跟a[keyi]相等的数据，放在哪个位置是无所谓的，没有影响。
3.6.4 相遇位置比keyi小推理(重点)
总结:不断缩小范围或者某一方向找不到，直到相遇的情况。但是相遇位置都是小，如果keyi在右边的话，那么只需要左边先走就可以了。
【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（三）https://developer.aliyun.com/article/1617282
