②快速排序三数取中版
我们选数要选一个合适的数，不能过大也不能过小，大小适中最为适合，于是我们提出了三数取中，即：取第一个数，最后一个数以及中间的数三个数比较，取中位数。
int GetMidIndex(int* a, int begin, int end) { int mid = begin + (end - begin) / 2; if (a[begin] < a[mid]) { if (a[mid] < a[end]) return mid; else//a[mid]>=a[end] { return a[end] > a[mid] ? end : mid; } } else//(a[begin]>=a[mid]) { if (a[mid] > a[end]) return mid; else//a[mid]<=a[end] return a[begin] > a[end] ? end : begin; } } int PartSort2(int* a, int left, int right) { int mid = GetMidIndex(a,left,right); Swap(&a[left], &a[mid]); int keyi = left; while (left < right) { //因为选取在左侧，所以要right先走 while (left < right && a[right] >= a[keyi])//右选小 { right--; } while (left < right && a[left] <= a[keyi])//左选大 { left++; } //选到左大，右小，进行交换 if (left < right) Swap(&a[left], &a[right]); } int meeti = left; Swap(&a[keyi], &a[meeti]); return meeti; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int meeti = PartSort2(a, left, right); QuickSort(a, left, meeti-1); QuickSort(a, meeti + 1, right); }
三数取中有个细节需要提醒一下，如果找到中位数，不是把这个中位数的下标作为keyi，而是把这个数和最左侧的数进行交换，还是以left作为keyi。
我们再来看一下三数取中模式递归调用堆栈的情况。
我们看到三数取中已经很不错了，但是它最后三层调用了80%的堆栈，如果这样的快排去排更多的数据，很可能会栈溢出，为了避免，我们可以进一步优化，把最后接近有序的数据用插排来排，这样会快上不少，也能避免栈溢出。
void QuickSort(int* a, int left, int right) { if (left >= right) return; if (right - left <= 8) { InsertSort(a + left, right - left + 1); } else { int meeti = PartSort2(a, left, right); QuickSort(a, left, meeti - 1); QuickSort(a, meeti + 1, right); } }
2.挖坑法
挖坑法是快排的另一种玩法，效率和hoare版本的差不多，也是用到了三数取中。
//挖坑法 int PartSort3(int* a, int left, int right) { int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int key = a[left];//存下来 int hole = left; while (left < right) { //因为选取在左侧，所以要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; //选到左大，右小，进行交换 if (left < right) Swap(&a[left], &a[right]); } a[hole] = key; return hole; }
3.前后指针版
int PartSort4(int* a, int left, int right) { int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int keyi = left; int prev = left; int cur = left+1; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[cur], &a[prev]); ++cur; } Swap(&a[keyi], &a[prev]); return prev; }
4.非递归实现快排
有些公司在面试的时候曾经提出这个问题，当然对于没有接触过的，当时可能就懵了。
我们来分析一下递归的时候，栈做了什么：
递归版本我们借助栈做了什么？不就是对这组数据不断细分然后进行三数取中再排，之前我们压栈放的这些分组，借助我们自己实现的栈去放也是一样的道理。
只不过我们需要先调用栈：
#include"Stack.h" #pragma once #include<stdio.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps,STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST* ps); void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } void StackCheckCapacity(ST* ps) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* newStack = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (newStack == NULL) { perror("realloc fail"); exit(-1); } else { ps->a = newStack; ps->capacity = newcapacity; } } } void StackPush(ST* ps, STDataType x) { assert(ps); StackCheckCapacity(ps); ps->a[ps->top] = x; ++ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDataType StackTop(ST* ps) { assert(ps); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } void QuickSortNonr(int* a, int left, int right) { ST st; StackInit(&st); StackPush(&st, left); StackPush(&st, right); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int keyi=PartSort4(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); }
快速排序特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN).
4. 稳定性：不稳定.
五、归并排序
基本思想：
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法（ Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
5.1递归版归并排序
我们观察归并排序的过程，就会发现，它本质是不断细分，(不断递归)，直到只剩两个数，然后借助第三空间，取小尾插，再返回上一级，层层递进，最后再把第三空间排号的数拷贝到原数组中，这时候就完成了归并的过程。
//归并排序 void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = begin + (end - begin) / 2; _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); int begin1 = begin, end1 = mid; int begin2 = mid + 1, 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"); return; } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
5.2非递归版归并排序
非递归版要比递归版本考虑更多情形，我们知道递归版本是递归到2个数据归并，然后返回，变为4个数据归并，不断返回。如果，我们刚开始就把数组里的数据从2个开始归并，然后开始不断扩大区间。
因为数据的个数不一定是整数倍，但是我们计算是按照整数倍来计算的，存在越界的情况，因此我们要修正一些场景。
我们要想明白归并排序是两组数据归并之后进行比较，取小的尾插，因此必须要有两组数据进行比较，我们分析越界情况有如下几种：
1.第一组end1越界。这种情况就没有了第二组，因此直接break，让它在其他gap值重新分组归并。
2.第二组全部越界。这种也是只有第一组
3.第二组越界部分越界。这种情况需要修正边界，修正第二组的right为数组末尾。可以比较。
void MergeSortNonR(int* a,int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { //gap个数据归并 for (int j = 0; j < n; j +=2* gap)//因为是两组数据 { int begin1 = j, end1 = j + gap - 1; int begin2 = j + gap, end2 = j + gap * 2 - 1; //第一组部分越界 if (end1 >= n) { break; } //第二组全部越界 if (begin2 >= n) { break; } //第二组部分越界 if (end2 >= n) { end2 = n - 1; } int i = j; 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 + j, tmp + j, (end2 - j + 1) * sizeof(int)); } gap *= 2; } free(tmp); tmp = NULL; }
归并排序的特性总结：
1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(N)
4. 稳定性：稳定
六、非比较排序(计数排序)
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
1. 统计相同元素出现次数。
2. 根据统计的结果将序列回收到原来的序列中。
计数排序的思想很有趣，统计数组中每个数出现的次数存到另一个数组中，另一个数组的下标加上最小的值就是要排序数组里的元素，而这些下标对应的值就是它出现的次数。
void CountSort(int* a, int n) { int max = a[0], min = 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* countA = (int*)malloc(sizeof(int) * range); if (countA == NULL) { perror("malloc fail"); return; } memset(countA, 0, sizeof(int) * range); for (int i = 0; i < n; ++i) { countA[a[i] - min]++; } int j = 0; for (int i = 0; i < range; ++i) { while (countA[i]--) { a[j]=i+min; ++j; } } free(countA); }
计数排序的特性总结：
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度： O(MAX(N, 范围 ))
3. 空间复杂度： O( 范围 )
4. 稳定性：稳定
七、排序算法复杂度及稳定性分析
