这篇文章会从思路到实现到分析时间空间复杂度，一次性搞懂各种排序
有帮助的话点个赞收藏一下不迷路啊
?如果对时间空间复杂度还不熟悉的请去看
本文章不会讲堆排序，这部分内容会马上单写一篇博客介绍，和堆的和一些更复杂的问题写在一起（写完我会来贴链接~）
目录
在介绍下面的代码之前，先进行一些准备工作，里面包括一些测试方法和性能比对
创建项目之后，把头文件（Sort.h），源文件（Sort.c），测试文件（test,c）都写好
?性能测试主要就是生成随机数然后用更多的测试样例测试运行时间
//性能测试
void Toptest()
{
srand(time(0));
const int N = 10000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
if (a1 == NULL)
{
perror("malloc a fail");
exit(-1);
}
if (a2 == NULL)
{
perror("malloc a fail");
exit(-1);
}if (a3 == NULL)
{
perror("malloc a fail");
exit(-1);
}if (a4 == NULL)
{
perror("malloc a fail");
exit(-1);
}if (a5 == NULL)
{
perror("malloc a fail");
exit(-1);
}if (a6 == NULL)
{
perror("malloc a fail");
exit(-1);
}if (a7 == NULL)
{
perror("malloc a fail");
exit(-1);
}
for (int i = 0; i < N; i++)
{
a1[i] = rand()+i; //如果想生成连续的数字，直接写ai[i]=i;
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
Insertsort(a1, N);
int end1 = clock();
int begin2 = clock();
Shellsort(a2, N);
int end2 = clock();
int begin3 = clock();
Selectsort(a3, N);
int end3 = clock();
int begin4 = clock();
Heapsort(a4, N);
int end4 = clock();
int begin5 = clock();
Bubblesort(a5, N);
int end5 = clock();
int begin6 = clock();
Quicksort(a6, N);
int end6 = clock();
int begin7 = clock();
Mergesort(a7, N);
int end7 = clock();
printf("Insertsort:%d \n",end1-begin1);
printf("Shellsort: %d \n", end2 - begin2);
printf("Selectsort:%d \n", end3 - begin3);
printf("Heapsort:%d \n", end4 - begin4);
printf("Bubblesort:%d \n", end5 - begin5);
printf("Quicksort:%d \n", end6 - begin6);
printf("Mergesort:%d \n",end7-begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}测试函数就是简单的自己开辟一块数组，然后再写一个打印函数
void Printf(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}头文件一定都要写在.h文件里
1.插入排序
?排序肯定不需要多介绍，插入排序就像是打牌的时候边摸排，边理牌，我们想把每个新摸到的手牌都按照顺序或者逆序放到之前的手牌里，这就是插入排序
1.1直接插入排序
直接插入就是用代码实现上面说过的过程，现在有一个数组a里面保存一些乱序数据，我们要做的就是从第二个元素开始，每一个元素都插入排序一遍
即，数组里第一个元素看成是有序的，后面每一个元素都使用插入排序
把要插入的元素保存在tmp，往前找比tmp里面元素更小的，如果比tmp保存的元素大，就往后挪动
void Insertsort(int*a ,int n) //a是一个数组指针，n是数据元素个数
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}性能分析：
时间复杂度：O(N^2)
空间复杂度：O(1)? 没有额外开口空间
稳定性（假设数组里面有两个5，排序之后是否还能保证两个5的相对位置）：好（能保证两个5的相对位置）
1.2希尔排序
希尔排序分成两步，第一步通过gap，把间隔为gap的数据都排序好，最后再把所有的数据进行插入排序
这两步简记为
1.预排序（gap>1）
2.直接插入排序(gap == 1)
gap的选择很重要，直接关乎到排序的性能
先来看一下希尔排序应该怎么写
//希尔排序,如果是i++就叫gap并排
void Shellsort(int *a,int n)
{
int gap = 3;
for (int j = gap; j > 0; j--)
{
for (int i = 0; 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;
}
}
}细心的小伙伴就会发现其实就是把直接插入排序的1换成gap
事实证明gap=2或者gap=3都是相对最好的，3用的更普遍一些
或者还可以写成更灵活的（gap越来越小代表排序的区间越来越细化）
//gap>1预排序，gap == 1直接排序
void Shellsort2(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2; //或者gap=gap/3+1;保证一定最后是1
for (int j = gap; j > 0; j--)
{
for (int i = 0; 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;
}
}
}
}希尔的时间复杂度是很复杂的，一眼看过去就不是我们之前见过的金典模型
直接给出结论，在数据结构的权威大佬严蔚敏《数据结构（C语言版）》有写、
时间复杂度是O(N^1.3)
空间复杂度毫无质疑：O(1)
稳定性：不好，因为一样的数据可能被分到不同的组（每组间距是gap）
2.选择排序
思想：把数组头（begin）尾（end）数据看成就是最大和最小的，从中间遍历，如果有比a[begin]还小的数据直接交换（最好单独写一个交换函数，分装一下），同理有比a[end]还大的数据直接和a[end]交换
2.1选择排序
直接实现上面的思想就可以了
void Selectsort(int* a, int n) //时间复杂度是N^2
{
int begin = 0;
int end = n-1;
while(begin<end)
{
for (int i = begin; i < end; i++)
{
if (a[i] < a[begin])
{
Swap(&a[i], &a[begin]);
}
if (a[i] > a[end])
{
Swap(&a[i], &a[end]);
}
}
begin++;
end--;
}
}性能分析：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不好
假设这样的情况
?最后两个5的顺序颠倒了所以是不稳定的
2.2堆排序
3.交换排序
基本思想：比较两个值然后进行交换
3.1冒泡排序
这个大家肯定最熟悉了
简单介绍一下 比较相邻的两个元素（按照顺序），如果大数在前就交换，否则比较下两个数字，直到没有数字需要比较
void bubblesort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = i; j < n - i; j++)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
}
}
}
}时间复杂度：O（N^2）
空间复杂度：O(1)
稳定性：好（相等的元素相邻直接不需要交换就过去了）
3.2快速排序（快排）
大名鼎鼎的快排其实有很多的小细节和多种实现方法
叫做快排，但不是最快或者说不是方方面面最优的
1.Hoare的经典老办法
其实他的历史很悠久了，Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：
然后转化成子问题，这时候key就把整个数组分成了两段
[begin,key-1]? key? [key+1,end]? 转化成子问题接着递归就好了
递归结束的条件就是begin>=end
void Quicksort(int* a, int begin,int end)
{
if (begin >= end)
{
return;
}
//减少递归调用的次数
//可以进行区间优化，其实最后区间长度很小没必要用子问题，直接插入排序就行
if ((end - begin + 1) < 5)
{
Insertsort(a, end - begin + 1);
}
else
{
int key = Part1Quicksort_Hoare(a, begin, end);
Quicksort(a,begin,key-1);
Quicksort(a ,key+1,end);
}
}写一个这样的函数，把不同的快排方法分装
int Part1Quicksort_Hoare(int*a,int begin,int end)
{
int mid = Getmid(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin, right = end;
int key = left;
while (left < right)
{
while (a[right] > key && left < right)
{
right--;
}
while (a[left] < key && left < right)
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
return key;
}优化： 其实也都写在上面了，如果最后的区间分划到足够小就可以不用非得快排，可以用很简单的插入排序
if ((end - begin + 1) < 5)
{
Insertsort(a, end - begin + 1);
}优化：三数取中选key，保障key不是最值，排除有序数组的影响
//三数取中,保证key的数据不是最值，排除有序对快排的影响
int Getmid(int* a, int begin, int end)
{
int mid = (begin + end) / 2;
if (a[begin] < a[mid])
{
if (a[mid] < a[end])
{
return mid;
}
else
{
if (a[begin] < a[end])
return end;
else
return begin;
}
}
else
{
if (a[mid] > a[end])
return mid;
else
{
if (a[begin] > a[end])
return end;
else
return begin;
}
}
}2.挖坑法
把key的数据放在临时变量里面（用坑位保存）
right先走找小，走到比key小停止，把right的位置换成坑位，然后left找大，找到了还是和坑位交换，最后坑位就是right和left的碰头点，坑位和key交换相当于left和坑位交换，就是碰头点和坑位交换
//挖坑法写快排
int Partsort2_Quicksort_Hole(int* a, int begin, int end)
{
int mid = Getmid(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin;
int right = end;
int hole = left;
int key = a[hole];
while (left < right)
{
while (a[right] > a[key] && left < right)
{
right--;
}
a[hole] = a[right];
hole = right;
while (a[left] < key && left < right)
{
left++;
}
a[hole] = a[left];
hole = left;
}
a[hole] = a[key];
return key;
}
3.双“指针”? 其实不是真正的指针，就是标注下标而已
cur表示当前位置的下标，把所有比key小的都先++prev再交换，然后cur往后走最后
还是一样的把所有比key小的都折腾到前面去了
//这样写双指针
int Partsort3_Quicksort_double(int* a, int begin, int end)
{
int key = begin;
int prev = begin;
int cur = prev++;
while (cur <= end)
{
if (a[cur] < a[key])
{
Swap(&a[cur], &a[++prev]);
}
cur++;
}
Swap(&a[prev], &a[key]);
key = prev;
return key;
}上面都是在递归的大框架下写的，但是要注意递归的空间复杂度是深不可测的，栈帧的开辟要谨慎，可能一不注意就栈溢出了
所以我们还可以非递归的方式
借助栈这个数据结构
（如果对栈有点陌生先去看一下我之前的博客吧：栈）
因为说白了你的子问题递归就是区间来回在传递在改变，所以只要解决了区间的问题递归与否无所谓
所以我们选择用栈来保存区间
注意：
如果是[1,2] [3,4]? 两个区间想先拿出[1,2]就要后入而且是入2 1
因为要时刻考虑到栈的结构特点：先入后出
//快排还可以用非递归的方法写、
//注意我们是因为要带着区间范围这个参数才选择用子问题
//但是区间还可以用栈保存
void QuickNonR(int* a, int begin, int end)
{
ST st; //需要拉进来栈的代码
StackInit(&st);
StactPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
int right = StackTop(&st);
StackPop(&st);
int left = StackTop(&st);
StackPpop(&st);
int key = Partsort2_Quicksort_Hole(a, left, right);
//如果按照前面的思路我还是想先排前面的区间就要先把后面的区间入栈
//【left,key-1】key【key+1,right】
if (key + 1 < right)
{
StackPush(&st, key + 1);
StackPush(&st, right);
}
if(left < key - 1)
{
StackPush(&st, left);
StackPush(&st, key - 1);
}
}
StackDestory(&st);
}其实上面的三种递归方法和一种非递归方法都是用key把区间分划成两段式
但是如果我的数据重合度很高（一万个2和一个4）这时候快排就会无敌慢?
为了解决这个大漏洞，有个天才想出了三段式的放法
//快排有一个优化的版本，当数据很多都等于key的时候老版本就会性能下降
void Quicksort_New(int* a, int begin,int end)
{
if (begin >= end)
{
return;
}
if ((end - begin + 1) < 5)
{
Insertsort(a, end - begin + 1);
}
else
{
int mid = Getmid(a, begin, end);
Swap(&a[begin], &a[mid]);
int left = begin;
int right = end;
int cur = begin + 1;
int key = a[left];
while (cur <= right)
{
if(a[cur]<a[left])
{
Swap(&a[cur++],&a[left++]);
}
if(a[cur]==a[left])
{
cur++;
}
if (a[cur] > a[right])
{
Swap(&a[cur], &a[right--]);
}
}
//[begin,left-1] [left , right] [right+1,end] 其中，中间区域都是和key相等的
Quicksort_New(a, begin, left - 1);
Quicksort_New(a, right + 1, end);
}
}性能分析（递归的）：
时间复杂度：O(N*logN)
空间及复杂度:O(logN)
参考二叉树的结构一下就知道为什么是这个空间复杂度了
稳定性:不好
4.归并排序
?稳稳的老大哥
还是和上面写快排一样可以分割出去子函数，方便以后有新方法之后补充
void Mergesort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("Mergesort malloc fail");
exit(-1);
}
//和上面的快排一样还是需要子函数
_Mergesort(a, 0, n-1, tmp);
free(tmp);
tmp = NULL;
}
?每次分到足够小之后就取小的尾插到tmp这块空间，然后足够小的几个数排完之后就拷贝回去即可
//归并排序，条件：两端有序区间，方法:取小的尾插
void _Mergesort(int* a, int begin, int end, int* tmp)
{
if (begin >= end)
return;
//还是涉及分割区间，最后要变成两个比大小
int mid = (begin + end) / 2;
//[begin,mid][mid+1,end]
//递归让子区间有序
_Mergesort(a, begin, mid, tmp);
_Mergesort(a, mid + 1, end, tmp);
//此时两个大区间都有序了，可以进行归并
//由于变量之间会相互影响，最好还是重新定义一下
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin;
while (begin1<=end1 && begin2<=end2)
{
if (a[begin1] < a[begin2])
{
tmp[i] = a[begin1++];
}
else
{
tmp[i] = a[begin2++];
}
i++;
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}修正：
因为限制条件只有begin1不会越界，其他end1，begin2，end2都可能越界
归并排序如果是把越界的地方修正成不存在的区间那是不是相当于在这次循环里根本什么都没动
就还是不越界那部分原封不动拷贝到tmp数组，然后memcpy拷贝回去了
?
当然非递归也是可以的
//也可以用非递归的方式
void MergesortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("Mergesort malloc fail");
exit(-1);
}
//每组有rangeN个数据要进行归并
for (int rangeN = 1; rangeN < n; rangeN *= 2)
{
for (int i = 0; i < n; i += rangeN * 2)
{
int begin1 = i;
int end1 = i+rangeN-1;
int begin2 = rangeN + i;
int end2 = i+2*rangeN-1;
//end1 begin2 end2 都越界
//可以修正也可以直接break
//修正出一段不存在的区间然后所有数据相当于没动
//如果在当前的i，break出去相当于跳出了这个i的循环，这一段没拷贝但是其他正常的地方还是要拷贝的所以不能把memcpy写在循环的外面（整体拷贝）
if (end1 >= n)
{
end2 = n-1;
end1 = n - 1;
begin2 = n;
}
//或者直接break；
/*if (end1 >= n)
{
break;
}*/
else if (begin2 >= n)
{
begin2 = n;
end2 = n - 1;
}
else if(end2>=n)
{
end2 = n-1;
}
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
}
}
free(tmp);
tmp = NULL;
}性能测试：
时间复杂度：O(NlogN）
空间复杂度：O(N）
稳定性：稳定
5.总结?
最后我们总结一下所有算法的性能
对你有帮助的话点个赞吧
