前言
在练习编程或者做项目时，是否经常与排序打交道，这篇文章会带你熟悉常见的八大排序。
目录
插入排序
对于要插入的一个数字，等待被插入数字的数组中是已经有序的，此时如果要插入一个数，就与有序数组中最后一个、倒数第二个......依次比较，直到此数字刚好位于前方数字小于它，后方数字大于它的位置，此时这个数字就被插入成功。依次插入剩下的数字重复上述步骤。?
?函数实现：?
void InsertSort(int* a, int n)
{
//由第一个元素作为一个有序数组依次将第二个、第三个......插入进去
for (int i = 0; i < n-1; i++)
{
int end = i;
//将待插入的按照规则进行比较，插入到正确位置
while (end >= 0)
{
if (a[end] > a[end + 1])//如果大于比较元素则交换数值
{
swap(&a[end], &a[end + 1]);
end--;
}
else//否则就意味着已经插入到了正确位置跳出循环
{
break;
}
}
}
}数组越接近有序排序算法效率越高
最坏时间复杂度为：O(N^2)，数组为逆序或者接近逆序时(一共需要比较1+2+...+n-1次)
最好时间复杂度为：O(N)，数组为有序或者接近有序时(一共需要比较n次)
空间复杂度为：O(1)
稳定性：稳定
希尔排序
希尔排序又称缩小增量法排序，先选定一个整数gap，将待排序数组分为gap个组，每个组的相邻元素下标相差gap，将每一组进行插入排序。然后再重复上述步骤，将gap值依次缩小，当gap为1时数组就被排好序了。
函数实现：?
void ShellSort(int* a, int n)
{
int gap = n;
//方法一：一组一组进行排序，排好一组再排下一组，一个一个来
while (gap > 1)
{
gap = gap / 3 + 1;//gap依次减少直到1
for (int i = 0; i < gap; i++)//将数组分为gap组
{
for (int j = i; j < n - gap; j += gap)//对每一组进行插入排序
{
int end = j;
while (end >= i)
{
if (a[end] > a[end + gap])
{
swap(&a[end], &a[end + gap]);
end -= gap;
}
else
{
break;
}
}
}
}
}
//方法2：对每一组对应的位置先进行排序，再对下一个位置都进行排序，齐头并进
//while (gap > 1)
//{
// gap = gap / 3 + 1;
// for (int j = 0; j < n - gap; j++)//j不再是+=上gap步，注意齐头并进
// {
// int end = j;
// while (end >= 0)
// {
// if (a[end] > a[end + gap])
// {
// swap(&a[end], &a[end + gap]);
// end -= gap;
// }
// else
// {
// break;
// }
// }
// }
//}
}?这里gap每次减少，可以选择gap/=2，也可以为gap=gap/3+1
因为希尔排序的分析是一个复杂问题，时间复杂度涉及到数学上尚未解决的难题，所以经过某些人的统计与计算我们时间复杂度暂且按O(N^1.25)到O(1.6*N^1.25)来算
稳定度：不稳定
选择排序
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。在待排序元素集合中如果最大或最小的元素不在第一位，则交换数据，排好一个后，下一次待排元素集合应出去排好的元素，重复上述步骤，直到剩下一个元素。
?
但是我们不妨思考一下，此时是否可以再优化排序方式，这里针对升序来讲，既然遍历一遍选择出最小的数交换到最前面，那么我们是否也可同时选出最大的数放在最后面？上代码！
函数实现：?
void SelectSort(int* a, int n)
{
//定义两个下标，一个记录当前最左边下标，一个记录当前最右边下标
int end = n - 1;
int begin = 0;
while (begin < end)
{
//定义两个变量一个找出待排序数组的最大值对应的下标max和最小值对应的下标min
int min = begin;
int max = begin;
for (int i = begin+1; i <= end; i++)
{
if (a[min] > a[i])
{
min = i;//最大值对应的下标
}
if (a[max] < a[i])
{
max = i;//最小值对应的下标
}
}
//找到后将最小值与待排数组最左边元素进行交换，最大值与最右边元素进行交换
//但是！如果最大值就在最左边，先将最小值与最左边交换，最大值就不再是原来的位置了
//就被交换到了交换前最小值所在的下标处了，所以我们要修正最大值下标为min
swap(&a[min], &a[begin]);
if (max == begin)//修正最大值
{
max = min;
}
swap(&a[max], &a[end]);
begin++;
end--;
}
}时间复杂度： O(N^2)最好情况与最坏情况一样
空间复杂度：O(1)
稳定性：不稳定
在实际中选择排序好理解，但是由于它的效率太低，不常使用
堆排序
所谓堆排序，就是利用数据结构中堆的特点性质来进行排序。在排序前我们应该先建立堆，对于升序要建立大根堆，而降序则要建立小根堆，因为这样对于后面数据排序处理会非常简单。
?建立大根堆利用向下调整算法来建立。
建立好大根堆后将大根堆最上面的一个数与最后一个数交换，此时将最后一个数映射在数组中的下标减去一。再对交换后最上面的数进行向下调整算法，使得第二大的数位于堆顶，再将下标减去一后的最后一个元素与堆顶元素交换重复上述步骤，就可依次将数据由大到小从数据的末尾往前排。
函数实现：
//因为要排升序，向下调整法来建立大根堆
void AdjustDown(int* a, int n, int parent)//向下调整法的条件是左右子树必须为大根堆或小根堆
{
//因为要建立升序，所以向下调整算法里应该将左右孩子里最大的那一个与父母交换，利用parent
//与child的关系来进行递推，当算出下标child大于数组的个数n时则一次调整结束
int child = parent * 2 + 1;
while (child < n)
{
//当右孩子存在，并且左孩子小于右孩子，要将child++
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
//当parent小于child时，要满足建立大根堆，将大的那个数往上去置换
if (a[parent] < a[child])
{
swap(&a[parent], &a[child]);
}
//当不用进行交换时则代表一次调整好了
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
void HeapSort(int* a, int n)
{
//要排升序先建立大根堆
//从最后一个元素的长辈系元素开始向下调整，当来到第一个元素时大根堆已经建立好了
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//开始排序
//循环n-1次第k次将第一个元素与第n-k+1个元素进行交换，同时参与下次调整的元素个数为前n-k个
//再对交换到第一个元素位置的数据向下调整
for (int j = n - 1; j > 0; j--)
{
swap(&a[0], &a[j]);
AdjustDown(a, j, 0);
}
}?时间复杂度：O(N*logN)因为在建立大根堆时，由最后一个元素的长辈系元素往上直到第一个元素都要进行近似logN次交换，在排序时每个元素都要向下调整一次，每次向下调整近似进行logN次交换。
空间复杂度：O(1)
稳定度：不稳定
冒泡排序
对于一个数组，针对升序，将前一个数与后一个数比若小于后一个数，则交换，再将后一个数与后一个数的后一个数比，以此类推，当比到最后一个元素时就可以缺定最大值。此时将数组往前缩小到n-1个再重复上述步骤，直到数组缩小为2个时，排序完成。
函数实现：?
void BubbleSort(int* a, int n)
{
int flag = 0;
int end = n - 1;
while (end > 0)//循环n-1次
{
for (int i = 0; i < n - 1; i++)
{
if (a[i] > a[i + 1])//将前后两个元素比较大小大的往后交换
{
swap(&a[i], &a[i + 1]);
flag = 1;
}
}
//思考一个问题：如果数组本来就排好序了，我们还需要循环n-1次去比较吗，此时我们不妨设置
//一个变量flag若一趟排序内没有交换任何元素就可以直接rturn代表数组已经有序了
if (flag == 1)
{
return;
}
end--;
}
}?没有优化代码时时间复杂度应为O(N^2)，优化后，对于有序或接近有序时间复杂度应为
O(N)。
空间复杂度为：O(1)
稳定度：稳定
快速排序
思路：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，每一趟排序完成后都会有一个被确定在正确的位置上，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。一般基准值取首元素，如果取任意元素排序过程中会更加麻烦。快速排序，由于要对左右子序列也进行排序过程，所以我们应该利用递归思想来进行排序，类似于二叉树的前序遍历，在递归左右子树前先对根节点进行适当的操作。这里我们先对一趟排序进行处理。快速排序，最初由Hoare提出的一种排序思想，所以就有了Hoare法，陆续也有了，挖坑法，以及前后指针法。
1.Hoare法
在一趟排序前确定一个基准值为6，keyi来代表它的下标，在这里我们以升序为例，因为要排升序，所以R应该先往左边找到比基准值小的值，然后L再往右边找到比基准值大的值，都找到后交换数据，直到L与R碰面（第一种碰面方式：R往左找碰到了L停止寻找，此时L所对应的值是上一次R交换过来的值是小于基准值的。第二种：R往左找到了比基准值小的值且未与L碰面，此时L往右找，碰到了R,R的值是比基准值小的值。），碰面后，交换基准值与RL碰面位置的值，就完成了一趟排序，在左边是比基准值小的值，在右边是比基准值大的值。
函数实现：?
int Part1Sort(int* a, int left, int right)
{
//三数取中，可以暂时忽略，下面快速排序的优化部分会解释
int mid = GetMid(a, left, right);
swap(&a[left], &a[mid]);
//基准值设为排序数组第一个元素
int keyi = left;
while (left < right)//在L与R不碰面的前提下去找对应的值
{
//R找比基准值小的值
while (left < right && a[right] >= a[keyi])
{
right--;
}
//L找比基准值大的值
while (left<right && a[left] <= a[keyi])
{
left++;
}
//如果没有碰面就交换R L找到的两个值
if (left < right)
{
swap(&a[left], &a[right]);
}
}
//R L碰见的位置为meet
int meet = left;
//交换碰见位置的值与基准值
swap(&a[keyi], &a[meet]);
return meet;
}2.挖坑法?
?
也是确定一个基准值，一般以首元素为基准。以一个零时变量key来存储基准值，这样首元素所处的位置就可以当作一个待填的坑hole，同样因为要排升序，所以我们应该先让R往左找比key小的值，将其填在hole中，此时R所在的位置就成为了新的坑，然后L再往右找比key大的值往坑里填，L所在的位置就是新的坑，以此类推，R找到填坑，所在的位置变为新的坑，L找到填坑，所在位置变为新的坑......当L与R碰面时，将key值填入碰面的位置，这样一趟排序就完成了。
函数实现：
int Part2Sort(int* a, int left, int right)
{
//三数取中
int mid = GetMid(a, left, right);
swap(&a[left], &a[mid]);
//将首元素作为基准值，保存在变量key中，首元素所在的位置变为了坑用hole记录
int key = a[left];
int hole = left;
while (left < right)//碰面前进行查找
{
//在不碰面的前提下R向左找比key小的值
while (left < right && a[right] >= key)
{
right--;
}
//找到了填坑
a[hole] = a[right];
//坑的位置更新
hole = right;
//在不碰面的前提下L向右找比key大的值
while (left < right && a[left] <= key)
{
left++;
}
//找到了填坑
a[hole] = a[left];
//坑的位置更新
hole = left;
}
//碰面了，将key填入坑中
a[hole] = key;
return hole;
}3.前后指针法?
确定一个基准值下标用keyi来表示。首先，定义两个变量，一个记录比keyi对应的值小的值的位置cur，一个记录比key对应的值大的值的位置prev，prev从keyi位置出发向右寻找，cur从keyi+1的位置出发向右寻找。当cur找到后，prev开始找，如果prev++后等于cur时，cur与prev没必要交换，如果prev找到后不等于cur，则交换cur与prev对应的值，然后cur继续往右边找比基准值小的值，重复上述步骤，当cur越界时，则停止寻找。此时将prev对应的值与keyi对应的基准值交换，就完成了一趟排序。
?函数实现：
int Part3Sort(int* a, int left, int right)
{
//三数取中
int mid = GetMid(a, left, right);
swap(&a[left], &a[mid]);
//报春选择基准值
int keyi = left;
//定义prev与cur分别找比基准值大与小的值
int prev = left;
int cur = left + 1;
while (cur <= right)，当cur没越界时去找
{
当cur找到了比基准值小的值，且++prev不等于cur时交换，因为相等时没必要交换
if (a[cur] < a[keyi] && ++prev != cur)
{
swap(&a[cur], &a[prev]);
}
//交换后cur继续往后找
//注意这里没有必要对prev进行任何操作，因为在一开始prev就在cur前一个，prev与cur
//之间的值都是大于基准值的，在上面代码中++prev!=cur以及对prev进行了操作。
cur++;
}
//cur越界后，交换基准值与prev对应位置的值
swap(&a[keyi], &a[prev]);
return prev;
}实现快速排序：
?
给大家讲完了三种处理一趟排序的方法后，现在就是要对整个排序过程编写代码了。在上面的分析中，我们可以利用递归的思想去解决问题。所以在第一趟排序后，我们得到了左右两个子序列，利用二叉树的前序遍历思想来进行递归，现在就是对左子序列进行递归，每次递归，都可以获得左右两个子序列，当递归到左子序列不存在或者没有元素时也就是left>=right时就进行回归，回归到上一层后，再对右子树进行类似的递归，最后整个序列中，左子序列递归回来后，右子序列也递归回来后，整个序列就已经排好序了，看代码！
void QuickSort(int* a, int left, int right)
{
//当递归下去时序列为空或不存在时就返回
if (left>=right)
{
return;
}
//记录一趟排序后已经被确定元素的下标，排序用上面三种方法任一一种都可以
int meet = Part1Sort(a, left, right);
对左右子序列进行递归
QuickSort(a, left, meet - 1);
QuickSort(a, meet + 1, right);
}在理想情况下，每次分割处左右子序列都是二分
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
由于是利用二叉数前序遍历思想，每次递归都会创建一个函数栈帧，但是左右区间递归是占用一个空间，所以空间复杂度就是它的递归成二叉树的高度，为logN，每一层遍历都是对每个元素进行遍历，所以时间复杂度，为N*logN
快速排序的优化：?
上面所说的快速排序全都是以基准值为中间，每次被分割出来的左右子序列，近似二分，才达到了高度为logN，但是如果取得的基准值是这个数组里最小的或者最大的且数组是有序的或近似有序，此时每趟排序，并不是二分，而是每趟排序，确定了最左边或者最右边的数，往下递归，每次递归长度减一，递归的深度就变成了N了，由于每次递归会创建一个函数栈帧，如果数组的元素个数很多，可能会出现栈溢出的情况，此时我们就要进行优化，如果每趟排序前，取得的基准值为中间值，这样就可以每次达到二分，所以我们可以在确定基准值前把将要取得基准值设为数组中的中间值。此时，我们可以将数组的首元素，末尾元素，与中间位置元素进行比较，取得三个数里面的中间值，将它与首元素交换即可。所以在上面三种方法中我们都在开头进行一次三数取中。看代码！
三数取中与交换换函数：
//交换函数
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中，首元素，末尾元素，中间位置元素
int GetMid(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else
{
if (a[left] < a[right])
return right;
else
return left;
}
}
else
{
if (a[left] < a[right])
{
return left;
}
else
{
if (a[right] < a[mid])
return mid;
else
return right;
}
}
}但是，这里我们还有优化的空间，在经过三数取中的优化后，每趟排序后都近似二分，这样在递归的最后三层中，递归的次数总和竟然达到了总次数的百分之七八十，所以我们可以针对最后三层进行优化不利用递归，只需在递归前进行判断，由可知第三层递归的序列个数几乎都是小于等于8的，所以我们可以修正代码：
void QuickSort(int* a, int left, int right)
{
if (left>=right)
{
return;
}
int meet = Part1Sort(a, left, right);
if (right - left <= 8)
{
InsertSort(a + left, right - left + 1);
}
else
{
QuickSort(a, left, meet - 1);
QuickSort(a, meet + 1, right);
}
}
?当right-left<=8时直接进行插入排序，效率就提升了很大。
快速排序的非递归版本：
为什么要有非递归版本？递归版本不是已经很好了吗？事情远不止如此，如果数组中的元素足够大，大到系统已经没有位置为递归开辟函数栈帧了，所以我们就要考虑非递归版本，将它改为循环，让它存储在堆上，堆相对于栈空间大的不止一星半点！?在编写非递归版本前，需要如何将递归改为循环呢？我们就要思考，在递归过程中，函数栈帧里保存的是什么？保存的应该是数组区间，所以我们应该利用一个数据结构来模拟栈空间里保存的数据，由于递归是先递进后回归，所以我们可以考虑使用数据结构中的栈，它的一个特点就是先入后出，后入先出，就对应了后递进的先回归，话不多说，直接上代码！
//Stack.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int StackDateType;
typedef struct Stack
{
StackDateType* arr;
int top;
int capacity;
}Stack;
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDateType n);
void StackPop(Stack* ps);
bool StackEmpty(Stack* ps);
StackDateType StackTop(Stack* ps);
int StackSize(Stack* ps);
//Stack.c
#include"Stack.h"
void StackInit(Stack* ps)
{
assert(ps);
ps->arr = NULL;
ps->capacity = 0;
ps->top = 0;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
void StackPush(Stack* ps, StackDateType n)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
StackDateType* tmp = realloc(ps->arr, newcapacity * sizeof(StackDateType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
ps->arr[ps->top] = n;
ps->top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
StackDateType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
//上面是数据结构中我们自己写出的栈
//非递归版本的实现
void QuickSortNonR(int* a, int left, int right)
{
Stack s;
StackInit(&s);
//将原始数组的区间压入栈中，先压区间左，后压区间右
StackPush(&s, left);
StackPush(&s, right);
while (!StackEmpty(&s))//当栈里没有区间的时候即排序完成
{
//取出栈中一个区间的元素，获得区间后弹出区间
int end = StackTop(&s);
StackPop(&s);
int begin = StackTop(&s);
StackPop(&s);
//进行一趟排序得到确定的元素位置mid
int mid = Part1Sort(a, begin, end);
//如果被mid分成的序列存在且不止一个元素，就将其区间压入栈内，这里我们还是以二叉树前序
//遍历的思想，因为是先递归左边后递归右边，所以要先压入右区间，后压入左区间。
if (mid + 1 < end)
{
StackPush(&s, mid + 1);
StackPush(&s, end);
}
if (begin < mid - 1)
{
StackPush(&s, begin);
StackPush(&s, mid - 1);
}
}
StackDestroy(&s);
}巧妙地利用数据结构栈的特点，将数据建立在堆区上！?
归并排序
?归并排序的思想：将左右两个有序序列合并成一个有序序列，我们需要做的就是怎么使两个序列有序，递归就可以很好解决，归并排序，相对于快速排序，用的是二叉树后序遍历的思想，当递归到最深处时，左右序列中只有一个数时，就可以默认它是有序的，此时将其与另外一个序列归并，就得到了一个有序的合并序列，在回归回去最后可以将原数组变得有序。
?
在归并排序中，需要创建第三方数组来零时存由两个有序数组归并好的数组，如果直接在原数组上归并，有些数据就会被覆盖这是坚决不可以的。归并完成后再将数据拷回原数组对应的位置。
函数实现：?
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)//如果一组数里面只有一个数就返回
{
return;
}
//将数组二分
int mid = begin + (end - begin) / 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 = begin1;//归并的数据保存在与原数组相对位置一样的地方
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)
{
//由于要进行递归，传值肯定是不可以的，所以我malloc一个数组出来传指针
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//进行递归
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}归并排序的非递归版本：?
既然有递归版本，当然就可有非递归版本。
?
大思路：还是这张图，我们观察，既然要每次归并都要求两个归并的数组为有序的，那我们不妨设置一个变量gap，当gap为1时代表一个待归并的数组有只有一个元素，所以我们先把数组一gap为1分开，将两两进行归并，在归并完成后，我们得到了数个有两个元素的数组，再对它们两两归并......直到，只剩下左右两个数组了，最后将他们归并，就得到了原数组的有序数组。
函数实现：?
void MergeSortNonR(int* a, int n)
{
//创建第三方数组
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
//先把数组分为若干个只有1个元素的数组两两归并，再把归并的有序数组两两归并，以此类推
for (int gap = 1; gap < n; gap *= 2)
{
//将两个元素个数为gap个的有序数组分在一组进行归并
for (int j = 0; j < n; j += 2 * gap)
{
//定义两个数组的区间
int begin1 = j, end1 = j + gap - 1;
int begin2 = j + gap, end2 = j + gap * 2 - 1;
//情况1：当第一组数的最后一个下标大于等于n的时候第二组数与第一组数
//最后下标周围的数都是越界访问的随机数，不能与第一组数进行归并
if (end1 >= n)
{
break;
}
//情况2：当第二组数的第一个下标>=n的时候第二组数都是越界访问的随机数，
//不能与第一组数进行归并
if (begin2 >= n)
{
break;
}
//情况3：当只有第二组数最后一个下标>=n时，第一组数与第二组数
//都有合法数进行归并，所以要修正end2为n-1
if (end2 >= n)
{
end2 = n - 1;
}
int i = begin1;//归并的数据保存在与原数组相对位置一样的地方
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));
}
}
free(tmp);
tmp = NULL;
}尤其要注意因为要排序的数组并不都是2^k个元素的，所以，在进行两两归并的时候，最后一个待归并数组可能没有能与之归并的一个数组。此时需要判断，我们不难想到，如果在两两归并后，有一个数组没有归并对象，比如这个数组的区间end1是大于n的，此时就不能进行递归，因为end1都是非法访问的位置，另一个数组的begin2与end2是非法的，还有end1是合法的，但是begin2与end2是不合法的，也没有与之归并的对象，也不能递归，最后还有一种情况，end1，begin2没有非法，end2有非法，此时第二个数组是由元素可以与第一个数组进行归并的，可以递归，所以就要将非法的end2修改为最后一个元素下标n-1。
计数排序
思路是统计原数组中相同元素的出现的次数，根据统计情况进行排序。
统计的数组大小我们利用相对法处理，它的大小利用原数组里的最大值与最小值来确定，这样就能保证每个元素都能被统计到而不会因为统计的数组大小设置小了而统计不到。它的大小我们设为max-min+1这样就保证了统计的完整性
?计数排序较为简单直接上代码：
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)//计算出数组中最大值与最小值
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
//开辟统计数组
int* count = (int*)calloc(max - min + 1, sizeof(int));
if (count == NULL)
{
perror("malloc fail");
return;
}
for (int j = 0; j < n; j++)//统计相同元素的个数
{
//这句代码，count的下标与原数组建立了联系，以一个规则来统计原数组相同元素的个数。
//原数组中一个元素减去最小值所得到的值作为count数组里的下标，统计一次次数
count[a[j] - min]++;
}
int i = 0;//创建临时变量i，以统计的结果将数组排序
//对计数数组进行遍历，如果一个下标对应的值不为0则利用统计规则反推出原数组中的元素
for (int k = 0; k < max - min + 1; k++)
{
while (count[k] != 0)//k下标对应的值不为0说明原数组中k反推回去的元素的个数也不为零
{
//count[k]为几就有几个相同的，放入一次减少一
a[i++] = k + min;
count[k]--;
}
}
}所有代码：?
//sort.h
#include "Stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>
void swap(int* p1, int* p2);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
void SelectSort(int* a, int n);
void BubbleSort(int* a, int n);
void AdjustDown(int* arr, int n, int parent);
void HeapSort(int* arr, int n);
int Part1Sort(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
void MergeSort(int* a, int n);
void MergeSortNonR(int* a, int n);
void CountSort(int* a, int n);
//sort.c
#include "sort.h"
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void InsertSort(int* a, int n)
{
for (int j = 0; j < n - 1; j++)
{
int end=j;
while (end >= 0)
{
if (a[end] > a[end + 1])
{
swap(&a[end], &a[end + 1]);
end--;
}
else
{
break;
}
}
}
}
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)//三层循环，一组一组的排好序
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
while (end >= i)
{
if (a[end] > a[end + gap])
{
swap(&a[end], &a[end + gap]);
end -= gap;
}
else
{
break;
}
}
}
}
}
//int gap = n;
//while (gap > 1)
//{
// gap = gap / 3 + 1;
// for (int i = 0; i < n - gap; i++)//两层循环，先把每一组的对应的两个排好序，齐头并进
// {
// int end = i;
// while (end >= 0)
// {
// if (a[end] > a[end + gap])
// {
// swap(&a[end], &a[end + gap]);
// end -= gap;
// }
// else
// {
// break;
// }
// }
// }
//}
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin<end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (a[i] < a[mini])
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
swap(&a[begin], &a[mini]);
if (maxi == begin)
{
maxi = mini;
}
swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
void BubbleSort(int* a, int n)
{
int end = n - 1;
int flag = 0;
while (end > 0)
{
for (int i = 0; i < end; i++)
{
if (a[i] > a[i + 1])
{
swap(&a[i], &a[i + 1]);
flag = 1;
}
}
if (flag == 0)
{
return;
}
end--;
}
}
void AdjustDown(int* arr, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
if (arr[parent] < arr[child])
{
swap(&arr[child], &arr[parent]);
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
//向下调整建堆时间复杂度为O(N),向上调整建堆时间复杂度为O(N*logN)
void HeapSort(int* arr, int n)
{
//如果要要排升序应该用大根堆向下调整,若降序则用小根堆向下调整。
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, n, i);//这里AdjustDown是大根堆向下调整
}
//实现排序
for (int i = 1; i < n; i++)
{
swap(&arr[0], &arr[n - i]);
AdjustDown(arr, n - i, 0);
}
}
int GetMid(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else
{
if (a[left] < a[right])
return right;
else
return left;
}
}
else
{
if (a[left] < a[right])
{
return left;
}
else
{
if (a[right] < a[mid])
return mid;
else
return right;
}
}
}
int Part1Sort(int* a, int left, int right)
{
int mid = GetMid(a, left, right);
swap(&a[left], &a[mid]);
int keyi = left;
while (left < right)
{
while (left < right && a[right] >= a[keyi])
{
right--;
}
while (left<right && a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
swap(&a[left], &a[right]);
}
}
int meet = left;
swap(&a[keyi], &a[meet]);
return meet;
}
int Part2Sort(int* a, int left, int right)
{
int mid = GetMid(a, left, right);
swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
while (left < right)
{
while (left < right && a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
int Part3Sort(int* a, int left, int right)
{
int mid = GetMid(a, left, right);
swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
swap(&a[cur], &a[prev]);
}
cur++;
}
swap(&a[keyi], &a[prev]);
return prev;
}
void QuickSort(int* a, int left, int right)
{
if (left>=right)
{
return;
}
int meet = Part1Sort(a, left, right);
if (right - left <= 8)
{
InsertSort(a + left, right - left + 1);
}
else
{
QuickSort(a, left, meet - 1);
QuickSort(a, meet + 1, right);
}
}
void QuickSortNonR(int* a, int left, int right)
{
Stack s;
StackInit(&s);
StackPush(&s, left);
StackPush(&s, right);
while (!StackEmpty(&s))
{
int end = StackTop(&s);
StackPop(&s);
int begin = StackTop(&s);
StackPop(&s);
int mid = Part1Sort(a, begin, end);
if (mid + 1 < end)
{
StackPush(&s, mid + 1);
StackPush(&s, end);
}
if (begin < mid - 1)
{
StackPush(&s, begin);
StackPush(&s, mid - 1);
}
}
StackDestroy(&s);
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)//如果一组数里面只有一个数就返回
{
return;
}
int mid = begin + (end - begin) / 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 = begin1;//归并的数据保存在与原数组相对位置一样的地方
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, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
for (int gap = 1; gap < n; gap *= 2)
{
for (int j = 0; j < n; j += 2 * gap)
{
int begin1 = j, end1 = j + gap - 1;
int begin2 = j + gap, end2 = j + gap * 2 - 1;
//当第一组数的最后一个下标>=n的时候第二组数与第一组数
//最后下标周围的数都是越界访问的随机数，不能与第一组数进行归并
if (end1 >= n)
{
break;
}
//当第二组数的第一个下标>=n的时候第二组数都是越界访问的随机数，
//不能与第一组数进行归并
if (begin2 >= n)
{
break;
}
//当只有第二组数最后一个下标>=n时，第一组数与第二组数
//都有合法数进行归并，所以要修正end2为n-1
if (end2 >= n)
{
end2 = n - 1;
}
//printf("[%d %d] [%d %d]", begin1, end1, begin2, end2);
int i = begin1;//归并的数据保存在与原数组相对位置一样的地方
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));
}
//printf("\n");
}
free(tmp);
tmp = NULL;
}
void CountSort(int* a, int n)
{
int max = a[0];
int min = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
{
max = a[i];
}
if (a[i] < min)
{
min = a[i];
}
}
int* count = (int*)calloc(max - min + 1, sizeof(int));
if (count == NULL)
{
perror("malloc fail");
return;
}
for (int j = 0; j < n; j++)
{
count[a[j] - min]++;
}
int i = 0;
for (int k = 0; k < max - min + 1; k++)
{
while (count[k] != 0)
{
a[i++] = k + min;
count[k]--;
}
}
}数据结构中栈代码在快速排序非递归代码中。?
创作不易，点关注收藏下吧！有错误的地方欢迎指正！