常见排序算法鉴赏（原理剖析+动图演示）

一、冒泡排序（BubbleSort）

二、选择排序（ SelectSort）

三、插入排序（InsertSort）

四、希尔排序（ShellSort）

五、堆排序

六、快排（QuickSort）

Hoare版本

前后指针法

优化之三数取中

七、归并排序（MergeSort）

八、计数排序（CountSoort）

九、小结

注：本文排序都是升序

一、冒泡排序（BubbleSort）

通过连续地比较与交换相邻元素实现排序，这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果“左元素>右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右端。

代码实现：

//冒泡排序
void BubbleSort(int* arr, size_t size) {for (size_t i = 0; i < size - 1; i++){bool exchange = 0;for (size_t j = 0; j < size - 1 - i; j++){if (arr[j] > arr[j + 1]) {Swap(&arr[j], &arr[j + 1]);exchange = 1;}}if (exchange == 0) break;}
}

动图演示：

二、选择排序（ SelectSort）

开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾：

初始状态下，所有元素未排序，即未排序（索引）区间为[0,𝑛−1]。
选取区间[0,𝑛−1]中的最小元素，将其与索引0处的元素交换。完成后，数组前1个元素已排序。
选取区间[1,𝑛−1]中的最小元素，将其与索引1处的元素交换。完成后，数组前2个元素已排序。
以此类推。经过𝑛−1轮选择与交换后，数组前𝑛−1个元素已排序。
仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

代码实现：


//简单选择排序
void SelectSort1(int* arr, size_t size) {//外层循环：[0,size-1]for (size_t i = 0; i < size - 1; i++){//记录最小值的索引size_t mini = i;//内层循环：找到未排序区间[1,size-1]的最小值//需要找size-1个数for (size_t j = i + 1; j < size; j++){if (arr[mini] > arr[j])mini = j;}Swap(&arr[i], &arr[mini]);}
}

优化版本：

从区间两边缩小，区间最左侧放最小值，区间最右侧放最大值

void SelectSort2(int* arr, size_t size) {size_t left = 0, right = size - 1;while (left <= right) {//假设第一个索引的值既是最大值也是最小值size_t mini = left, maxi = left;//只需要从第二个值开始遍历 找新的最大值最小值for (size_t i = left + 1; i <= right; i++){if (arr[i] > arr[maxi]) maxi = i;if (arr[i] < arr[mini]) mini = i;}//交换值Swap(&arr[left], &arr[mini]);//这里需要多个判断 如果maxi == left 两数交换两次相当于没有交换if (maxi == left) maxi = mini;Swap(&arr[right], &arr[maxi]);left++;right--;}
}

动图演示：

三、插入排序（InsertSort）

与手动整理一副牌的过程非常相似。具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。

代码实现：


//插入排序
void InsertSort(int* arr, int size) {//end走到倒数第二个就停下，无需再做比较for (size_t i = 0; i < size - 1; i++){//[0,end],end+1int end = i;int insertVal = arr[end + 1];while (end >= 0) {if (insertVal < arr[end]) {arr[end + 1] = arr[end];end--;}else {break;}}arr[end + 1] = insertVal;}}

动图演示：

四、希尔排序（ShellSort）

希尔排序又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个gap组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后（gap / 3 + 1）重复上述分组和排序的工作。当到达gap=1时，所有记录在统一组内排好序。

这里可以得到一个结论：

gap越大，数据跳跃越快，越小的越容易到前面，但是越不接近有序

gap越小，数据跳跃越慢，越小的不更易到前面，但是越接近有序

代码实现：

//希尔排序
void ShellSort(int* arr, size_t size) {int gap = size;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < size - gap; i++){//[0,end],end+1int end = i;int insertVal = arr[end + gap];while (end >= 0) {if (insertVal < arr[end]) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = insertVal;}}
}

五、堆排序

流程：

1）建堆实现升序建大根堆实现降序建小根堆

核心原理：

堆排序通过反复提取堆顶元素（极值）实现排序，堆的类型决定了提取元素的顺序：

大顶堆：堆顶始终为当前最大值
小顶堆：堆顶始终为当前最小值

2）排序利用堆删除思想排序

注：此流程图来源 hello‑algo.com

代码实现：

//向下调整算法，参数：数组 数组元素个数 开始向下调整的父节点索引
AdjustDown(HpDataType* arr, size_t size, size_t parent) {//找较大的子节点，假设左子节点较大size_t child = 2 * parent + 1;//child索引不断增大，但不会超过数组元素个数while (child < size) {//假设错误，右子节点更大，更新索引if (child + 1 < size && arr[child] < arr[child + 1]) {child++;}//如果父节点小于等于子节点，交换两节点的值if (arr[parent] <= arr[child]) {Swap(&arr[parent], &arr[child]);//更新父节点的索引，现在变成儿子了parent = child;//继续找儿子比较child = 2 * parent + 1;}else {break;}}
}void HeapSort(HpDataType* arr, int size) {// 建堆 升序建大根堆 降序建小根堆for (int i = (size - 2) / 2; i >= 0; i--) {AdjustDown(arr, size, i);}// 排序int end = size - 1;while (end > 0) {Swap(&arr[0], &arr[end]);  AdjustDown(arr, end, 0);   end--;}
}

六、快排（QuickSort）

Hoare版本

快排最早是由Hoare提出的，所以，他的经典思想我们有必要学习一下

有如下步骤：

1.基准元素选择

        选择数组第一个元素作为基准，记录基准索引keyi

2.双向指针扫描

设置两个指针left和right，left从数组左端（begin）开始向右扫描，right从右端（end）开始向左扫描，一定要让右指针先走，这样才能保证较大值右移、较小值左移
right指针寻找第一个小于等于基准的元素，找到之后停止不动
left指针寻找第一个大于等于基准的元素，找到之后停止不动
当两指针相遇或交叉时停止扫描

3. 元素交换

        当left < right时，交换arr[left]和arr[right]的值。这个交换操作能使较大值右移、较小值左移

4.分区完成判断

   重复步骤2-3直到left >= right，此时j所指位置即为当前分区的中间点。此时数组被划分为：左区间：[begin,keyi-1]右区间：[keyi+1,end]

5.递归排序

        对左右两个子数组分别递归执行上述过程，直到子数组长度为1时终止递归

第一趟详细排序：

递归完成最后排序：

动图演示：

代码实现：

//Hoare版本快排
void QuickSort2(int* arr, int left, int right) {if (left >= right)return;//创建变量保存区间边界int keyi = left;int begin = left, end = right;while (left < right) {//右边找小while (left < right && arr[keyi] <= arr[right]) {--right;}//左边找大while (left < right && arr[keyi] >= arr[left]) {++left;}Swap(&arr[left], &arr[right]);}Swap(&arr[keyi], &arr[left]);keyi = left;// [begin, keyi-1]keyi[keyi+1, end]QuickSort2(arr, begin, keyi - 1);QuickSort2(arr, keyi + 1, end);}

前后指针法

动图演示：

核心思路：

1.选定最左侧元素为基准值并保存，将prev设置为left，cur设置为left+1

2.cur去寻找当前区间内比基准值小的元素

3.如果没找到，说明基准值右侧的元素都是大于基准值的，不需要其他操作，直接跳出循环即可

4.如果找到了先prev++，再将prev和cur位置的元素交换，然后cur++。

5.等到cur越界之后，说明遍历完序列中的所有元素了，将基准值位置的元素和prev位置的元素交换

6.最后返回prev即可

代码实现：

//前后指针法快排
void QuickSort1(int* arr, int left, int right) {if (left >= right)return;int prev = left, keyi = left;int cur = left + 1;while (cur <= right) {if (arr[cur] < arr[keyi] && prev++ != cur) {Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//[left, keyi - 1] keyi [keyi + 1, right]QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi + 1, right);
}

优化之三数取中

如果遇到有序序列或者是接近有序序列，快排的效率就会接近O(n^2)，原因是我们每次选择keyi都是区间左值，这样可能选取到极端值（比如最小或最大元素）作为基准，这样会导致分区不平衡。

三数取中，顾名思义：取三个数中第二大的数

代码实现：

//三数取中
int ThreeNumMid(int* arr, int left, int right) {int mid = (left + right) / 2;if (arr[mid] < arr[right]) {if (arr[mid] > arr[left]) {return mid;}else if(arr[left] < arr[right]) {return left;}else {return right;}}else {// arr[mid] > arr[right]if (arr[mid] < arr[left]) {return mid;}else if (arr[right] < arr[left]) {return left;}else {return right;}}
}

但是如果数据量过小，我们三数取中法又显得十分累赘，这种情况下，我们可以选择更高效的排序，插入排序

优化后的代码：

//Hoare版本快排
void QuickSort2(int* arr, int left, int right) {if (left >= right)return;// 小区间选择走插入，可以减少90%左右的递归if (right - left + 1 < 10){InsertSort(arr + left, right - left + 1);}else {//创建变量保存区间边界int midi = ThreeNumMid(arr, left, right);Swap(&arr[left], &arr[midi]);int keyi = left;int begin = left, end = right;while (left < right) {//右边找小while (left < right && arr[keyi] <= arr[right]) {--right;}//左边找大while (left < right && arr[keyi] >= arr[left]) {++left;}Swap(&arr[left], &arr[right]);}Swap(&arr[keyi], &arr[left]);keyi = left;// [begin, keyi-1]keyi[keyi+1, end]QuickSort2(arr, begin, keyi - 1);QuickSort2(arr, keyi + 1, end);}//双指针法快排
void QuickSort1(int* arr, int left, int right) {if (left >= right)return;// 新增三数取中逻辑int mid = ThreeNumMid(arr, left, right);Swap(&arr[left], &arr[mid]);int keyi = left;int prev = left, cur = left + 1;while (cur <= right) {if (arr[cur] < arr[keyi] && prev++ != cur) {Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[keyi]);keyi = prev;QuickSort1(arr, left, keyi - 1);QuickSort1(arr, keyi + 1, right);
}

七、归并排序（MergeSort）

归并排序利用分治的思想，分为划分区间和归并排序两个阶段

1.划分区间阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题

2.归并排序阶段：当子数组长度为1时终止划分，开始归并，持续地将左右两个较短的有序数组归并为一个较长的有序数组，直至结束

如下图所示：

观察发现，归并排序与二叉树后序遍历的递归顺序是一致的。 ‧ 后序遍历：先递归左子树，再递归右子树，最后处理根节点 ‧ 归并排序：先递归左子数组，再递归右子数组，最后处理合并

代码实现：


//归并排序
void _MergeSort(int* arr, int* tmp, int begin, int end) {//递归到最小子区间if (begin == end)return;int mid = (begin + end) / 2;//[begin,mid] [mid+1,end]_MergeSort(arr, tmp, begin, mid);_MergeSort(arr, tmp, mid+1, end);//归并排序 将更大的值尾插到tmp数组中//分出两个区间范围值int left1 = begin, right1 = mid;int left2 = mid + 1, right2 = end;int i = begin;//判断两个区间的值谁更小while (left1 <= right1 && left2 <= right2) {if (arr[left1] < arr[left2]) {tmp[i++] = arr[left1++];}else {tmp[i++] = arr[left2++];}}//任何一个区间结束，将剩余的直接尾插while (left1 <= right1) {tmp[i++] = arr[left1++];}while (left2 <= right2) {tmp[i++] = arr[left2++];}//将排序好的tmp拷贝到arr中memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* arr, size_t size) {int* tmp = (int*)malloc(sizeof(int) * size);if (tmp == NULL) {perror("malloc() err!");return;}_MergeSort(arr, tmp, 0, size - 1);free(tmp);tmp = NULL;
}

动图演示：

八、计数排序（CountSoort）

核心原理：

统计每个数出现的次数，一个数出现几次，映射的位置值就加几次

这个排序算法有一定的局限性：

只适用于整型排序
只适用于数据集中的数据群
不适用于数据较为分散的数据群

代码实现：

//计数排序
void CountSoort(int* arr, size_t size) {//找最大值和最小值int min = arr[0], max = arr[0];for (size_t i = 1; i < size; i++){if (arr[i] < min) min = arr[i];if (arr[i] > max) max = arr[i];}//创建临时数组用于统计次数int range = max - min + 1;int* tmp = (int*)malloc(sizeof(int) * range);if (tmp == NULL) {perror("malloc() err!");return;}memset(tmp, 0, sizeof(int) * range);//统计次数for (size_t i = 0; i < size; i++){tmp[arr[i] - min]++;}//排序int j = 0;for (size_t i = 0; i < range; i++){while (tmp[i]--) {arr[j++] = i + min;}}}

动图演示：