排序及其代码详解~
排序是数据结构中一个十分重要的一部分，不管是平时还是其他时候，我们都能见到各种各样的排序，今天就来学习下各种排序吧。
在学习之前，我们需要知道一共有哪些排序。
目录
开胃菜——直接插入排序
插入排序的特性
希尔排序
选择排序
堆排序
冒泡排序
快速排序
快速排序的思想
Hoare法
挖坑法
前后指针法
快速排序的非递归
了解了大概有哪些排序后，就来正式学习吧。
开胃菜——直接插入排序
插入排序实际上就是在将一个数据插入到一个有序的数列之中它所应在的位置，从第一个数据一直到最后一个数据，然后就整个数据有序。
思想说起来简单，但是实验起来比较麻烦，这里先给代码然后再一句一句讲解：
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;
}
}
此处end表示一组数据有序序列的最后一位，用 i 控制，tmp则表示有序数据之后的一位数据，也就是我们需要插入有序数列中的数。
此处，如果我们需要插入到有序数列中的数比有序数列的a[end]还要小，那我们就需要将数据往后移动，而若是tmp大于a[end] 的时候，那么tmp就应该插入到a[end+1]的位置。
用语言文字比较难懂，那我就勉为其难用一张动图方便理解吧。
就像图中，若是tmp小于a[end]上的数，那么就将a[end+1]变成a[end] , 反之则说明tmp找到对的位置，由此插入。
插入排序的特性
从时间复杂度上来看，插入排序的时间复杂度是O(N^2)级别的；
但是在特殊场景下，插入排序的速度会提升，那就是当数据大致有序的时候，插入排序的速度非常快。
想象一个场景，当一组数据大致有序的时候，每一个tmp都可能只用寻找个数级别的次数就能插入到对应的位置，那么次数就大大减少了，那么利用这个特性，有大佬就优化了插入排序，这就是希尔排序。
希尔排序
正如上面所说，希尔排序实际上是根据插入排序优化而来，那么具体是怎样优化呢？且听我细细说来。
根据插入排序的特性，当一组数据大致有序的时候，就是插入排序最快的时候；
越接近有序，越是快速，那么希尔排序的优化，实际上就是将一组无序的数据变为接近有序
的数据，最后采用和插入排序一样的方法进行排序；
那么重点就是如何将一组无序的数据变为接近有序的数据；
而希尔排序的创始人给出了这样的答复
： 给数组分组排序就可以了！
正如希尔所说，希尔排序正是将数据分组排序，将数据变成大致有序的。
那么怎样才能让一组数据变得有序呢？
我们用一个变量gap用来将数据分组，比如我们给出一组数据
“2，1，6，3，9，10，5，2，6，4”
我们设置gap等于3。
就像这张图，设置gap为三，用不同颜色的线表示哪些数据是一组，然后将每一组数据按升序排序，这组数据就变成这样了。
这样就完成了一次排序，我们可以发现，排序后大的数据基本都到后面去了，而希尔排序正式运用这种办法，进行一次又一次的排序，并且减小gap，最后当gap == 1时，就能够很快的拍好序。
但是有一个问题，那就是gap如何设置初始值，若是当gap太小，那么组数过多，反而会导致排序效率降低，因此我们的gap也应该跟随数据的大小而变化。
了解这些之后，我们就直接来看看代码。
void ShellSort(int* a, int size)
{
int gap = size;
while (gap > 1)//是先判定
{
gap = gap / 3 + 1;//后改gap，所以最后一套还是gap
for (int i = 0; i < size-gap; i++)//i小于size-gap用来防止指针越界
{
int end = i;
int tmp = a[end + gap];// 和插入排序一样，只不过一个是在end+1而这里是根据gap分组的
while (end >= 0)
{
if (tmp < a[end])
{
Swap(&a[end], &a[end + gap]);
}
else
{
break;
}
end -= gap;//只在组内比较
}
a[end + gap] = tmp;
}
}
}实际上希尔排序中的gap等于1的时候，就相当于是插入排序，但是由于之前gap!=1的时候，内部已经将数组变得接近有序， 因此速度快多了。
选择排序
名副其实，选择排序就是和选择脱不开干系的排序；
这个算法核心就是每一次从数组中选取一个最小的数据和最初始的数据交换，从头到尾，由此进行排序。
这个估计听起来挺简单的，但是呢，写起来就会发现，其实更加简单。
这里就直接给代码：
void SelectSort(int* a, int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int maxi = begin;
int mini = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[maxi] < a[i])//找到更大的数就更新maxi
{
maxi = i;
}
if (a[mini] > a[i])
{
mini = i;// 找到更小的数就更行mini
}
}
Swap(&a[begin], &a[mini]);//从begin遍历到end后就交换mini和begin上的数据
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);//交换maxi和end上的数据
end--;
begin++;//更新end和begin
}
}看到这条代码，估计从头到尾找不到有什么难点，唯一一个难点是这个
为何当maxi和begin相等的时候，需要将maxi和mini更新呢？
我给出这样一组数据：
100，5，4，9，1，3，4，6，7.
很明显这里最大的数是100，那么在mini和begin上的数据交换后，100就会到mini上面去，因此需要更新maxi。
这里和交换顺序是有关系的，若是先end和maxi交换，那就反过来更新就是了。
堆排序
在我的博客
二叉树的顺序结构以及线性结构代码~_一般路过半缘君的博客-CSDN博客
中，我讲过堆的结构以及一些接口，若是不知道堆是什么的就请移步到这篇博客中去；
当我们需要用堆进行升序排序时，我们需要利用堆的向下排序建一个大根堆，而降序排序反而需要建一个小根堆；
为什么呢？我们用建立升序排序进行说明。
当我们将一组数据变成大根堆时，那我们就能发现，最大的数据一定在第一个位置；
那我们直接将第一个数据与最后一个数据交换，那么最后一个数据就是最大的了；
然后将数组从1到size-2的位置依次向下调整，这样就保存了原本的大根堆特性，然后重复这个操作就行了。
接下来看源码：
void HPAdjustDown(HDataType* a, int size, int parent)
{
assert(a);
int MinChild = parent * 2 + 1;
while (MinChild < size)
{
if (size > MinChild + 1 && a[MinChild] < a[MinChild + 1])//升序建大根堆，选择较大的那个孩子
{
MinChild++;
}
if (a[MinChild] > a[parent])//若孩子大于父亲，交换，建立大根堆
{
Swap(&a[MinChild], &a[parent]);
}
else
{
break;
}
parent = MinChild;
MinChild = parent * 2 + 1;
}
}
void HeapSort(int* a, int n)
{
int i = 0;
for (i = (n - 2) / 2; i >= 0; i--)//从倒数第一个非叶节点开始
{
HPAdjustDown(a, n, i);//排升序建大堆，降序建小堆
}
for (i = 1; i < n; i++)
{
Swap(&a[0], &a[n - i]);//将第一个数据和最后一个数据交换
HPAdjustDown(a, n - i, 0);//然后从size-i的位置到0的位置向下调整
}
}
这里有一个难点
首先是建立大根堆的位置，若是最后一层自然不用管，因为下面没有数据；
所以只用从倒数第一个非叶节点的位置建立大根堆；
并且由于向下调整算法想要建立一个大根堆，必须这个节点的左右节点都是堆，因此这里只能倒过来建立堆。
而倒数第一个非叶节点就是最后一个节点的父节点，根据公式，可以快速求出来。
冒泡排序
顾名思义，冒泡排序就是将大的数据往后移动，像一个泡泡从水里面冒出来一样。
就像这张图一样，有大的就交换；
那么这是怎么实现的呢？
我们先直接看源码
void BubbleSort(int* a, int size)
{
for (int i = 0; i < size; i++)
{
int exchange = 0;
for (int j = 1; j < size - i; j++)
{
if (a[j] < a[j-1])
{
Swap(&a[j], &a[j-1]);
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
}
}接下来一个一个讲解；
冒泡循环总体是由一个二层循环构成，外层总的就是将从0到size-1的数据依次比较；
而内层则有一点难点，那就是为什么 j < size - i；
实际上，这个size-i只是一个小小的优化罢了；
因为每一次我们完成内部循环的时候，就会将最大的数放到最后面；
所以就不用和最后面的几个数比较了，因为它们一定比前面的数都大；
而这些数的个数都和 i 有关，当 i = 0的时候，说明是第一次比较，最大的数没到最后；
i = 1则说明有一个最大的数到了最后面；
因此实际上我们内层循环就算是 j < size；
也是一样的，有图为证：
快速排序
要说运用最广泛的排序那必然是快速排序了，它能够适用多种场景；
并且它正和它的名字一样，十分快捷；
这么重要的排序我们当然不能错过啦；
快速排序的思想
以数组的某一个数为基准值；
将比基准值小的数放在基准值的左边；
将比基准值大的数放在基准值的右边；
然后递归去左边和右边分别重复这个操作；
这个思想是快速排序的创始人C.A.R.Hoare所提出的：
而这个方法也用这位大佬的名字命名，名叫Hoare法；
为了更好理解Hoare法，这里可以用一个动图表示：
看完一遍动图后，基本上Hoare法的代码也快呼之欲出了；
Hoare法
这里直接给出代码：
int GetMid(int* a, int begin, int end)
{
int mid = begin + (end - begin) / 2;
if (a[mid] > a[begin])
{
if (a[end] < a[begin])
{
return begin;
}
else if (a[mid] < a[end])
{
return mid;
}
else
{
return end;
}
}
else//a[mid]<=a[begin]
{
if (a[end] < a[mid])
{
return mid;
}
else if (a[end] > a[begin])
{
return begin;
}
else
{
return end;
}
}
}
//Hoare法
int PartSort1(int* a, int l, int r)
{
int mid = GetMid(a, l, r);
Swap(&a[l], &a[mid]);
int keyi = l;
while (l < r)
{
while (a[r] >= a[keyi] && l < r)//r找小
{
r--;
}
while (a[l] <= a[keyi] && l < r)//l找大
{
l++;
}
if (l < r)//必须要l在r左边，否则可能出现重复交换
{
Swap(&a[l], &a[r]);
}
}
int meeti = l;
Swap(&a[meeti], &a[keyi]);//meeti所在位置应该是keyi所在位置的最终位置，所以应该交换一次
return meeti;
}
void QuickSort(int* a, int begin, int end)
{
if (begin > end)
{
return;
}
if (end - begin <= 8)//小区间优化
{
InsertSort(a + begin, end - begin + 1);
}
int l = begin;
int r = end;
int keyi = PartSort1(a, l, r);// 得到一套循环后基准值所在位置
QuickSort(a, begin, keyi - 1);//分别在左边和右边递归
QuickSort(a, keyi + 1, end);
}看完代码后，大家应该会有一个疑问：
为什么要去寻找mid？
为什么要将 a[ l ] 和 a[mid]交换位置？
首先，我们要了解Hoare法的一个弊端，那就是当数据选取的基准值是固定的位置时；
有可能这个固定位置是这组数据中最大的数或者是最小的数；
那么我们的 l 或者 r 可能就会循环找完整个数组，导致效率低下；
之后就算是递归再次操作也可能有这个弊端；
因此我们需要用这个函数来在 begin 位置，mid位置，end位置三个位置中寻找不大不小的数，然后返回它的下标；
之后将找到的这个数和 l 交换，就能达到优化的效果；
挖坑法
了解了快速排序的Hoare法后，我们再来学一下快速排序的其它方法：挖坑法；
挖坑法和Hoare法不一样；
首先，Hoare法是利用 l 和 r 两个变量记录下标，交换的是 l 和 r 上的数据；
最后才将 meeti 和 keyi 上的数据交换；
而挖坑法则是先用一个变量key记录基准值；
然后用 一个变量 pit 记录 key的下标作为坑位；
然后 r 从右往左找比 key 小的数，找到了就将这个数据和 pit 上的数据交换，pit 更新；
然后 l 从左往右找比 key 大的数，然后执行相同的操作；
它的代码相较于Hoare法更加简单，细节方面更少，也对新手更为友好：
int PartSort2(int* a, int l, int r)
{
int mid = GetMid(a, l, r);
Swap(&a[l], &a[mid]);
int key = a[l];
int pit = l;
while (l < r)
{
while (a[r] >= key&&l<r)
r--;
a[pit] = a[r];
pit = r;
while (a[l] <= key&&l<r)
l++;
a[pit] = a[l];
pit = l;
}
a[pit] = key;
return pit;
}
void QuickSort(int* a, int begin, int end)
{
if (begin > end)
{
return;
}
if (end - begin <= 8)//小区间优化
{
InsertSort(a + begin, end - begin + 1);
}
int l = begin;
int r = end;
int keyi = PartSort2(a, l, r);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}前后指针法
最后介绍一个比较新颖的方法：前后指针法;
所谓前后指针法，它的主要思想就是在除了有一个key的基准值之外，还有两个变量用来作为指针指向数组的下标，然后根据数据大小和指针的变化来进行操作，我们先看下一个动图来深入理解下
通过动图，我们发现前后指针法的主要算法有以下几个点：
1. cur指向的数据比key小的时候，cur和prev是先后向后走；
2. cur指向的数据比key大的时候，cur走prev不走；
3. 当prev和cur之间的差距大于1的时候，prev和cur的数据交换；
4. cur脱离数据后，将key和prev交换；
当了解后我们再来看看代码：
int PartSort3(int* a, int l, int r)
{
int mid = GetMid(a, l, r);
Swap(&a[l], &a[mid]);
int key = a[l];
int prev = l;
int cur = prev + 1;
while (cur <= r)
{
//碰到小的就停下
if (a[cur] < key && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[l], &a[prev]);
return prev;
}
void QuickSort(int* a, int begin, int end)
{
if (begin > end)
{
return;
}
if (end - begin <= 8)//小区间优化
{
InsertSort(a + begin, end - begin + 1);
}
int l = begin;
int r = end;
int keyi = PartSort3(a, l, r);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
前后指针的思想较挖坑法较为晦涩难懂，但是也是十分重要的。
快速排序的非递归
在前面三种方法中，我们都是利用递归来实现快速排序的；
但是当快速排序使用在那种比较有序的数据中的时候，会有爆栈的风险；
因为快速排序每一套排序都会将key上的值放在它应在的地方；
若是数据有序，那么key值就会在靠后的位置，而左边递归可能会比较深；
若是左边数据过多，一直向左边递归，那么栈就可能过深；
因此我们需要学会非递归的快速排序；
那么非递归的快速排序是怎么实现呢？
既然编译器的栈区自己会炸，那我们就自己开辟一个栈用来放数据麻~
此时一个突击检查！
动态开辟的空间在哪里？
既然我们自己开辟了一个栈，那我们就按照快速排序递归的逻辑；
来将左右边界一个个压栈，然后用的时候再拿出来不久好了？
那么快速排序递归的逻辑是什么呢？
自然是每次都将key-1，key+1，begin，end之类的按顺序压栈了呀；
至于这个顺序，自然是看你内部怎么写的就怎么压了；
代码如下：
void QuickSortNonR(int* a, int l, int r)
{
STK st;
StackInit(&st);
StackPush(&st, l);//将左右区间分别入栈
StackPush(&st, r);
while (StackEmpty(&st))
{
int end = StackTop(&st);//先拿右
StackPop(&st);
int begin = StackTop(&st);//后拿左
StackPop(&st);
int keyi = PartSort3(a, begin, end);//一套排序后将keyi拿到手
if (begin < keyi - 1)//若是大于等于则说明已经排完左边了
{
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
if(keyi+1<end) //若是大于等于则说明已经排完右边了
{
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
}
StackDestroy(&st);
}
这些前缀是Stack的函数在我之前的博客(118条消息) 栈和队列的基本操作_一般路过半缘君的博客-CSDN博客
写过，有兴趣的可以看看（球球惹）
归并排序
归并排序是个很神奇的排序；
它的核心思想是利用分治法，将一个数组不断划分为左右两侧的小数组，然后使得小数组内部有序之后，再归并，并且使得合并后的大数组也是整体有序；
这么说可能有点抽象，那么我们先看看动画来深入理解归并排序；
看了动画我们来整理下归并排序的特点：
1. 将数组不断划分，直到只剩最后两个数据，使得两个数据内部有序后，再和其它数据归并
2. 存储数据的方法是用另一个数组来接收数据，然后在原数组对应位置将有序数据覆盖上去
递归实现
首先我们用递归来实现归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)//递归的终止条件
{
return;
}
int mid = (begin + end) / 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;//要在tmp相应的位置将数据放进去
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;
tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
}
首先是第一个难点
首先我们需要不断向左递归，若是递归到只有一个数据，则说明内部已经有序，返回上一层递归；
就像这张图，我们首先会递归到只有一个数据的时候，而一个数的时候自身内部有序；
而内部有一个以上的数据的时候，就会进行下面的排序代码；
这里是将 左边的数据和右边的数据按大小依次放入tmp数组的对应位置中；
全部放入之后，再将数据覆盖到 a 数组的对应位置中；
就像上图一样，将数据在tmp中排好序，然后再拷贝进去；
而归并就是指两边的数据依次排好序放入tmp中的过程；
而当我们对全体数据进行一次归并，就完成了排序；
就像二叉树一样，先递归到底层，再依次返回，返回的途中顺便排好序；
非递归实现
非递归实现需要在意的细节就比较多；
首先是如何模仿递归；
递归时虽然会一直递归到最底层，但是实际上有效的是从倒数第二层才开始的；
而递归倒数第二层则是一组两个数据，那我们可以利用一个变量 gap，将数据分成两个一组；
但是非递归既然是非递归，那么就和递归有不一样的地方；
首先一个不一样的地方是：非递归是将一组数据分为两个两个一组，然后全部都排好序；
而递归是将 两组有两个数据的数组排好序后，再将这两组数据合并成一个有四个数据的数组；
然后再将另外一边给排好序之后，再归并成一组；
而非递归要一次性将分好组的数据全部排好，就应该用一套循环控制；
而且还有一个就是，有时候数据个数并不是偶数，按照递归那一套一定会出错；
比如越界访问之类的，那我们就要对变量等进行操作；
接下来我们看代码
void _MergeSortNonR(int* a, int begin, int end, int* tmp)
{
int gap = 1;
while (gap <= end)
{
for (int j = 0; j <= end; j += 2 * gap)
{
int begin1 = j, end1 = j + gap - 1;
int begin2 = j + gap, end2 = j + 2 * gap - 1;
int i = j;//要在tmp相应的位置将数据放进去
if (end1 > end)
{
break;
}
if (begin2 > end)
{
break;
}
if (end2 > end)
{
end2 = end;
}
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 + j, tmp + j, sizeof(int) * (end2 - j + 1));
}
gap *= 2;
}
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc,fail");
return;
}
_MergeSortNonR(a, 0, n - 1, tmp);
}
首先利用gap和内层循环，来将分好组的数据排好序；
而外层循环则是用来模拟归并过程；
当gap == end 时，就说明已经全部排好序了；
而这里则是控制这几个指向下标的变量，防止越界访问；
但是为什么这里只有 end2 需要修改呢？
我们先把这几串代码屏蔽一下，添上这句代码：
首先我们设置数据为2的次方倍
我们可以看到，没有一个越界访问；
然后我们加一个数据，再看看；
我们发现第一次是 end2 和 begin2 越界；
再加一个数据；
我们发现，越界归并到最后一组，只有end2 会越界，而前面则不一样，各有越界；
因此，我们对 end1 ，begin2 和end2 进行处理的时候，只用对end2 的数据进行修改就行，因为若是只有end2越界，那么一定就是到了最后一次归并；
因此处理数据时只要对end2修改就行；
总结
在了解各种数据后，我们针对每个排序的时间复杂度和空间复杂度，以及稳定性来画出一个表格；
在此之前，我们先来了解下稳定性是什么；
稳定性
相同的数据在排完序后，先后顺序不变，则具有稳定性；
| 排序 | 时间复杂度 | 空间复杂度 | 稳定性 |
| 直接插入排序 | O(N*N) | O(1) | √ |
| 希尔排序 | O(N^ 1.3) | O(1) | × |
| 选择排序 | O(N*N) | O(1) | × |
| 堆排序 | O(N*log2N) | O(1) | × |
| 冒泡排序 | O(N*N) | O(1) | √ |
| 快速排序 | O(N*log2N) | O(log2N) | × |
| 归并排序 | O(N*log2N) | O(N) | √ |
以上就是个人的全部见解；