一、排序简介
生活中，我们经常能看到排序的应用。例如，我们在网购商品的时候，经常按销量从高到低排序。
常见的排序算法有：
先来介绍一下关于排序算法的几个概念。
稳定性：相等的元素排序之后相对次序不变
内部排序：数据全在内存中的排序
外部排序：数据太多不能同时在内存中
下面所有排序算法都以排升序为例。
二、直接插入排序
直接插入排序类似我们平时玩扑克牌的洗牌过程。
基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
如图所示，我们手上已经洗好了 2、4、5、10 四张牌。再拿到一张 7，先跟 10 比，比 10 小，所以再往前比对。跟 5 比，比 5 大，就把 7 挨着插到 5 的后面。这样我们手上的牌就从四张有序的牌变成五张有序的牌了。
我们来看一个动图：
该动图完整展现了插入排序的过程。
在代码实现中，我们把牌插到哪个位置，这个位置后面的所有元素就要后挪一位。而后挪会覆盖我们拿出来的那张牌原本位置的元素，所以应该先保存待插元素的值。
完整代码如下：
void InsertSort(int* a, int n)
{
for(int i = 1; i < n; i++)
{
int tmp = a[i];
int j = i - 1;
while(j >= 0 && tmp < a[j])
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = tmp;
}
}
//小区间优化常用插入排序
因此，我们可以发现：
- 一开始越接近有序，插入排序的效率就越高。
- 插入排序后，相等元素的相对次序是不变的，故插入排序具有
稳定性。
时间复杂度：
最坏情况 O(N^2)
最好情况 O(N)
空间复杂度：O(1)
三、希尔排序
希尔排序，又称缩小增量排序。
上文提到，对于直接插入排序，一开始越接近有序，排序的效率越高。所以，希尔排序的优化方式就是先让数组接近有序。
希尔排序包括两个过程：预排序和直接插入排序。
- 预排序：让数组先接近有序。
按照间隔gap分组，进行直接插入排序，可以一组排完再排另一组，也可以多组一起排。 - 直接插入排序
在代码实现中，预排序其实就是gap > 1时进行排序的过程，直接插入排序也就是gap == 1时的排序过程。
完整代码如下：
void ShellSort(int* a, int n)
{
int gap = n / 2;
while (gap > 0)
{
for (int i = gap; i < n; i++)
{
int tmp = a[i];
int j = i;
while (j >= gap && tmp < a[j - gap])
{
a[j] = a[j - gap];
j -= gap;
}
a[j] = tmp;
}
gap /= 2;
}
}
//对于接近有序的序列，直接插入排序最快
//对于无序的序列，希尔排序能大幅优化插入排序的效率
希尔排序的具体效率很难计算，我们暂且认为时间复杂度大约在O(N^1.3)。
空间复杂度：O(1)
另外，在预排序中，相等元素的相对次序可能会发生变化，所以希尔排序是不稳定的。
四、选择排序
选择排序的思想其实非常简单，以升序为例，就是每次选出最小的换到左边。
思路非常简单，来看看代码怎么写。
void SelectSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int mini = i;
for (int j = i; j < n; j++)
{
if (a[j] < a[mini]) mini = j;
}
swap(&a[i], &a[mini]);
}
}
时间复杂度：O(N^2)
空间复杂度：O(1)
选择排序是不稳定的。
五、堆排序
堆排序是选择排序的一种，就是把原数组看成一个堆，利用堆的性质，对数组进行处理，达到排序的效果。
需要注意的是：排升序要建大堆，排降序建小堆。
具体过程如下：
完整代码如下：
//向下调整时间复杂度 O(logN)
void adjustDown(int a[], int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
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, i, n);
}
//排序时间复杂度 O(NlogN)
for (int i = n - 1; i >= 0; i--)
{
swap(&a[0], &a[i]);
adjustDown(a, 0, i);
}
}
时间复杂度：O(NlogN)
空间复杂度：O(1)
由于存在堆顶与末尾元素交换的过程，所以堆排序是不稳定的。
六、冒泡排序
以排升序为例，从前到后依次比较相邻两个元素，如果第一个比第二个大，就两两交换。第一趟把最大的元素推到最右边，第二趟把次大的元素放到倒数第二个位置，以此类推。
整个过程就像冒泡一样，每趟都把当前区间最大的元素往右边推，最后只剩第一个元素的时候本身有序。
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//n-1趟
{
bool flag = false;//检查是否交换
for (int j = 0; j < n - 1 - i; j++)//每趟比较n-1-i次
{
if (a[j] > a[j + 1])
{
swap(&a[j], &a[j + 1]);
flag = true;
}
}
if (!flag)//如果没交换，说明已经有序
{
break;
}
}
}
由于比较相邻元素时，相等不会交换位置，所以冒泡排序具有稳定性。
时间复杂度：
最坏情况 O(N^2)
最好情况 O(N)
空间复杂度：O(1)
可以发现，冒泡排序的时间复杂度无论最坏情况还是最好情况，都和直接插入排序相同。
因此我们可以比较一下二者的效率。
七、冒泡排序与直接插入排序效率对比
数组有序时：一样
接近有序时：冒泡慢一些
数组局部有序：冒泡慢很多
所以，虽然冒泡排序可能是我们最早接触的一种排序算法，但是它的效率真的很一般，甚至不如直接插入排序。文章来源：https://www.toymoban.com/news/detail-426401.html
测试函数：文章来源地址https://www.toymoban.com/news/detail-426401.html
void TestOP()
{
srand(time(0));
const int N = 50000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
int* a8 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
a8[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
BubbleSort(a5, N);
int end5 = clock();
int begin6 = clock();
quicksort(a6, 0, N - 1);
int end6 = clock();
int begin7 = clock();
MergeSort(a7, N);
int end7 = clock();
int begin8 = clock();
CountSort(a8, N);
int end8 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("BubbleSort:%d\n", end5 - begin5);
printf("QuickSort:%d\n", end6 - begin6);
printf("MergeSort:%d\n", end7 - begin7);
printf("CountSort:%d\n", end8 - begin8);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
}
到了这里，关于【数据结构】图解八大排序（上）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
