痛苦“浅尝”八大排序
目录
前言：
1.打印
2.插入排序
a.思想：
b.代码解释：
c.时间复杂度：
3.希尔排序
a.思想：
b.代码解释：
c.时间复杂度：
d.附加---多组并排：
4.冒泡排序
a.思想：
b.代码解释：
c.时间复杂度：
5.选择排序
a.思想：
b.代码解释：
c.时间复杂度：
6.堆排序
a.思想：
b.代码解释：
c.时间复杂度：
7.快速排序
a.霍尔法：
b.挖坑法：
c.前后指针法：
d.时间复杂度
e.快排优化：
f.空间复杂度
8.计数排序
a.思想：
b.代码解释：
c.时间复杂度：
d.空间复杂度
9.归并排序
a.思想：
b.代码解释：
c.时间复杂度：
d.空间复杂度
10.快排非递归
11.归并非递归
12.排序稳定性的分析
13.排序的总结比较
总结：
前言：
为什么是痛苦浅尝，因为解析的过程让博主感受到只能欣赏，不能触摸的感觉~~~
1.打印
这里提一下，默认排序都排成升序。
2.插入排序
a.思想：
其实为什么叫插入排序呢？就是将一个个数据往一个数组中插入进行排序，这里选了网上一个比较清晰的gif图帮助理解这个思想：
b.代码解释：
1.首先解释为什么循环的变量要从i开始，因为我们选取数据进行排序的时候，是选一个数据和这个数据的下一个数据进行比较，所以开始end从i-1开始，对于第一个数据，tmp则记录它的下一个数据。
2.外面每循环一次，相当于插入一个数据，相当于我们再[0,end]这个区间内插入数据并进行升序排序；如果前一个大于后一个，那就让前一个挪到后一个，并且--end，让end往前走，这是为了继续比较挪动完后前面的数据是否还需要挪到，最后我们再让记录下来的tmp给tmp的前一个位置即end+1（+1是因为end已经--了，要注意下标的对应关系）
3.如果插入后有序了，直接跳出循环，继续下一个数据。
c.时间复杂度：
1.如果是数组的顺序是排好的，那时间复杂度就是O(N),也就是遍历了一遍。
2.如果数组是逆序，那时间复杂度就是O(N^2)了，因为遍历一遍为N,在遍历的过程中，由于是逆序
所以会插入数据后一直往前交换，往前的每一个数据都会比较，然后交换，相当于外面遍历+里面比较构成等差数列，比如插入最后一个数据时前面全部数据都要往后挪，所以为O(N^2)：
3.希尔排序
a.思想：
首先预排序即接近有序(大的数更快跳到后面，小的更快跳到前面) ，然后执行插入排序(间隔为gap的分为一组，一共gap组。希尔的思想文字细说实在不易或者有些抽象博主也不能理解的很清楚，主要理解是分组的插入排序即可，一样给上一张清晰的网图理解一下：
b.代码解释：
1.我们要分为gap组，这个gap要怎么确定？假设我们设n为7，数据为下：
2.大致思路就是这，j是控制gap组数据，也就是分组的；为什么i 1) //{ // gap /= 2; // for (int i = 0; i = 0) // { // if (a[end] > tmp) // { // a[end + gap] = a[end]; // end -= gap; // } // else // { // break; // } // a[end + gap] = tmp; // } // }
其实这个思路更符合分组再插入的理念，i a[child + 1])//如果右孩子存在（因为如果左孩子为n-1,那右孩子就为n了，就越界了）并且左孩子大于右孩子，下标就走到右孩子上 { child = child + 1; } if (a[child]
void HeapSort(int* a, int n)
{
for (int 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;
}
}
如果我们要排升序，只需要改动向下调整或者写两个建堆方法：
改动两处：选孩子时选大的那个；如果孩子大于父亲，交换：
b.代码解释：
建堆注意点：
1.我们既然默认左孩子为小的那一个，那结束条件就应该是左孩子不存在的情况即当左孩子等于n的时候就越界了，而又由于堆是完全二叉树，所以左孩子不存在，那右孩子一定不存在，所以只写这一个就行。
2.child + 1 a[child + 1]，首先需要注意左孩子存在，但右孩子不存在的情况，所以判断child+1a[child+1]为假，就判断不出右孩子可能越界的情况了，所以右孩子的检查应该放到&&前面。
c.时间复杂度：
O（N*logN），详细见https://blog.csdn.net/2301_79698419/article/details/136179286
7.快速排序
a.霍尔法：
思想：
1.找一个基准值k（一般是最左或最右，是下标）,它比左边都小，比右边的大，此时k就在最终排好序的位置了。
2.如何保证k的左边都比它小，右边都比它大？将k从最左边L开始，右边R先走，R找到比k小停下；左边再走，找到比k大停下，交换左右；如果相遇，交换左L对应的值和k对应的值(为什么相遇这样交换，下面解释)。
3.再取k的左右区间，分别递归,直到只剩一个数或者区间不存在停下（停下原因下面解释），往回反，直到全部有序。
霍尔法：
int PartSort1(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int k = left;//默认k在左边
while (left end了，不存在这样的区间直接返回
{
return;
}
//三路划分
int left = begin;
int right = end;
int cur = left + 1;
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);//防止有序，导致效率下降
int key = a[left];
while (cur key)
{
Swap(&a[right], &a[cur]);
--right;
}
else
{
++cur;
}
}
小 相等 大 不用递归相等的区间了
[begin,left-1] [left,right] [right+1,end]
QuickSort(a, begin, left - 1);
QuickSort(a, right + 1, end);
}
有些极端情况时间上会变大，所以可以采取优化1.三路划分（小于k的，等于k的，大于k的）
//1.起始为l和k，l的下一个为c，末尾为r
//2.a[c]k，交换c和r的位置，--r（不++c是因为交换过来r的值不确定，还要判断c的值）
//4.a[c]==k，++c（当一串数都相等的情况直接++到最后，就不会再递归了）
//5.cur>r结束
f.空间复杂度
O（logN），满二叉树高度为logN，往下要压logN层栈帧，不用担心递归回来会再建立，递归回来会复用之前开好的栈帧，所以对于非递归的快排也是往下要logN层，也是O（logN）
8.计数排序
a.思想：
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 0; i max)
{
max = a[i];
}
}
int range = max - min + 1;
int* countA = (int*)calloc(range, sizeof(int));
if (countA == NULL)
{
perror("calloc fail");
exit(-1);
}
memset(countA, 0, sizeof(int) * range);
//统计次数
for (int i = 0; i
b.代码解释：
1.统计次数
统计每个数出现几次,次数放到countA对应的下标里（countA对应的下标因为减了最小的数，所以对应的再加上min正好是对应的数，没出现的是次数是0，就不会进下面的循环了)。
2.排序
每个数是被计了几次，就映射几次，如果对应坐标没有数据，就不映射。
3.缺陷
依据数据的范围，适用于范围集中的数组,数据不集中，range很大，比N大时间上就大了；
只能用于整形。
c.时间复杂度：
时间复杂度---O(N+Range)，range大就算range
d.空间复杂度
空间复杂度---O(Range)
9.归并排序
a.思想：
归并排序---对两个有序数组进行归并排序
1.先分解成两个数组，看分别有没有序，无序接着再对左部分再分解
2.直到分解到有序，往回归并(类似递归，往深先走)
3.归并时对原数组copy到tmp数组，copy过程中用尾插，尾插完再copy回去
代码：
void _MergeSort(int* a,int begin,int end,int* tmp)
{
if (begin == end)
{
return;
}
if (end - begin + 1 
还没有评论，来说两句吧...