目录
本篇文章主要是介绍一些数据结构的基础排序算法。
常见的排序算法：
插入排序：
- 直接插入排序
- 希尔排序
选择排序：
- 选择排序
- 堆排序
交换排序：
- 冒泡排序
- 快速排序
归并排序：
- 归并排序
排序算法复杂度及稳定性分析：
排序介绍与实现：
1.直接插入排序
动图演示：
直接插入排序是认为要插入数之前的所有数据已经排序好，用一个tmp临时变量存储要插入的值，如果要插入值的前一个数据比他大，那么就向后覆盖，接着继续往前比，直到遇到比要插入值小的数据，将要插入值插入在该数据的后一位。
代码演示：
void Insert_Sort(int* a, int n)
{
// 这边由于要取值到end+1，所以end的最大值为n-2,所以 i < n-1;
for (int i = 0; i < n - 1; i++)
{
int end = i;
// tmp用于存放插入数
int tmp = a[end + 1];
// 写法一：
while (end >= 0) // end为下标，最坏的比较情况是插入值小于a[0]
{
if (a[end] > tmp)
{
a[end + 1] = a[end];// 如果插入数小则向后覆盖
--end; // 继续比较前一个，如果比较的是a[0]，那么当前的end<0,会跳出循环
}
else {
break;
}
}
a[end + 1] = tmp;
// 写法二：
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else {
a[end + 1] = tmp;
break;
}
}
// 特殊情况如果插入值比a[0]还小，end<0,但在上述循环中无法插入
if (end < 0)
{
a[end + 1] = tmp;
}
}
}2.希尔排序
静态图介绍：
希尔排序是直接插入排序的升级版，相较于直接插入排序，希尔排序会对要排序的数据进行一个预处理，他不是像插入排序一样直接前一个和后一个比较插入，这样的间距gap==1，那样的效率太慢了，希尔排序则是跨大步，将间距gap变大，实现快速的跳跃，举个例子，如果我们排升序，那么这种方法就可以将大的数据快速的放到后面，小的数据放在前面，当数据预排序差不多了，gap再次调整为1，进行直接插入排序，所以希尔排序的最后一步一定是直接插入排序，因此希尔排序可以称作为直接插入排序的升级版。
gap的选取没有具体明确的最好规定，小编这边推荐取gap=n/3+1为起始gap。
代码演示：
void Shell_Sort(int* a, int n)
{
int gap = n; // 先将gap赋值为n
while (gap>1)
{
gap = gap / 3 + 1; // 算取初始gap
// 写法一：
// 以组排序
// 先排序第一组，也就是用相同颜色线连接的数据
for (int i = 0; i < gap; i++) // 划分为gap/3个区域
{
// 比较一趟的数据（具体逻辑和直接插入排序无区别，只是原本直接插入排序的gap为1）
for (int j = i; j < n - gap; j++)
{
int end = j;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
// 写法二：
// 一个一个排序
// 从0~n-gap数据
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
}3.选择排序
静态图介绍：
选择排序是从数据的首端去进行选择，遍历一遍数组取选出最大值和最小值，选出后交换放在两端排序，继续去选择。注意的是如果最大值是第一个数据，后面交换时会出现数据被替代的情况，这种情况下我们需要在交换后将最大值下标指向最小值下标。
代码演示：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Select_Sort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
// 如果比最大值还大，更新最大值下标
if (a[i] > a[maxi])
{
maxi = i;
}
// 如果比最小值还小，更新最小值下标
if (a[i] < a[mini])
{
mini = i;
}
}
// 将最小值交换放在首位
Swap(&a[begin], &a[mini]);
// 如果最大值是首位，那么在交换后最大值被放在的mini下标的位置
if (begin == maxi)
{
maxi = mini;
}
// 将最大值交换放在末尾
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
4.堆排序
静态图介绍：
堆排序之前需要对数据进行建堆处理，建堆分为大堆，小堆，大堆指的是所有父亲节点的值都要大于孩子节点；小堆指的是所有父亲节点的值都要小于孩子节点。建堆又可以分为向上调整和向下调整，向上调整指的是将数据插入末尾，然后根据什么堆型去进行调整；向下调整指的是第一个父亲节点位置开始根据堆型情况向下进行调整。 建完堆最后的排序需要使用向下调整，升序建大堆，降序建小堆。
代码演示：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
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 Heap_Sort(int* a, int n)
{
// 建堆
// i 起始为第一个父亲节点
// 方法1：使用向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// 方法2：使用向上调整建堆
for (int i = 0; i < n; i++)
{
AdjustUp(a, i);
}
// 排序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}5.冒泡排序
动图演示：
冒泡排序是前一项和后一项进行比较，如果大就进行交换，然后将数据一直冒到最后放置。冒泡排序可以进行一次优化，使用flag进行记录，如果遍历一次没有进行交换说明是有序的，直接跳出循环。
代码演示：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void Bubble_Sort(int* a, int n)
{
for (int i = 0; i < n - 1; ++i)
{
// 定义flag用于判断
int flag = 1;
for (int j = 0; j < n - 1 - i; ++j)
{
if (a[j + 1] < a[j])
{
Swap(&a[j + 1], &a[j]);
flag = 0;
}
}
// 如果排序一遍没有交换，说明有序，直接跳出
if (flag == 1)
{
break;
}
}
}6.快速排序hoare版本
hoare版本动态演示图：
该版本的快速排序通过定义数据左端的首数据为key，然后分别从左右两端开始找，先从右端找比key小的数据，再从左端找比key小的数据，交换。最后左右相遇的位置与key指向的数据交换，并且成为新的key。
新的可以划分成两个区域，递归继续往下调整。
代码实现：
void Quick_Sort_hoare(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
while (a[end] >= a[keyi] && begin < end)
{
--end;
}
while (a[begin] <= a[keyi] && begin < end)
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;
Quick_Sort_hoare(a, left, keyi - 1);
Quick_Sort_hoare(a, keyi + 1, right);
}但是我们上面实现的快速排序还有些小瑕疵，如果是有序数组排序，那么这种快速排序就是最坏的情况了，在数据过多的情况下还可能造成栈溢出的风险。
为了解决这种问题我们可以采用三数取中和小区间优化的方法。
代码实现：
// 三数取中
int GetMid(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right]) // left < mid < right
{
return mid;
}
else if (a[left] > a[right]) // right < left < mid
{
return left;
}
else { // left < right < mid
return right;
}
}
else { // mid < left
if (a[mid] > a[right]) // right < mid < left
{
return mid;
}
else if (a[right] > a[left]) // mid < left < right
{
return left;
}
else {
return right;
}
}
}
小区间优化：
这边推荐使用插入排序，优点是实现容易，并且对于快有序的数据的排序效率也高。
void Insert_Sort(int* a, int n)
{
// 这边由于要取值到end+1，所以end的最大值为n-2,所以 i < n-1;
for (int i = 0; i < n - 1; i++)
{
int end = i;
// tmp用于存放插入数
int tmp = a[end + 1];
// 写法一：
while (end >= 0) // end为下标，最坏的比较情况是插入值小于a[0]
{
if (a[end] > tmp)
{
a[end + 1] = a[end];// 如果插入数小则向后覆盖
--end; // 继续比较前一个，如果比较的是a[0]，那么当前的end<0,会跳出循环
}
else {
break;
}
}
a[end + 1] = tmp;
// 写法二：
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
--end;
}
else {
a[end + 1] = tmp;
break;
}
}
// 特殊情况如果插入值比a[0]还小，end<0,但在上述循环中无法插入
if (end < 0)
{
a[end + 1] = tmp;
}
}
}最后装备完全的快速排序代码：
// 三数取中
int GetMid(int* a, int left, int right)
{
int mid = (left + right) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right]) // left < mid < right
{
return mid;
}
else if (a[left] > a[right]) // right < left < mid
{
return left;
}
else { // left < right < mid
return right;
}
}
else { // mid < left
if (a[mid] > a[right]) // right < mid < left
{
return mid;
}
else if (a[right] > a[left]) // mid < left < right
{
return left;
}
else {
return right;
}
}
}
void Quick_Sort_hoare(int* a, int left, int right)
{
if (left >= right)
{
return;
}
if ((right - left + 1) < 10) // 这边算的是最后需要排序数据的个数
{
Insert_Sort(a + left, (right - left + 1)); // 注意这边a要加上left，不然就会从首位置算起
}
else{
// 取完数据需要进行交换
int mid = GetMid(a, left, right);
int keyi = left;
Swap(&a[mid], &a[keyi]);
int begin = left, end = right;
while (begin < end)
{
while (a[end] >= a[keyi] && begin < end)
{
--end;
}
while (a[begin] <= a[keyi] && begin < end)
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
keyi = begin;
Quick_Sort_hoare(a, left, keyi - 1);
Quick_Sort_hoare(a, keyi + 1, right);
}
}7.快速排序挖坑版本
动态演示图：
可能在前面的hoare版本还有小伙伴疑惑为什么最后相遇的数据一定小于key指向的数据，不同于hoare版本，挖坑版本的快速排序我们更加轻易可以理解最后交换的数据小于key的数据。
代码的整体实现和之前版本只有细微差异，下面是代码参考：
void Quick_Sort_Wk(int* a, int left, int right)
{
int keyi = left;
int key = a[left];
int begin = left, end = right;
while (begin < end)
{
while (a[end] >= key && begin < end)
{
--end;
}
if (a[end] < key)
{
a[keyi] = a[end];
keyi = end;
}
while (a[begin] <= key && begin < end)
{
++begin;
}
if (a[begin] > key)
{
a[keyi] = a[begin];
keyi = begin;
}
}
a[begin] = key;
Quick_Sort_hoare(a, left, keyi - 1);
Quick_Sort_hoare(a, keyi + 1, right);
}当然该版本也可以加入之前版本的优化。
8.快速排序指针版本
动态演示图：
用key记录比较数据下标，然后创建prev和cur指针，prev指针从首位置开始，cur指针指向prev的下一个位置，cur指针向前走，如果cur指向的数据小于key下标指向的数据，那么prev++，prev和cur指向的数据交换，cur++；如果cur指向的数据大于key下标指向的数据，cur指针继续向前走，直到cur指针超过right范围，prev指向的数据和key的数据交换，prev的位置成为新的key。
代码实现：
void Quick_Sort_Point(int* a, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if(a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
// 范围
[left, keyi - 1] keyi [keyi + 1, right]
Quick_Sort_Point(a, left, keyi - 1);
Quick_Sort_Point(a, keyi + 1, right);
}9.快速排序非递归版本
静态图介绍：
我们都知道递归的缺点是一旦深度太深可能会造成栈溢出的问题，所以有些必要的时候需要我们取实现非递归版本来优化，那么怎么实现非递归版本呢，很简单，就是去模拟递归的过程。
递归的走法是先算出keyi的值，然后通过范围【left， keyi-1】keyi【keyi+1，right】分别去递归左边的数据和右边的数据，以此类推往下走，那么我们非递归的实现也需要借助栈，具体过程如上图。
注意：32位机器，函数创建的栈帧存储在栈区，大小大概为8M，而通过数据结构实现的栈存储在堆区，大概为3G
代码实现：
#include "Stack.h"
//
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int partSort(int*a, int left, int right)
{
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[prev], &a[keyi]);
return prev;
}
void QuickSort_Nore(int* a, int left, int right)
{
Stack s;
stackInit(&s);
// 先压右再压左
stackPush(&s, right);
stackPush(&s, left);
while (!stackIsEmpty(&s))
{
int begin = stackTop(&s);
stackPop(&s);
int end = stackTop(&s);
stackPop(&s);
int keyi = partSort(a, begin, end);
// 范围 [begin, keyi-1] keyi [keyi+1, end];
// 先压右再压左
if (keyi + 1 < end)
{
// 先压右再压左
stackPush(&s, end);
stackPush(&s, keyi + 1);
}
if (begin < keyi - 1)
{
// 先压右再压左
stackPush(&s, keyi - 1);
stackPush(&s, begin);
}
}
stackDestroy(&s);
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(a) / sizeof(int);
QuickSort_Nore(a, 0, len - 1);
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
return 0;
}10.归并排序
动态演示图：
代码实现：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
{
return;
}
int mid = (begin + end) / 2;
// 范围 [begin, mid][mid+1, end];
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
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, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(a) / sizeof(int);
MergeSort(a, len);
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
return 0;
}11.归并排序非递归版本
静态图介绍：
代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void _MergeSort_Nore(int* a, int* tmp, int n)
{
// 每组归并的数据的个数
int gap = 1;
while (gap < n) // 归并数据的个数最大不能超过n
{
// gap*2跳过的是前一组归并的数，如[0,0][1,1]归并，下一组归并的数应该是[2,2][3,3]
for (int i = 0; i < n; i += 2 * gap)
{
// 这边gap+i等于需要归并的数据个数，但是我们的end是下标所以要-1
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
// 临时数组的下标
int j = i;
// 如果begin2已经超出范围，那么就不用归并了，直接跳出循环
// 为什么不用end1判断，有可能是end1刚好没过范围，但是begin2过了
// begin2过了范围一定就不用归并了
if (begin2 >= n)
{
break;
}
// 如果begin2没有超出范围，而是end2超出范围，这时我们就需要进行调整
// 因为我们不能确保每次归并的数据都是相等的，有可能是4个有序数据和3个有序数据进行归并，这种情况也是可以的
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));
}
// 调整gap
gap *= 2;
}
}
void MergeSort_Nore(int* a, int n)
{
// 申请tmp数组进行临时拷贝
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort_Nore(a, tmp, n);
free(tmp);
tmp = NULL;
}
int main()
{
int a[] = { 6,1,2,7,9,3,4,5,10,8 };
int len = sizeof(a) / sizeof(int);
MergeSort_Nore(a, len);
for (int i = 0; i < len; i++)
{
printf("%d ", a[i]);
}
return 0;
}