八大排序

• 一，直接插入排序
• 二，希尔排序
• 三，选择排序
• 四，堆排序
• 五，冒泡排序
• 六，快速排序
• • 1，递归版本
  • • （1）hoare法
    • （2）挖坑法
    • （3）前后指针法（推荐）
  • 2，非递归版本
  • 3，快排的优化
  • • （1）三数取中
    • （2）小区间优化
    • （3）三路划分
• 七，归并排序
• • 1，递归实现
  • 2，非递归实现
• 八大排序稳定性总结

一，直接插入排序

思路：
在已经有序的数据基础上再插入一个新的数据，已经有序的数据最有一个数据的下标为end，将要插入的数据与end下标的数据比较，如果小于end小标的数据，那么end小标的数据就移动到end+1小标的位置，同时–end。同时，还要注意当end减小到-1时，就要停止比较直接插入到下标为0的位置。

下面看代码：

void InsertSort(int* a, int size){for (int i = 0; i < size - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}}

选择排序的时间复杂度：O(N^2)
空间复杂度：O(1)

二，希尔排序

希尔排序是直接插入排序的升级版本，由于当插入的值较小时，直接插入排序需要移动大量的数据，希尔排序对其做出的改进就是增加了多组预排序，将每隔gap间距的数据归为一组，一共可以分成gap组，对这gap组数据进行预排序时，在需要挪动数据的时候，数据跳动的步长大，不再像直接插入排序一样一步一步的挪动。

所以，希尔排序的单趟排序与直接插入排序十分类似，
下面看单趟排序的代码：

for(int j = 0;j < gap; j++){ for (int i = j; i < size - gap; i+=gap){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;}}

上面这种写法，是每排完一组后，再排另一组，我们可以对其简化一下，直接进行多组并排：

for (int i = 0; i < size - 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 ShellSort(int* a, int size){int gap=size;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < size - 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;}}}

gap再逐渐的减小，当减小到1的时候就是直接插入排序，但此时与直接插入排序相比，数据已经大部分有序了。

希尔排序是一个较为优秀的排序
时间复杂度：O(N^1.3)
空间复杂度：O(1)

三，选择排序

选择排序的思路是：
每次遍历数组标记出最大数据的小标与最小数据的下标，分别将其与最有一个数据和开头数据进行交换。
下面看代码：

void SelectSort(int* a, int size){int begin = 0;int end = size - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}swep(&a[begin], &a[mini]);if (maxi == begin){maxi = mini;}swep(&a[maxi], &a[end]);++begin;--end;}}

这种一次循环找出最大值与最小值的下标的写法，会存在一个小问题，就是maxi与begin重合的情况，当我们对mini与begin数据交换后，此时的begin下标位置的数据就已经不是最大的数据了，所以在交换end下标与maxi下标位置的数据前要先做判断。

选择排序的时间复杂度：O(N^2)
空间复杂度：O(1)

四，堆排序

堆排序的详细过程已在之前博客讲过：
链接: 堆排序博客

void AdjustDown(int* a, int size, int parent){int child = parent * 2 + 1;while (child < size){if (child+1<size&&a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){swep(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapSort(int* a, int size){for (int i = (size - 2) / 2; i >= 0; i--){AdjustDown(a, size, i);}int end = size - 1;while (end > 0){swep(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}}

堆排序也是一个比较优秀的排序：
时间复杂度：O(N*logN)
空间复杂度：O(1)

五，冒泡排序

不得不说，冒泡排序绝对是非常经典的排序，大量出现在教学中。
思路：
前后数据对比，若前面数据大于后面的数据就交换，这样经过第一轮的排序，最大值就被换到了末尾，这样以此往复，第二大的数据被放到倒数第二的位置…

void BubbleSort(int* a, int size){for (int i = 0; i < size; i++){int flag = 1;for (int j = 0; j < size - 1 - i; j++){if (a[j] > a[j + 1]){flag = 0;swep(&a[j], &a[j + 1]);}}if (flag){break;}}}

冒泡排序也可以进行一个小的优化，定义一个flag标识符，在进行一趟的比较中，如果没有进行过数据的交换，那么就证明此时这组数据已经有序了，那么就直接break跳出循环即可。

虽然，冒泡排序大量用在教学中，但其的性能不高，
时间复杂度：O(N^2)
空间复杂度：O(1)

六，快速排序

实际中，快速排序是被应用最广泛的排序，敢叫快速排序绝不是浪得虚名哟~
快速排序的单趟排序思路：首先选一个key位置，将key下标的数据调整到它在整个数据中的正确位置，并且将key位置的左右区间拆分成与其类似的子问题。

1，递归版本

（1）hoare法

hoare法：
1，选取key位置，通常选在数据的一个个位置也就是left位置。
2，如果key选在left位置，那么right指针先动，找到比key位置数据小的数据时停住。
3，left指针再动，找到比key位置数据大的数据后停住
4，交换left，right位置的数据，以此往复前面的操作，直到left，right相遇位置。
5，相遇后，交换key位置与相遇位置的数据，此时，相遇位置的左边的数据小于等于相遇位置的数据，右边的数据大于等于相遇位置的数据。所以，这个数据就调整到了它的正确位置。

int PartSort1(int* a, int begin, int end){int keyi = begin;int left = begin;int right = end;while (left < right){//找小while (left < right && a[right] >= a[keyi]){--right;}//找大while (left < right && a[left] <= a[keyi]){++left;}swep(&a[left], &a[right]);}swep(&a[keyi], &a[left]);keyi = left;return keyi;}

此时，肯定有人会有疑问？为什么相遇位置的数据一定小于等于key位置的数据。
首先，相遇无非两种情况：
1，right指针找到left指针
2，left指针找到right指针
先分析1：
当right指针移动的时候，说明之前已经发生过交换，交换后left指向的一定是比key位置数据小的数据。即使是right指针第一次移动时，直接移动到了数据的最左端与left相遇，那此时的相遇位置的数据与key位置的数据相同。

再分析2：
left指针移动前，right指针肯定移动过（因为规定right指针先移动），那么此时right指向的数据一定比key位置的数据小，所以left与right相遇时，相遇的位置的数据比key位置的数据要小。

（2）挖坑法

hoare法出现后，小的细节比较多，后面也出现了许多新的放法，比如：挖坑法
1，把数组left位置的数据赋值给key，形成了第一个坑位hole就是left位置。
注意：此时的key不再是数组的下标
2，还有right指针先动，找到比key小的数据停止，将数据填到坑位中，将此时的right赋值给hole形成新的坑位。
3，left指针后动，找到别key数据大的数据停止，将其填到坑位中，将left赋值给hole，形成新的坑位。
4，right与left相遇时停止，将key填入坑位中。此时，key数据就调整到了它的正确位置。

int PartSort2(int* a, int begin, int end){int key = a[begin];int hole = begin;int left = begin;int right = end;while (left < 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;}a[hole] = key;return hole;}

（3）前后指针法（推荐）

定义一个key是数组第一个元素的下标，prev指向第一个元素，cur指向第二个元素。
1，cur指针移动，找到比key为下标的数小的时候停止。
2，++prev，交换prev与cur位置的数据。
3，当cur指向数组最有一个位置的下一个位置时，循环停止。
4，交换key下标与prev下标的数据。

int PartSort3(int* a, int begin, int end){int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi]&&++prev!=cur){swep(&a[prev], &a[cur]);}++cur;}swep(&a[prev], &a[keyi]);keyi = prev;return keyi;}

这段代码中，可能有人会对if条件判断语句产生疑问，为什么这样写呢？
下面通过图示来解答：

上图就是，单趟循环的整个过程，我们发现前几次cur与prev指向的是同一个位置，所以就没必要进行交换。

下面看递归版本的完整代码：

int PartSort3(int* a, int begin, int end){int keyi = begin;int prev = begin;int cur = begin + 1;while (cur <= end){if (a[cur] < a[keyi]&&++prev!=cur){swep(&a[prev], &a[cur]);}++cur;}swep(&a[prev], &a[keyi]);keyi = prev;return keyi;}void QuickSort1(int* a, int begin, int end){if (begin >= end){return;}swep(&a[begin], &a[mid]);int keyi = PartSort3(a, begin, end);QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi+1, end);}

2，非递归版本

递归的写法虽然简单，但是当递归深度太深的话，就会出现问题，所以就出现了非递归的写法：
非递归是借助数据结构的栈来实现的
因为，快排是针对同一个数组的不同区间进行调整的，所以把要调整的区间存到栈中，然后每次取出栈顶的区间进行调整，调整完后将形成新的两段区间压栈。
注意：为了模拟递归的过程，要先压有段区间，再压左端区间。还有如果产生的两段区间中数据个数小于两个时，就不需要压栈了。

void QuickSortNonR(int* a, int begin, int end){ST st;STInit(&st);STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = left;int cur = left + 1;int prev = left;while (cur <= right){if (a[cur] < a[keyi]&&++prev!=cur){swep(&a[prev], &a[cur]);}++cur;}swep(&a[prev], &a[keyi]);keyi = prev;if (keyi + 1 < right){STPush(&st, end);STPush(&st, keyi + 1);}if (left < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);}

3，快排的优化

当每次选的key最终都被调整到数组的中间位置时，那么快排就类似一个二分结构，时间复杂度是O(N*logN)。

（1）三数取中

当数组本身就有序或者接近有序的时候，每次key都被调整到最开始或最末尾的位置，导致快排达不到一个二分的结构，此时的时间复杂度就为O(N^2)。
为了防止这种现象的出现，采取三数取中的方式，在begin，end，一个随机位置中选出第二大的数据与begin数据做交换，在在begin位置标记为key。
这样就不会存在上述问题了

int GetMidIndex(int* a, int begin, int end){int mid = begin + rand() % (end - begin);if (a[begin] > a[end]){if (a[end] > a[mid]){return end;}else if (a[mid] > a[begin]){return begin;}else{return mid;}}else{if (a[mid] < a[begin]){return begin;}else if (a[mid] > a[end]){return end;}else{return mid;}}}

（2）小区间优化

正常的快排类似于一个二分的结构，

最后一层的数量要占到总数的1/2左右，最后两层占到总数的3/4左右。
由于，递归是有消耗的，所以当区间内数据量小于10个的时候，我们就用插入排序来代替快速排序，这样减少递归的消耗。

void QuickSort1(int* a, int begin, int end){if (begin >= end){return;}if ((end - begin + 1) < 10){InsertSort(a, (end - begin + 1));}int mid = GetMidIndex(a, begin, end);swep(&a[begin], &a[mid]);int keyi = PartSort3(a, begin, end);QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi+1, end);}

（3）三路划分

当要排序的一组数据中，所有数据或者说绝大多数数据相等时，也会极大的降低快排的效率。
1，left和right分别指向数组的首个元素和末尾元素，将首个元素赋值给key。
2，cur指针指向首个元素的下一个元素。
3，当cur指向的数据小于key时，交换left和cur的数据，并且left++，cur++
4，当cur指向的数据大于key时，交换right和cur的数据，并且right–。
5，当cur指向的数据等于key时，cur++。
6，当cur与right错过时，停止循环。

将数组拆分为三段，begin-left-1是小于key的数据
left到right是等于key的数据
right+1到end是大于key的数据

void QuickSort2(int* a, int begin, int end){if (begin >= end){return;}if ((end - begin + 1) < 10){InsertSort(a, (end - begin + 1));}int mid = GetMidIndex(a, begin, end);swep(&a[begin], &a[mid]);int left = begin;int right = end;int key = a[begin];int cur = begin + 1;while (cur <= right){if (a[cur] < key){swep(&a[left], &a[cur]);++left;++cur;}else if (a[cur] > key){swep(&a[right], &a[cur]);--right;}else{++cur;}}QuickSort2(a, begin, left-1);QuickSort2(a, right+1, end);}

七，归并排序

1，递归实现

思路：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有
序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

（1）拆分：

（2）归并

递归代码实现：

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];++begin1;}else{tmp[i++] = a[begin2];++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 size){int* tmp = (int*)malloc(sizeof(int) * size);if (!tmp){perror("malloc fail");exit(-1);}_MergeSort(a, 0, size - 1,tmp);free(tmp);tmp = NULL;}

2，非递归实现

递归调用占用堆栈的空间，每递归一次都会新开辟一块空间，这样当递归的深度太深的时候，可能会栈溢出。
由于，归并的第一步是拆分，将一个n个数据的数组，拆分成n个一个数据的数组，再归并tmp数组中，再将tmp数组拷贝回去。设定一个rangeN表示两两数组归并时，数组中的数据个数。

上面是理想状态
当数据个数不是2的整数倍的时候，会出现越界的情况，需要我们对区间进行控制。
（1）end1越界

（2）begin2越界

（3）end2越界

对上述情况做出处理：

void MergeSortNonR(int* a, int size){int* tmp = (int*)malloc(sizeof(int) * size);if (!tmp){perror("malloc fail");exit(-1);}int rangeN = 1;while (rangeN < size){for (int j = 0; j < size; j += rangeN * 2){int begin1 = j;int end1 = j + rangeN - 1;int begin2 = j + rangeN;int end2 = j + rangeN * 2 - 1;if (end1 >= size){end1 = size - 1;begin2 = size;end2 = size - 1;}else if (begin2 >= size){begin2 = size;end2 = size - 1;}else if (end2 >= size){end2 = size - 1;}int i = j;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1];++begin1;}else{tmp[i++] = a[begin2];++begin2;}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}}memcpy(a, tmp, sizeof(int) * size);rangeN *= 2;}}

归并排序时间复杂度：O(N*logN)
空间复杂度:O(N)

八大排序稳定性总结

稳定排序：冒泡排序，插入排序，归并排序
非稳定排序：选择排序，希尔排序，堆排序，快速排序

非稳定排序的例子
1，选择排序

2，希尔排序由于进行多组预排序，当相同的数据被分配到不同组时，并且在不同组内的相对顺序不同时，就会使排序不稳定。
3，堆排序

这是一个大堆当第一个8与堆的最后一个元素交换后，将堆的节点数-1，向下调整后再与堆的最有一个元素交换时，就会破坏稳定性。
（4）快速排序