排序（插入，希尔，选择，堆，冒泡，快速，归并，计数）

本文中的Swap()函数都是下面这段代码

// 交换
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}

---

常见排序：

一.插入排序

1.直接插入排序：

直接插入排序的基本思想：通过取一个数a与前面的数比较，a小则将前面的数后移，a继续向前比较，直到找到比a更小的数，插入到该位置。

代码实现：

// 直接插入排序  时间：O(N^2)   空间：O(1)
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];// [0,end]区间为有序的，排序好的有序区间// end+1位置的值插入到有序区间中while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

2.希尔排序：

希尔排序的基本思想：先选定一个整数gap，将需要排序的内容分为gap组，所有的距离为gap的在同一组，并对每一组内的数进行排序。然后重复上述操作，直到gap减为1。

我们来看一下分步图：

// 希尔排序  时间：O(N^1.3)（大致）   空间：O(1)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保证最后一个gap一定是1// gap > 1 时是预排序// gap == 1 时是插入排序gap = gap / 3 + 1;for (int i = 0; i < n - 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时都是在对数组进行预排序，当gap = 1时，此时的数组已经接近有序了，且当gap为1时，我们代入到希尔排序的代码中，再与上面的插入排序比较一下，我们就能发现是一样的。

二.选择排序

1.选择排序：

选择排序的基本思想：每一次从待排序的数据中选出最小（或最大值），将其放在前面，直到全部待排序的数据元素排完。

为了提高排序效率，我们也可以同时选出最小值和最大值，将最小值放在前面，最大值放在后面。

// 选择排序  时间：O(N^2)   空间：O(1)
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;  // 定义首位元素地址,同时找到最大和最小的，分别放到首和尾while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++)  // 找到最大和最小值的下标{if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);// 若首元素最大，将最小值交换到最前面后，begin会与maxi重叠// 需要更新maxi，防止begin与maxi重叠后，将把最小值交换到最后if (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}

2.堆排序：

堆排序需要我们对堆这个数据结构有一定了解。

堆排序时利用数据结构树（堆）进行排序的一种算法。通过堆进行选择数据。排升序建大堆，排降序建小堆。

我们来看一下分步图：

// 堆排序  时间：O(NlogN)   空间：O(1)
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//找到两个孩子中，较小/较大 的孩子                                                                                                                                      if (a[child + 1] < a[child] && child + 1 < n){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)
{// 向下调整建堆 O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

三.交换排序

1.冒泡排序：

冒泡排序的基本思路：从前向后，两两比较，小的放前，大的放后

// 冒泡排序  时间：O(N^2)   空间：O(1)
void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){int flag = 1;   // 标记设为1，若后面都有序则直接进行下一次循环for (int j = 0; j < n - i; j++){if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);flag = 0;}}if (flag == 1){break;}}
}

2.快速排序：

快排的代码我们采用分离处理，下面三种方法的代码只写明单趟排序。递归的部分在三种方法之后。

快速排序的基本思想：任取待排序元素中的某个元素作为基准值key，以这个基准值key将数组分割为两部分，左边的所有元素均小于基准值key，右边的所有元素均大于基准值key，然后将左边重复该过程，右边重复该过程，直到数组有序。

注（重要）：三数取中

在选取基准值key的时候，如果数组本身是有序的，直接对左边或者右边取key，这时算法的时间复杂度就会退化O(N^2)，因此递归的深度比较大，可能会导致栈溢出，这就很坑。所以，我们应该科学的选key，这种方法就是三数取中。

三数取中的基本思路：我们取最左边，中间，最右边三个值，对这三个值进行比较，选择中间大小的值作为key。

// 三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;// left midi rightif (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}else if (a[left] < a[right]){return right;}else{return left;}}else // a[left] > a[midi]{if (a[midi] > a[right]){return midi;}else if (a[left] < a[right]){return left;}else{return right;}}
}

（1）Hoare法：

在用Hoare法进行排序时，需要注意key的位置：左边做key，右边先走；右边做key，左边先走，这样才能保证相遇位置比key小。

我们来看一下分步图：

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);  // 将key值放在左边int keyi = left;int begin = left, end = right;while (begin < end){// 右边找小（右边先走）while (begin < end && a[keyi] <= a[end]){end--;}// 左边找大while (begin < end && a[keyi] >= a[begin]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;
}

（2）挖坑法：

挖坑法的基本思路：先用key存储基准值，将第一个位置形成一个坑位，右侧找比key小的数，放入坑位，这个数的原位置形成新的坑位，重复这个操作，直到最后的坑位左侧都小于key，右侧都大于key。

注意：当此处为坑位时，不进行移动，移动另一个指针。

我们来看一下分步图：

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];int begin = left, end = right;int holi = left;while (begin < end){while (begin < end && key <= a[end]){end--;}a[holi] = a[end];holi = end;while (begin < end && key >= a[begin]){begin++;}a[holi] = a[begin];holi = begin;}a[begin] = key;return begin;
}

（3）前后指针法：

前后指针法基本思路：cur找比key小的数，prev找比key大的数，然后进行交换，cur越界，最后将key和prev交换。

这种方法也不用和Hoare法一样考虑先走左还是先走右，也更易理解。

我们来看一下分步图：

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);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[keyi], &a[prev]);return prev;
}

快速排序递归版：

对上面三种方法进行递归，进行多次排序。

void QuickSort(int* a, int left, int right)
{if (left >= right)return;if ((right - left + 1) < 10)  // 这里小优化一下，数据内容小于10个的时候，直接进行插入排序，不走递归{InsertSort(a + left, right - left + 1);}else{// 三种方式随意选int keyi = PartSort1(a, left, right);//int keyi = PartSort2(a, left, right);//int keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

快速排序非递归版：

快排的非递归实现，需要用到栈这个数据结构，因此需要先了解栈。

快排的非递归基本思路：用栈模拟递归的实现，在栈中存储区域范围，然后取栈顶区间，单趟排序，右左子区间入栈，循环上面的操作，直到栈为空。

// 快速排序 非递归实现
#include"Stack.h"
void QuickSortNonR(int* a, int left, int right)
{Stack st;StackInit(&st);StackPush(&st, right);  // 先存right才能后用StackPush(&st, left);   // 后存left才能先用while (!StackEmpty(&st))  // 循环每走一次相当于之前的一次递归{int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = PartSort1(a, begin, end);  // 三种方式随意选// [begin, keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (begin < keyi - 1){StackPush(&st, keyi - 1);StackPush(&st, begin);}}StackDestroy(&st);
}

四.归并排序

1.归并排序

归并算法的基本思路：将已经有序的子序列合并，得到完全有序的序列；即先把每个子序列变成有序，然后两个子序列有序的合并成为一个新的有序子序列，最终合并为一个完整的有序序列。

我们来看一下分步图：

归并排序递归版：

// 归并排序    时间：O(NlogN)   空间：O(N)
//
// 归并排序递归实现
void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end){return;}int midi = (begin + end) / 2;  // [begin, midi] [midi + 1, end]  分为两个区间// 递归_MergeSort(a, tmp, begin, midi);_MergeSort(a, tmp, midi + 1, end);int begin1 = begin, end1 = midi;int begin2 = midi + 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, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}

归并排序非递归版

归并排序的基本思路：首先设置gap表示归并的元素个数，然后对子序列中的gap个元素进行归并，更新gap，重复上面操作，以循环的形式模拟递归的过程。

我们来看一下分步图：

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");}int gap = 1;  // 每组归并的数据个数while (gap < n){for (int i = 0; i < n; i += 2 * gap)  // i表示每组归并的起始位置{// [begin1, end1][begin2, end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;int j = i;// 这里需要对范围进行修正，否则有可能会导致数组越界访问// 第二组越界，整组都不需要归并if (begin2 >= n){break;}// 第二组的尾end2越界，修正后，再归并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, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(tmp);tmp = NULL;
}

五.计数排序

计数排序的基本思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。首先定义一个数组用来统计每个数出现的次数，然后根据统计的结果将序列回收到原来的序列中。

// 计数排序
void CountSort(int* a, int n)
{// 找最大，最小值，max - min + 1为count数组的长度，节省空间int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("malloc fail");}// 统计次数for(int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;  // 前面存储数据的时候减去了min，这里需要还原加上min}}free(count);count = NULL;
}