现在我们一起分析一下排序算法
在初级数据结构中，有着以下几种排序算法：
首先我们介绍一下插入排序：
1. 插入排序
1.1 直接插入排序
直接插入排序，顾名思义，他就是先从前到后找到一个比前面数字小的数字，然后拿起他，然后将他插入前面的数据当中，使这些数据暂时有序。咱们玩的斗地主的插牌原则底层就是直接插入排序的逻辑。
在这里，我们先给上一组数据。
int arr[] = {5,3,6,9,4,0,2,1,7,8};5 3 6 9 4 0 2 1 7 8。
我们讲一下思路，怎么样可以将这对数据按照扑克牌的思路捋顺呢？
首先，我们要定义一个指针叫end，这个指针就像是我们的右手，他要从头一直往后遍历，看看哪一个数据比前面的大。然后我们还要定义一个指针叫做tmp，这个指针要提前将前面可能会改变的数据提前保存好。然后定义一个begin指针，表示一个正在作为基准比较大小的数字。但是begin可以不用定义，直接用循环里面的i来表示就可以了。
具体的函数操作步骤如下：
首先，上传待排数据arr指针和数组的元素个数n。然后先用一个for循环中的i表示要比较的元素的下标，然后end指针和指向下标为i的元素，tmp始终保存arr[end+1]这个数据，如果end指针指向的元素大于tmp，那就直接让arr[end+1]=arr[end]，不用担心end+1原本指向的元素会被覆盖，因为tmp已经将这个数据保存起来了。然后让end--，如果arr[end]小于tmp了或者end指针出界了小于零了，就让arr[end+1]=tmp，然后i++，继续重复上面的过程。注意for循环的限制条件是i<n-1，因为要保证tmp保存的数据不能出界。
要定义的指针变量：end指向i
要定义的非指针变量：tmp指向arr[end+1]这个数据
过程：i for循环，arr[end]与tmp比，end--到arr[end]<tmp或者end<0后arr[end+1]=tmp，重复for循环。(简短版本，细节见上)
实现代码如下：
void InsertSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}我们看这个代码，如果n趋于无限个并且全部为逆序的话，end每一次都要从i重新遍历到第一个，因为整个数组右边的数字普遍偏大，左边的数字普遍偏小，这个代码的时间复杂度最差的时候就为O(n方)。
1.2 希尔排序
为了解决上面数组左边数据普遍偏大，右边数字普遍偏小的情况，我们有一个希尔排序的方法：
希尔排序的方法是：将整个数组分为2个或者3个或者4个...为一组，将每一组的第一个数据进行直接排序的方法进行排序，然后将每一组的第二个、第三个等都进行直接插入的方法进行排序。
上面的操作叫做预排序，当gap=1的时候为直接插入排序。
即将上面的直接排序方法的间隔个数1改成了gap个，一般来说，gap最开始等于n，然后gap=gap/3+1;然后一直循环，加1就是为了让gap最后等于1，可以变成直接的插入排序，最后退出外循环。
代码实现如下：
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)//防止gap等于1的时候此时数组已经有序了，但是又进入循环，进入死循环。
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)//就像上面的n-1一样，防止tmp取值的时候出gap这个界限
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}希尔排序的作用就是让原来的数据左边的数据为偏小的数据，右边的数据为偏大的数据，这样子的话就防止直接插入排序的时候会遇见时间复杂度过大的情况。
那希尔排序的时间复杂度为多少呢？
假设最开始一共有n个元素，由上面的分析可得gap为分开的组数，那么每一组元素的个数就为n/gap，那么最差的情况，即这n/gap个元素全部都是逆序的元素，那么这一次的比较需要的时间复杂度就是1+2+3+...+(n/gap-1)，一共有gap组，所以需要的时间复杂度就是[1+2+3+...+(n/gap-1)]*gap，我们现在列一下gap的取值，一般都是n/3
当gap越来越小，等于1的时候，这个时候的数组已经大致有序了，所以肯定不存在最差的情况，这个时候的消耗为O(n)。
从O(n)到O(4n)....到O(N)，中间一定有一个最高点，通过大量的实验，大概估计这个值为O(n的1.3次方)，这个具体的值目前还没有确定下来。
2. 选择排序
2.1 直接选择排序
直接选择排序有一个最初的版本，他的排序原则如下：
先定义一个mini指针指向第一个元素，然后往后遍历数组中最小的数，然后把下标赋给mini，遍历完成后mini与第一个元素交换，然后i++，直到i出界。
根据这个思路，我们不难写出代码：
//直接选择排序
void SelectSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
int mini = i;
//找最小的数字
for (int j = i+1; j < n; j++)
{
if (arr[j] < arr[mini])
{
mini = j;
}
}
swap(&arr[mini], &arr[i]);
}
}
但是我们来看，这个代码的时间复杂度很容易达到O(n方)。
所以我们有一个有一个优化版本的直接选择排序，他的思路如下：
1.先定义好begin和end指针指向数组的头和尾。定义min和max指针指向begin。
2.找begin+1和end区间的最大值和最小值，在这个过程中用i来遍历，找到以后将最大值和end交换，将最最小值和begin交换。然后end--，begin++，重复上述过程
根据这个思路，我们可以尝试着写出代码：
//直接选择排序2
void SelectSort2(int* arr, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int min = begin;
int max = begin;
for (int i = begin+1; i <= end; i++)
{
if (arr[i] > arr[max])
{
max = i;
}
if (arr[i] < arr[min])
{
min = i;
}
}
if (begin == max)
{
max = min;
}
swap(&arr[min], &arr[begin]);
swap(&arr[max], &arr[end]);
end--;
begin++;
}
}其中，这一段代码要注意一下：
if (begin == max)
{
max = min;
}
swap(&arr[min], &arr[begin]);
swap(&arr[max], &arr[end]);
因为有可能begin所在的位置就是最大值的位置，如果直接就先让mini和begin进行交换的话，就会导致原本的最大的数据被覆盖，等max再和end交换的时候，就会导致end的为止也为最小值。相反也是一样，如果后面先交换的是max和end，就要先写上下面的这个条件：
if (end == min)
{
min=max;
}
2.2 堆排序
堆排序在之前分析堆的应用的时候有讲过，感兴趣的朋友可以自行翻看。
3. 交换排序
3.1 冒泡排序
冒泡排序是一个基础排序，这里附上冒泡排序的代码：
//冒泡排序
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int exchange = 0;//加上exchange过后，如确定有序，i就不用变了，不加的话，下面的for循环已经遍历过一次确定有序了，i还得++继续遍历
for (int j = 0; j < n - i - 1; j++)
{
//排升序：arr[j] > arr[j + 1]
//排降序：arr[j] < arr[j + 1]
if (arr[j] > arr[j + 1])
{
exchange = 1;
int tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
if (exchange == 0)
break;
}
}我们主要来探讨快速排序。
3.2 快速排序
快速排序是Hoare提出的一种二叉树结构的交换方法。其基本思想为：任取待排序元素序列中的某元素作为基准值，按照一个方法将基准值放在数组中的一个地方，使得数组的左边小于基准值，右边大于基准值，然后再将左右边的数组按照同样的方法找到基准值，再将它进行分割，直到所有的数列都排列好为止。
其基本框架如下：
//快排的基本框架：
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = _QuickSort(arr, left, right);
//排左边
QuickSort(arr, left, keyi-1);
//排右边
QuickSort(arr, keyi+1, right);
}这里有一个找基准值的方法函数：_QuickSort(arr, left, right)。
实现这个函数有以下的方法：
3.2.1 hoare版本
现在可以探索一下hoare版本寻找基准值的方法：
1.在数组中定义left是下标为零的位置，定义keyi在left所在的位置，left++到1，定义right是数组最后一个元素的位置。
2.将right从右往左进行遍历，找小于keyi的值，如果没有找到就right--，如果找到了就停止遍历，换到left从左到右进行遍历，找大于keyi的值，如果没有找到就left++，如果找到了就停止遍历。
3.如果找到了，并且right比left大，就将arr[left]和arr[right]的数据进行交换，然后left++，right--，继续重复上面的过程。
4.整个过程中，如果right<left了，就要跳出循环。数据arr[keyi]与arr[right]也进行交换，此时right所在的位置就是基准值所在的位置。
5.然后在这个数组里面，将基准值左边的数组和右边的数组按照相同的方法进行基准值的判断。左边数据上传的参数left应为left，参数right应为keyi-1。右边的数据上传的参数left应为keyi+1，参数right应为right。
通过上面的描述，可以先试着写一下这个代码：
//hoare版本
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
left++;
while (left <= right)//问题4
{
//arr[right]小于或者等于arr[keyi]的话right就要停下，等待交换
while(left <= right && arr[right] > arr[keyi])//问题2和1
{
right--;
}
//arr[left]大于或者等于的arr[keyi]话left就要停下，等待交换
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
if (left <= right)//问题3
{
swap(&arr[left++], &arr[right--]);
}
}
//arr[right]和arr[keti]进行交换
swap(&arr[right], &arr[keyi]);
return right;
}四个条件
里面有四个条件值得探讨：
1. arr[right] > arr[keyi] 和 arr[left] < arr[keyi]这两个条件为什么不能是大于等于或者小于等于？即为什么二者相等的时候还要交换？
在这里我们举一个这样的例子：
若在相等的时候交换：
对半分的进行排序的时候更容易排序，在有很多重复数据的时候能够更好的将数据分开。
若相等的时候不交换：
这样子的话，若在元素大量相等的或者完全相等的时候，下一批左边没有元素，右边有n-1个，更难以排序。
综上所述，arr[right]=arr[keyi]或者arr[left]=arr[keyi]的时候，要交换，尽量把keyi往中间放，这样子更能更大的放大hoare版本二叉树的优势。
2. 为什么while(left <= right && arr[right] > arr[keyi])这个条件中left等于right的时候不跳出循环？
在这里我们也举三个例子：
若left和right的相遇点数据小于arr[keyi]，这样子即使left和right相遇后直接跳出循环没有关系。同理，若left和right的相遇点数据等于arr[keyi]，left和right相遇后直接跳出循环也没有关系。但是如果left和right的相遇点的数据大于arr[keyi]，left和right相遇后直接跳出循环，right与keyi的数据进行交换，比keyi大的right的数据到了keyi的左边，就不符合找基准值的原则了。所以left等于right的时候不能跳出循环，只有当right真真切切地在left左边的时候，right遇到的值才彻彻底底不会大于keyi，同理，只有当left真真切切地在right左边的时候，left遇到的值才彻彻底底不会小于keyi。
3. 在条件if (left <= right)中left等于right的时候left和right还要自己和自己交换？
因为如果程序走到这里是left等于right，就证明此时left和right所在位置的值是等于arr[keyi]的，因为没有一个数即比arr[keyi]大又比arr[keyi]小，如果直接跳出来的话，left就不能自加，right就不能自减，转到大循环的while(left<=right)的条件的时候，就会进行死循环。所以二者等于的时候要自己跟自己交换，是为了这个循环里面的自减自加步骤，让left和right越界。
4.while (left <= right)，在这个条件中为什么left等于right的时候还要进入大循环？
这个和第二个问题的解释一样，但是有点区别，请看下图：
在这里还是因为如果二者相遇的值大于arr[keyi]的话，跳出循环right和keyi交换的时候会导致keyi左边的值不全部小于keyi，但是这里的相遇是因为二者自加后导致的相遇，不是因为根据大小遍历得出来的相遇。所以二者在进行交换的时候，中间应该隔着一个元素，这样子的话就有这种情况发生了。
二叉树递归思想
我们来看这两个代码：
再对比一下二叉函数前序遍历的代码：
其实都是“先读取根，再读取左节点，最后读取右节点”的思想，用一个整体思想，把整个数组想成是一个根节点，然后一遍一遍的递归，再一遍一遍的返回。
当基准点递归到只有两个数据的时候，left一开始自加后left=right，如果后面的数据大于前面的数据，right--直接走到left前面，跳出循环，right自己和自己进行交换，数组有序；如果后面的数据小于前面的数据，right不懂，left++直接走到right的后面，跳出循环，right和第一个数据发生交换，数组有序。
当基准点的左或右数组只有一个数据的时候，mid+1的left一开始就等于right了，进去主实现函数的if(left>=right)的条件代码中，return。mid-1的right一开始就等于left了，进ru主实现函数的if(left>=right)的条件代码中，return。如果为空，则一开始left就大于right，也会进入主实现函数的if(left>=right)的条件代码中，return。
复杂度
找基准点就像二叉树一样，两份两份的向下递归，若设要排序的数据有n个，不难推测出递归到每段数组里面只有一个数据的时候，总共递归了log以2为底n层，可以简略成logn层。
时间复杂度：左右每递归一层，进行基准值的寻找的时候，从宏观上来说就是对这n个数据进行了一次比较，每递归一层进行n次比较，总共递归了logn层，所以消耗的时间复杂度就是O(nlogn).
空间复杂度：对于空间复杂度的定义，是对一个算法在运行过程中临时占用存储空间大小的量度。对于每次递归，每一层函数实际上定义的都是常数次的变量，可以理解为一次函数调用空间复杂度是O（1），但是每次递归下去的时候呢，因为函数栈帧是不销毁的，只有递归到n == 1的时候才开始回退销毁，所以这个最长的路径就是高度 logn，所以空间复杂度是 1 * logn，即O(logn).
3.2.2 挖坑法
现在探索一下挖坑法找基准值的方法：
1.给函数上传的形参是int* arr, int left, int right。定义一个指针为hole，首先hole先指向left，定义一个key保存最开始arr[hole]的值。
2.right从右往左找，找小于key的值，找不到就right--，如果找到了就把这个值与hole的值交换，然后hole=right，hole在right的地方成为了一个新的hole。
3.left从左往右找，找大于key的值，找不到就left++，如果找到了就把这个值与hole的值交换，然后hole=left，hole在left的地方成为了一个新的hole。一直循环直到left>right.此时将key的值赋给hole所在的数据，hole此时就是基准值keyi。
根据这个思路，尝试写一下代码：
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];//要有一个key把hole的值存起来，这是基准值
while (left < right)//问题3
{
while (left<right && arr[right] > key)//问题1和2
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}接下来继续探讨三个问题：
1.为什么循环条件while (left<right && arr[right] > key)不是left<=right?
因为这里是right到了小的数值的时候hole就过来了，left走到大的数值的时候hole就走过去了，二者相等对于hole没有影响。到达了就证明hole，left，right都在一个地方，也就证明这个地方的左边没有大于key的数，这个地方的右边也没有小于key的数，并且此时hole所在的地方是没有值存在的，需要key给它赋值，就没有hoare方法的那种相遇值大于key的情况。问题3也是一样的解释。
2.为什么循环条件while (left<right && arr[right] > key)不是arr[right] >= key?
这个就同hoare的情况了。
3.2.3 lomuto前后指针
现在探索一下lomuto前后指针找基准值的方法：
1.参数上传的是int* arr, int left, int right，定义一个pre指针指向left的位置，定义一个cur指针指向pre指针的下一个位置，定义一个keyi来保存left的值。
2.cur遍历，如果arr[cur]的值小于arr[keyi]，在pre往前走一步后和cur不相同的情况下，pre往前走一步并且与cur交换（不是赋值）。如果arr[cur]的值大于arr[keyi]，cur++。
3.注意：只要arr[cur]<arr[keyi]，不管pre++后是否与cur相等，pre都必须++
根据这个思路我们可以写一下代码：
//lomuto前后指针
int _QuickSort3(int* arr, int left, int right)
{
int pre = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
if(arr[cur] < arr[keyi] && ++pre != cur)//问题1
{
swap(&arr[cur], &arr[pre]);
}
cur++;
}
swap(&arr[pre], &arr[keyi]);
return pre;
}这里有一个问题：为什么arr[cur]=arr[keyi]的时候不进行交换？
其实等不等于都无所谓，因为如果全部都是相同的数据的话，若相等进行交换，pre最后会在最后一个，若不交换，pre最后会在第一个，对于下一次找基准点二者都没有什么优化，所以加不加等于都行。
3.2.4 非递归版本
非递归版本的快速排序方法需要借助一个数据结构：栈。
具体的实现方法如下：
1.上传的参数依然是int* arr, int left, int right.首先先定义一个栈ST st，然后初始化一下。
2.将left和right的值放进栈里面，先放right再放left，因为栈是先进后出的结构，要确保后面取栈顶元素的时候先拿的就是left的位置，第二次拿的就是right的位置。
3.取两次栈顶元素，第一次取出来的值作为left，第二次取出来的值作为right，并删除掉这两个元素。进行找基准值的操作，用上面的lomuto指针的方法找到基准值keyi后，将keti-1作为right，和left依次放入栈中，重复上述过程，先继续找左边的。
4.当left=right的时候，停止放元素。然后将keyi+1作为left，和right依次放入栈中，重复上述过程，继续找右边的。
根据这个思路我们可以写一下实现代码：
//非递归版本需要的栈的结构：
typedef struct Stack {
int* arr;
int size;
int capacity;
}ST;
//栈的初始化
void STInit(ST* pst)
{
//不用传**ppst，改st里面的内容就只用传st的地址就好了
assert(pst);
pst->arr = NULL;
pst->capacity = pst->size = 0;
}
//往栈里插入元素
void STPush(ST* pst, int x)
{
assert(pst);
//增容
if (pst->capacity == pst->size)
{
int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
int* tmp = (int*)realloc(pst->arr, sizeof(int) * newcapacity);
if (tmp == NULL)
{
perror("relloc fail!");
exit(1);
}
pst->arr = tmp;
pst->capacity = newcapacity;
}
pst->arr[pst->size] = x;
pst->size++;
}
//去栈顶元素
int STTop(ST* pst)
{
assert(pst&&pst->size);
return pst->arr[pst->size - 1];
}
//删除栈里的元素
void STPop(ST* pst)
{
assert(pst&&pst->size);
pst->size--;
}
//判断栈里面是否为空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->size == 0;
}
//销毁栈
void STDestouy(ST* pst)
{
assert(pst);
if (pst->arr)
free(pst->arr);
pst->arr = NULL;
pst->capacity = pst->size = 0;
}
//非递归版本
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
//取栈顶元素作为遍历数组的头和尾
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
//进行lomuto的操作找基准值
int pre = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
//如果arr[pre]>arr[cur],pre往后走一步后二者交换，cur++
if (arr[keyi] > arr[cur] && ++pre != cur)
{
swap(&arr[pre], &arr[cur]);
}
cur++;
}
swap(&arr[pre], &arr[keyi]);
keyi = pre;
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, begin + 1);
}
if (keyi - 1 > begin)
{
STPush(&st, keyi-1);
STPush(&st, begin);
}
}
}这里为什么if (keyi + 1 < end)和if(keyi - 1 > left)中不用等于？
因为当keyi+1=end或者keyi-1=left的时候，右边或者左边已经只有一个数据了，这种情况下没有入栈的必要了。
4. 归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。主要是是将已经有序的数列进行合并，得到一个完全有序的数列。即先将每一个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路合并。
具体步骤如下：
1.参数上传的是int* arr, int left, int right, int* tmp，先找到待排序数据中的mid位置，然后递归的找下去，每一层都是要先找完左边再找右边。
2.找到只剩下一个数据的时候，与其另一边的数据进行两个有序数组合并成一个有序数组的操作，再一层一层的递归上去。
3. 把合并的数组递归回去后，成为上一个数组的左边部分的返回，继续与上一个数组的右边进行比较，直到把所有的数据排成有序的为止。
注意：这个实在原来的数组下标的基础上进行一部分一部分的排序，所以需要一个临时的数组来保存已经排序好的数据，这样子才可以将排好的数据转移到原来的数组中。
根据上面的分析，我们可以得到下面的代码：
//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//进行该数组的左边两边合并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;//随时做好数据更新的准备
//左右两个数组都不越界的时候
while (begin1 <= end1 && begin2 <= end2)//要加上等于，因为比较的是begin位置的数据，begin走到end的时候end的数据也要进行比较
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
//判断哪个没越界，就把哪个给放在tmp接下来的数组位置上
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
//将tmp数组里面的元素转到arr数组里面
for (int i = left; i <= right; i++)//要写left，因为如果排序右边的数据的话，left是数组里面中间的元素，保存的时候自然也应该保存到中间的位置
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail!");
exit(1);
}
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}这里要注意：for (int i = left; i <= right; i++)，因为在覆盖数据的时候，right的位置也要覆盖上。
在这里，时间复杂度：O(nlogn)，解释和上面快速排序找基准值的解释一样。而空间复杂度为O(n)，因为自始至终都是在arr本身进行数据交换，新开辟的空间tmp也是n个大小，所以为O(n)。
以上就是排序方法的所有内容。
