1.插入排序
1.1直接插入排序
在[0 end]区间上有序，然后将（end+1）的数据与前面有序的数据进行比较，将（end+1）的数据插入，这样[0 end+1]区间上就是有序的，然后再向后进行比较。
例如：想要数据调整为升，数组（end+1）位置的数据，前面是比它小的数据，后面是比它大的数据。
时间复杂度：O（N^2）
动图显示：
实现代码：
//插入排序(升序)
void intsertsort(int* arr, int num );
参数：指向数组首元素的指针，数组中的元素个数
//插入排序(升序)
void intsertsort(int* arr, int num )
{
for (int i = 0;i<num-1;i++)
{
//只考虑一次排序，在[0，end]上是有序的
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}1.2希尔排序
希尔排序是从直接插入排序演化而来的，分为两步，一个步是预处理，另一步是直接插入排序。
预处理：预处理是将原来的数据处理的尽可能有序，让数据尽可能的在最终排序完成的位置附近，这样就可以避免直接插入排序 数组（end+1）位置的数直接与[0 end]这个区间的数全部比较。
时间复杂度：O(N*logN)
动图演示：
实现代码：
//希尔排序
void shellsort(int* arr, int num)；
函数参数：指向数组首元素的指针，数组中的元素个数
//希尔排序(升序)
#include<stdio.h>
//*希尔排序
//*1.预排序
//*2.插入排序
//*时间复杂度O（N^1.3）
//*
void shellsort(int* arr, int num)
{
int gap = num;
while (gap > 1)
{
//保证最后一次是1，gap不是1时实现预排序，是1时实现插入排序
gap = gap / 3 + 1;
for (int i = 0; i < num - gap; i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + gap] = arr[end];
end=end-gap;
}
else
{
break;
}
}
arr[end + gap] = tmp;
}
}
}注：在gap不等于1的时候，是在执行预处理，当gap等于1的时候实在实现直接插入排序。
2.选择排序
2.1选择排序
选择排序，就是一趟选择出一个数组中的一个最大值或者最小值
时间复杂度：O(N^2)
动图演示：
实现代码：
//选择排序
void selectsort(int* arr, int num)函数参数：指向数组首元素的指针，数组中的元素个数
//交换函数
void swap(int*x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//选择排序
void selectsort(int* arr, int num)
{
//提升效率，可以同时进行最大值和最小值的排序
int begin = 0, end = num ;
while (begin < end)
{
int imin = begin, imax = begin;
for (int i = begin; i < end; i++)
{
if (arr[i] > arr[imax])
{
imax = i;
}
if (arr[i] < arr[imin])
{
imin = i;
}
}
if (begin == imax)
imax = imin;
//放置最小值和最大值
swap(&arr[imin], &arr[begin]);
swap(&arr[imax], &arr[end - 1]);
begin++;
end--;
}
}注：实现函数中是一趟找出数组中的最大值和最小值，这算是一种优化。
2.2堆排序
先堆数组进行堆排序，升序建大堆，降序建小堆，下面用小堆举例子，数组的首元素一定是数组的最大数，将首元素与数组的最后一个数进行交换，然后对数组[0 end-1]区间进行向下调整。继续，直到真个数组有序。
时间复杂度：O（N*logN）
动图演示：
注：上面演示的数组一开始已经建大堆。
实现代码：
//向下调整函数
void downjust_big(HPDataType* root, int num,int tmp)参数：指向数组首元素的指针，数组中的元素个数，需要向下调整的位置
//向下调整创建大堆
void downjust_big_heap(HPDataType* arr, int num)参数：指向数组首元素的指针，数组中的元素个数
//大堆升序
void downjust_arry_up(HPDataType* arr, int num)参数：指向数组首元素的指针，数组中的元素个数
//交换函数
void Swap(HPDataType* x, HPDataType* y)参数：指向需要交换元素的两个指针
//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//向下调整函数
void downjust_big(HPDataType* root, int num,int tmp)
{
assert(root);
int parent = tmp;
//假设左孩子和右孩子中大的那个是左孩子
int child = parent * 2 + 1;
//如果孩子节点不在堆中，就直接结束
while (child < num)
{
//（1）如果右孩子大于左孩子
//（2）如果没有右孩子，那么左孩子一定是最大的
if (root[child] < root[child + 1] && (child + 1) < num)
{
//将最大的孩子修改为右孩子
child++;
}
if (root[parent] < root[child])
{
Swap(&root[parent], &root[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
//直接跳出循环
break;
}
}
}
//向下调整创建大堆
void downjust_big_heap(HPDataType* arr, int num)
{
assert(arr);
for (int i = (num - 2) / 2; i >= 0; i--)
{
downjust_big(arr, num, i);
}
}
//大堆升序
void downjust_arry_up(HPDataType* arr, int num)
{
assert(arr);
downjust_big_heap(arr, num);
while (num)
{
Swap(&arr[0], &arr[num - 1]);
num--;
downjust_big(arr, num, 0);
}
}3.交换排序
3.1冒泡排序
冒泡排序，实际上就是两两比较，满足条件的两两交换，一趟可以选择出数组中的最大值后者最小值（取决于升序还是降序），直到将数据中的全部数据排序完成。
时间复杂度：N(N^2)
动图演示：
实现代码：
//冒泡排序
void BubbleSort(int* arr, int n) ;
函数参数：指向数组首元素的指针，数组中的元素个数
//冒泡排序（升序）
//* 时间复杂度O（N^2）
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void BubbleSort(int* arr, int n)
{
for (int j = 0; j < n-1; j++)
{
int flag = 1;
//一次遍历
for (int i = 0; i < n -j- 1; i++)
{
if (arr[i] > arr[i + 1])
{
swap(&arr[i], &arr[i + 1]);
flag = -1;
}
}
if (flag == 1)
break;
}
}
3.2快速排序
快速排序：就是选择一个数据，将数组中的数分为小于该数和大于该数的两个部分，小于该数的部分在该数的左边，大于的放在该数的右边。然后该数的位置为分界，然后在两个小区间重复上面的操作。
时间复杂度：O(N*logN)
代码演示：
hoare法：
挖坑法：
前后指针法：
初学者适合先看挖坑法进行一个理解。
实现代码：
//快速排序（hoare）
void QuickSort(int* arr, int left, int right) ;参数：指向数组首元素的指针，指向数组最左边位置，指向数组最右边位置
//快速排序
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
int keyi = begin;
while (begin < end)
{
//左边当钥匙时，是右边开始移动
//当找到一个比keyi小的数字时，停下来
while (begin<end && arr[end] >= arr[keyi])
{
end--;
}
//右边开始移动
while (begin<end && arr[begin] <=arr[keyi])
{
begin++;
}
swap(&arr[begin], &arr[end]);
}
//begin和end相遇
swap(&arr[keyi], &arr[end]);
keyi = begin;
//接下来就是递归
//标准值左右两边
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi+1,right);
}注：选择最左边的数为标志数，那么那就不许从右边进行开始比较。
//快速排序（挖坑法）
void QuickSort(int* arr, int left, int right)；参数：指向数组首元素的指针，指向数组最左边位置，指向数组最右边位置
//快速排序（挖坑法）
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
int begin = left, end = right;
int keyi = arr[left];
while (begin < end)
{
//左边当钥匙时，是右边开始移动
//当找到一个比keyi小的数字时，停下来
while (begin < end && arr[end] >=keyi)
{
end--;
}
arr[begin] = arr[end];
//右边开始移动
while (begin < end && arr[begin] <= keyi)
{
begin++;
}
arr[end] = arr[begin];
}
//begin和end相遇
arr[end] = keyi;
keyi = begin;
//接下来就是递归
//标准值左右两边
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}//快速排序（前后指针法）
void QuickSort(int* arr, int left, int right)
参数：指向数组首元素的指针，指向数组最左边位置，指向数组最右边位置
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
int prev = left, cur = left + 1;
int keyi = left;
while (cur<=right)
{
//cur指针找比arr[keyi]小的数值
if (arr[cur] < arr[keyi] && arr[++prev] != arr[cur])
swap(&arr[cur], &arr[prev]);
cur++;
}
swap(&arr[keyi], &arr[prev]);
keyi = prev;
//接下来就是递归
//标准值左右两边
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
由于快速排序使用递归，如果数据过大，就很容易出现栈的溢出，因此需要改为非递归。
//快速排序（非递归）
实际上，非递归是使用了递归的逻辑，只不过是使用栈数据结构来储存需要进行快速排序的两个区间。
void QuickSortNonR(int* arr, int left, int right)
参数：指向数组首元素的指针，指向数组最左边位置，指向数组最右边位置
//栈的定义
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶（指向栈顶元素的下一位）
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
// 入栈 (对应顺序表的尾插)
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//判断插入时的空间
if (ps->top == ps->capacity)
{
//判断栈是否申请空间
ps->capacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* new = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType));
if (new == NULL)
{
perror("StackPush::realloc");
}
else
{
ps->a = new;
}
}
//尾插
ps->a[ps->top] = data;
ps->top++;
}
// 出栈 (对应于顺序表的尾删)
void StackPop(Stack* ps)
{
assert(ps);
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->top-1];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
//栈为空返回1，栈不为空返回0
if (ps->top == 0)
{
return 0;
}
else
{
return 1;
}
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
ps->capacity = ps->top = 0;
free(ps->a);
ps->a = NULL;
}
//快速排序（非递归）
void QuickSortNonR(int* arr, int left, int right)
{
//非递归实际上就是使用栈来模拟递归
Stack ps;
StackInit(&ps);
//将区间数放入栈中
StackPush(&ps, left);
StackPush(&ps, right);
while (StackEmpty(&ps))
{
//取出栈的区间
int end = StackTop(&ps);
StackPop(&ps);
int begin = StackTop(&ps);
StackPop(&ps);
//去除区间只有一个数值，和区间没有数值
if (begin < end)
{
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && arr[++prev] != arr[cur])
swap(&arr[cur], &arr[prev]);
cur++;
}
swap(&arr[keyi], &arr[prev]);
keyi = prev;
//添加小区间,先添加右区间，在添加左区间
StackPush(&ps, keyi + 1);
StackPush(&ps, end);
StackPush(&ps, begin);
StackPush(&ps, keyi - 1);
}
}
//销毁栈
StackDestroy(&ps);
}3.2.1快速排序优化（三数取中）
如果我们只是单一的选择数组的首元素作为比较的标志数，那么我们就很容易取到过于大或者过于小的数，那么我们的时间复杂度就很容易偏向于O(N^2) ,所以使用三数取中，其取数组的首元素，尾元素和中间元素，在这个三个数中取中间的数，然后将中间的数与数组首位置的数据交换，然后进行一个快速排序。
代码实现：
//三数取中
int ThreeNumMiddle(int* arr, int left, int right)参数：指向数组首元素的指针，指向数组最左边位置，指向数组最右边位置
//三数取中
int ThreeNumMiddle(int* arr, int left, int right)
{
int middle = (right + left) / 2;
if (arr[left] > arr[right])
{
if (arr[right] > arr[middle])
return right;
else
{
if (arr[left] > arr[middle])
return middle;
else
return left;
}
}
else
{
if (arr[middle] > arr[right])
return right;
else
{
if (arr[left] > arr[middle])
return left;
else
return middle;
}
}
}3.2.2快速排序优化（小区间优化）
快速排序是一个前序遍历，这个排序的区间的划分上很像二叉树，最终小区间的数量会非常多，其实当区间足够小的时候，不同排序之间的时间差异不是很大，当区间差小于一个数时，使用直接插入排序，这样会很节约很多分区间的时间花费。
//小区间优化
//三数取中
int ThreeNumMiddle(int* arr, int left, int right)
{
int middle = (right + left) / 2;
if (arr[left] > arr[right])
{
if (arr[right] > arr[middle])
return right;
else
{
if (arr[left] > arr[middle])
return middle;
else
return left;
}
}
else
{
if (arr[middle] > arr[right])
return right;
else
{
if (arr[left] > arr[middle])
return left;
else
return middle;
}
}
}
//插入排序(升序)
void intsertsort(int* arr, int num)
{
for (int i = 0; i < num - 1; i++)
{
//只考虑一次排序，在[0，end]上是有序的
int end = i;
int tmp = arr[end + 1];
while (end >= 0)
{
if (tmp < arr[end])
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;
}
}
arr[end + 1] = tmp;
}
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
//小区间优化
//在小区间中使用快速排序
if ((right - left) <= 5)
{
intsertsort(arr + left, right - left + 1);
return;
}
//三数取中
int middle = ThreeNumMiddle(arr, left, right);
swap(&arr[left], &arr[middle]);
int prev = left, cur = left + 1;
int keyi = left;
while (cur<=right)
{
//cur指针找比arr[keyi]小的数值
if (arr[cur] < arr[keyi] && arr[++prev] != arr[cur])
swap(&arr[cur], &arr[prev]);
cur++;
}
swap(&arr[keyi], &arr[prev]);
keyi = prev;
//接下来就是递归
//标准值左右两边
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}4.归并排序
4.1归并排序
归并排序，如其其名，先归，指将数组进行一个划分将区间中只剩一个数，然后将这个区间与它相邻的区间进行比较，将两个区间的数据进行一个排序，插入到一个中间数组中。
动图演示：
代码实现：
//归并排序(递归版)
void MergeSort(int* arr, int num)参数：指向数组首元素的指针，数组中元素的数量
//子函数（实现主要功能）（递归）
void _MergeSort(int* arr, int* tmp, int left, int right)参数：指向数组首元素的指针，指向中间临时数组首元素的地址，指向数组最左边位置，指向数组最右边位置
//子函数（实现主要功能）（递归）
void _MergeSort(int* arr, int* tmp, int left, int right)
{
//区间中只有一个数直接跳出循环
if (left >= right)
return;
int middle = (left + right) / 2 ;
//左区间
_MergeSort(arr, tmp, left, middle);
//右区间
_MergeSort(arr, tmp, middle+1, right);
int begin1 = left, begin2 = middle + 1;
int end1 = middle, end2 = right;
int i = begin1;
//一次比较
while (begin1<=end1&&begin2<=end2)
{
//将小的数放数组中
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
//循环左右两个数组一个又一个读取完成
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//将调序的结果复制到原数组中
memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
}
//归并排序(递归版)
void MergeSort(int* arr, int num)
{
int* tmp = (int*)malloc(sizeof(int) * num);
if (tmp == NULL)
{
perror("MergeSort::malloc");
exit(1);
}
//调用子函数
_MergeSort(arr, tmp, 0, num-1);
//释放空间
free(tmp);
tmp = NULL;
}//归并排序（非递归）
void MergeSortNonR(int* arr, int num)//子函数（非递归）
void _MergeSortNonR(int* arr, int* tmp, int left, int right)
//子函数（非递归）
void _MergeSortNonR(int* arr, int* tmp, int left, int right)
{
int gap = 1;
int n = right - left + 1;
while (gap<n)
{
for (int j = left; j <=right;j=j+2*gap )
{
int begin1 = j, begin2 = j + gap;
int end1 = j + gap - 1, end2 = j + 2*gap - 1;
int i = j;
//数组越界的问题
//[begin1 end1]和[begin2 end2]
//对应于end1大于n和begin2 > n的情况
if (begin2 > right)
break;
//对应end2 > n 的情况
if (end2 > right)
{
end2 = right;
}
//一次比较
while (begin1 <= end1 && begin2 <= end2)
{
//将小的数放数组中
if (arr[begin1] < arr[begin2])
tmp[i++] = arr[begin1++];
else
tmp[i++] = arr[begin2++];
}
//循环左右两个数组一个又一个读取完成
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//将调序的结果复制到原数组中
memcpy(arr + j, tmp + j, sizeof(int)* (end2-j+1));
}
gap = 2 * gap;
}
}
//归并排序（非递归）
void MergeSortNonR(int* arr, int num)
{
int* tmp = (int*)malloc(sizeof(int) * num);
if (tmp == NULL)
{
perror("MergeSort::malloc");
exit(1);
}
//调用子函数
_MergeSortNonR(arr, tmp, 0, num - 1);
//释放空间
free(tmp);
tmp = NULL;
}gap是一个区间差，区间差成倍数的增加，这样最终会出现一个越界的情况，每一次会分为连个区间 [begin1 end1] [begin2 end2] begin1是不可能越界的，越界的可能是end1 begin2 和end 2
end1越界：说明end1，begin2和end2都是越界的。这也就是说只有一个区间是有效区间，那么就不需要两个区间进行比较，直接退出。
begin2越界：这个情况和end1越界是一样的，只有一个有效区间，可以直接退出。
end2越界，说明有两个区间，一个区间有效，一个区间部分有效，end2越界说明它大于数组的最左边的位置，那么那个部分有效的区间中的有效区间实际上就是[begin2 right],直接将end2赋值为rigth，就可以进行两个区间的比较。
总结
上面介绍了几种常见的数据结构的排序方法，一些排序的理解是比较复杂的，所以需要自己画相应的图，一步一步的推演排序的过程。同时有什么错误或者问题可以在评论区进行交流。
