🥰作者: FlashRider
🌏专栏: 初阶数据结构
🍖知识概要：详解八大排序的原理、时间复杂度分析、以及代码实现。
目录
八大排序
插入排序
直接插入排序
希尔插入排序
选择排序
冒泡排序
计数排序
堆排序
快速排序
霍尔法
挖坑法
前后指针法及优化快排
归并排序
八大排序
八大排序分别是：插入排序、希尔排序、选择排序、冒泡排序、快速排序、归并排序、计数排序以及堆排序。
我们很多算法和数据结构的实现都离不开排序，也有很多实际应用离不开排序，如何去选择一个合适的排序是我们需要熟知并掌握的知识。
插入排序
直接插入排序
假设我们有一个已经有序的序列，那么新插入的数只需要和序列中的数依次比较，找到合适的位置插入即可。
那么对于一个待排序的序列，我们只需要遍历这个数列，将每一个数当作新插入的数，插入到之前已经有序的序列中即可（第一个数插入到空序列，空序列必定有序）。
过程如下：
void InsertSort(int* a, int n)
{
for(int i = 1; i < n; i++)
{
int end = i-1;
int tmp = a[i];
while(end >= 0)
{
if(a[end] > tmp)
{
a[end+1] = a[end];
end--;
}
else break;
}
a[end+1] = tmp;
}
}希尔插入排序
从上方插入排序的过程可以看出来，如果待排序的序列是有序或者接近有序的时候，我们的每次插入都只需要遍历寥寥几个数，希尔排序的思路就是，利用步长把一个序列排为接近有序，逐步将步长缩短，这样能优化插入排序的效率。
void ShellSort(int* a, int n)
{
for(int j = 0; j < gap; j++)//分为gap组数据 分别进行插入排序
{
for(int i = j; i < n - gap; i += gap)//插入排序逻辑
{
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;
}
}
}选择排序
对于一个待排序的序列，我们选择其中的最小值，和第一个位置的数交换，再选择次小值，和第二个位置的数交换，以此类推......
最后就能得到一个升序的序列。（降序同理）
void SelectSort(int* a, int n)//同时选择最大值和最小值，可以提高小部分效率
{
int begin = 0, end = n - 1;
while(begin < end)
{
int maxi = begin, mini = begin;
for(int i = 0; i < n; i++)
{
if(a[maxi] < a[i]) maxi = i;
if(a[mini] > a[i]) mini = i;
}
Swap(a[mini], a[begin]);
if(maxi == begin) maxi = mini;//修正
Swap(a[maxi], a[end])
begin++, end--;
}
}冒泡排序
冒泡排序的主要思想就是相邻交换，比如我要将一个序列变成升序序列，一个数比右边的数大，那么他就要和右边的数进行交换，这样不断交换下去，一趟遍历的交换就能把最大的值放在倒数第一位，第二趟遍历就可以把第二大的值放在倒数第二位，以此类推。
当某一次遍历所有数后也没发生交换，代表已经有序，就可以退出排序了。
void BubbleSort(int* a, int n)
{
for(int j = 0; j < n; j++)//确定n个数的位置
{
int exchange = 0;//是否发生交换
for(int i = 1; i < n - j; i++)
{
if(a[i - 1] > a[i])
{
Swap(a[i - 1], a[i]);
exchange = 1;
}
}
if(exchange == 0) break;
}
}计数排序
我们开一个数组全部初始化为0，下标对应数字，来统计每个数出现的次数，从小到大遍历数组，把出现过的数依次拿出来即可。
步骤如下：
1. 统计数字出现的次数
2. 按照次数有序归回原数组
局限性：浮点数与字符串无法排序。耗费大量空间。
void CountSort(int* a, int n)
{
int max = a[0], min = a[0];
for(int i = 0; i < n; i++)
{
if(a[i] > max) max = a[i];
if(a[i] < min) min = a[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
memset(count, 0, sizeof(int) * range);
//统计
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;
}
}
}堆排序
堆排序有两种方式，一种是将一个序列建成堆，再不断打印堆顶元素并pop，就能满足有序，但实际上这个序列本身是堆，而非有序序列，只是打印的时候有序罢了。
这里推荐第二种方式，直接将一个待排序序列建堆，比如我们建大堆，这样堆顶就是最大的元素，让堆顶和堆尾进行swap，再将堆的size减少1，这样不断做下去就能得到有序序列。
void HeapSort(int* a, int n)
{
int i;
//向下调整建堆
for(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--;
}
//最后数组里的数将会是降序 大~小
}快速排序
霍尔法
快排的思想主要是选择一个key作为关键值，我们让比key小的数都在key左边，比key大的都跑去key右边，再将左右两个区间递归进行此过程即可。
每一次过程有两个指针left和right，当left遇到比key大的数停下，right遇到比key小的停下。
最后left和right的位置相互交换即可。
当left和right相遇时，用key和它们的位置交换，就能保证key左比key小，key右比key大。
void QuickSort(int* a, int begin, int end)
//快排 霍尔版 不需要考虑边界问题 用key做了下标 不需要考虑key本身的位置
{
if(begin >= end) return;//保证区间存在
int left = begin, right = end;
int key = left; //left为key right先走 保证交换key后永远左边最小右边最大
while(left < right)
{
while(left < right && a[right] >= a[key]) right--;
while(left < right && a[left] <= a[key]) left++;
Swap(a[left], a[right]);
}
Swap(a[left], a[key]);
key = left;//修正key
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}挖坑法
挖坑法就是把key的位置挖一个坑（未填充数字），不再是交换left和right了，而是将满足条件的数填充到坑中，并把它原本所在的位置当作新的坑。
void QuickSort(int* a, int begin, int end)
{
if(begin >= end) return;
int left = begin, right = end;
int key = a[left];
int pit = left;
while(left < right)
{
while(left < right && a[right] >= key) right--;
a[pit] = a[right];
pit = right;
while(left < right && a[left] <= key) left++;
a[pit] = a[left];
pit = left;
}
a[pit] = key;
QuickSort(a, begin, pit - 1);
QuickSort(a, pit + 1, end);
}前后指针法及优化快排
两个指针，cur指向的数如果大于了key，那么cur++。
一旦当cur小于了key，那么让cur和prev指向的数交换，并且cur++，prev++。
这样就能保证比key小的数都交换到前面去了。
快排优化：
快速排序的过程里面最蛋疼的一点就是，当你还剩一小部分元素的时候，它依然会去递归，开辟函数栈帧，这样消耗的资源其实远远大于直接将这部分元素排序的资源的。
所以我们当排序元素剩下一小部分的时候，就直接用插入排序（因为插入排序效率算比较高的了）进行排序即可。
void QuickSort(int* a, int begin, int end)
{
if(begin >= end) return;
int prev = begin, cur = begin + 1;
int key = begin;
while(cur <= end)
{
if(a[cur] < a[key] && ++prev != cur)
Swap(a[cur], a[prev]);
cur++;
}
//递归优化
if(end - begin > 10)
{
Swap(a[prev], a[key]);
key = prev;
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}
else InsertSort(a+begin, end - begin + 1);
}归并排序
首先我们要知道，如何将两个有序序列合并为一个新的有序序列。
其实很简单，我们将两个序列当前遍历到的数比完大小一个个摘下来放到新序列中即可。
那么一个待排序的序列，我们把不断对半对半分下去，最后序列会被分为一个个单独的数，那么对于单独的数来说，它本身就是一个有序序列，这样我们就可以使用上面的方法去排序了。
void _MergeSort(int* a, int begin, int end, int* tmp)
{
//递归条件
if(begin >= end) return;
int mid = begin + end >> 1;
//划分区间
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//归并
int k = begin;
int l1 = begin, r1 = mid;
int l2 = mid + 1, r2 = end;
while(l1 <= r1 && l2 <= r2)
{
if(a[l1] < a[l2])
{
tmp[k++] = a[l1];
l1++;
}
else
{
tmp[k++] = a[l2];
l2++;
}
}
while(l1 <= r1)
{
tmp[k++] = a[l1];
l1++;
}
while(l2 <= r2)
{
tmp[k++] = a[l2];
l2++;
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n-1, tmp);
free(tmp);
}
