2.6快速排序：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序有三种写法：
1.hoare版本
2.挖坑法
3.前后指针法
以及优化：
1.三数取中
2.6.1hoare版本（递归版本）
动图演示：
hoare版本思路：
单趟排序，key一般选最左边或者最右边
当key为最左边，右边找小，左边找大，然后交换继续，相遇停止，相遇的值跟key交换
当key为最右边相反
当左区间有序，右区间有序那整体就ok了，如果左右区间不有序，左右区间就是单趟的子问题
当区间只有一个值，就不排了，返回
问题：为什么是key为最左边时，右边先走，最右边做key时，左边先走
answer：左边做key，右边先走，可以保证相遇位置比key要小
此时有两种情况：
1.相遇，left是停着(一定>=key)，right向后走，相遇的位置是left的位置
2.相遇，right是停着（一定<=key），left向前走，相遇的位置是right的位置
单趟有两个意义
1.分割出左右区间，左比key小，右比key大
2.key到了正确位置（排序后的最终位置）
key以后不用变了，到了正确位置
代码：
int Partsort1(int* a, int begin, int end) {//hoare版本 int mid = GetMidIndex(a, begin, end); Swap(&a[mid], &a[begin]); int left = begin; int right = end; int keyi = begin; 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]); keyi = left; return keyi; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end-begin+1 < 10) { InsertSort(a + begin, end - begin + 1); } else { int keyi=Partsort1(a, begin, end); //int keyi=Partsort2(a, begin, end); //int keyi = Partsort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
时间复杂度:O(NlogN)
2.6.2三数取中
每次排序都会将数组分为三个部分：
【left-key-1】【key】【keyi+1-right】
在理想情况下，我们每次进行完单趟排序后，key的左序列与右序列的长度都相同：
若每趟排序所选的key都正好是该序列的中间值，即单趟排序结束后key位于序列正中间，那么快速排序的时间复杂度就是O(NlogN)。
但事实上可能会遇到极端情况：就是我们每次取到的都是最大值或者最小值，那么快排的时间复杂度达到最低O（N^2）
可以看到，这种情况下，快速排序的时间复杂度退化为O(N^2)。其实，对快速排序效率影响最大的就是选取的key，若选取的key越接近中间位置，则则效率越高。
为了避免这种极端情况的发生，于是出现了三数取中：
三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。
代码：
int GetMidIndex(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] < a[mid]) { if (a[mid] < a[end]) { return mid; } else if (a[begin] > a[end])//a[mid]>a[end]的前提下 { return begin; } else//a[mid]>a[end]&&a[begin] < a[end]的前提下 { return end; } } else//a[begin] > a[mid] { if (a[end] < a[mid]) { return mid; } else if (a[begin] > a[end])//a[end] > a[mid] { return end; } else//a[end] > a[mid]&&a[begin] < a[end] { return begin; } } }
2.6.3挖坑法
动图演示：
思路：
将一开始的left保存起来，然后左边 空出来一个坑，右边先走，右找大，然后将右边的值的数据填进去，找到的位为坑，左边找小将右边的坑填进去，最后一定会在坑的位置相遇
代码：
int Partsort2(int* a, int begin, int end) {//挖坑法 int mid = GetMidIndex(a, begin, end); Swap(&a[mid], &a[begin]); int left = begin; int right = end; int keyi = a[left]; int hole = left; while (left < right) { while (left < right && a[right] >= keyi) { right--; } a[hole] = a[right]; hole = right; while (left < right && a[left] <= keyi) { left++; } a[hole]=a[left]; hole = left; } a[hole] = keyi; keyi = left; return hole; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end-begin+1 < 10) { InsertSort(a + begin, end - begin + 1); } else { //int keyi=Partsort1(a, begin, end); int keyi=Partsort2(a, begin, end); //int keyi = Partsort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
时间复杂度:O(NlogN)
2.6.4前后指针法：
动图演示：
思路：
1、cur找比key小，找到后停下来
2、++prev, 交换prev位置和cur位置的值
代码：
int Partsort3(int* a, int begin, int end) { int prev = begin; int cur = begin + 1; int keyi = begin; while (cur<=end) { /*if (a[cur] < a[keyi]) { Swap(&a[++prev], &a[cur]); }*/ if (a[cur] < a[keyi]&&++prev!=cur) { Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; return keyi; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end-begin+1 < 10) { InsertSort(a + begin, end - begin + 1); } else { /*int keyi=Partsort1(a, begin, end); int keyi=Partsort2(a, begin, end);*/ int keyi = Partsort3(a, begin, end); QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
时间复杂度:O(NlogN)
2.6.5非递归写法：
思路：
通过非递归的方式实现递归的情况的话，递归从底层是先排左边再排右边因此类推，因此写非递归我们从顶层到底层就需要反过来。
借助栈的内存结构让先入的后出，所以要先压begin再压end，取出来的话就是先出右再出左
再先排右边再排左边。
代码：
void QuickSortNonR(int* a, int begin, int end) {//非递归 ST st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int keyi = Partsort3(a, left, right);//单趟排序 if (keyi + 1 < right) { StackPush(&st, keyi+1); StackPush(&st, right); } if (left < keyi-1) { StackPush(&st, left); StackPush(&st, keyi - 1); } } StackDestory(&st); }
2.7归并排序
2.7.1递归写法：
动图讲解：
思路：
将两端有序序列取各种较小的值比较排序成一个有序序列。
代码：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) / 2; _MergeSort(a, mid+1, end, tmp); _MergeSort(a, begin, mid, tmp); int begin1 = begin; int end1 = mid; int begin2 = mid+1; int end2 = end; int i = begin; while (begin1<=end1&&begin2<=end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } 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 fail"); exit(-1); } _MergeSort(a, 0, n-1, tmp); free(tmp); tmp = NULL; } 3.
2.7.2非递归写法：
极端情况：
越界有三种情况
1.end1越界 begin2越界end2越界
2.begin2越界end2越界
3.end2越界
整体拷贝的话会有覆盖丢失
代码：
void MergeSortNonrR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int RangN = 1; while (RangN < n) { for (int i = 0; i < n; i += 2 * RangN) { int begin1 = i; int end1 = i + RangN - 1; int begin2 = i + RangN; int end2 = i + 2 * RangN - 1; int j = i; if (end1>=n)// 修正区间 ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝 { end1 = n - 1; begin2 = n;// 不存在区间 end2 = n - 1; } else if (begin2 >= n) { begin2 = n; end2 = n - 1; } else if(end2>=n) { end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } RangN *= 2; } free(tmp); tmp = NULL; }
时间复杂度：O（NlogN） 空间复杂度：O（N）
2.8计数排序
思路：
绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。
代码：
void CountSort(int* a, int n) { int min = a[0]; int max = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int* CoutA = (int*)calloc(range, sizeof(int)); if (CoutA == NULL) { perror("calloc fail"); exit(-1); } for (int i = 0; i < n; i++) { CoutA[a[i] - min]++; } int k = 0; for (int i = 0; i < range; i++) { while (CoutA[i]--) { a[k++] = i + min; } } free(CoutA); }
时间复杂度：O(N+range) 空间复杂度：O(range)
