堆排序还有冒泡排序都在前面的文章写过在这一章节就不写了
一、插入排序
一个数跟一个有序数组比较，最终这个数放在数组中的合适位置
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else {
break;
}
}
a[end + 1] = tmp;
}
} 二、希尔排序（思路）
2.1希尔排序的推导
预排序：分组插入排序
目标：大的更快换到后面，小的数更快换到前面的位置
思路：
假设间距 gap = 3
1.先逐个比较，比较的区间是[0, end]
先看红色
1.1如果前面的数据比后面的数据大，后面的数据就要覆盖住
当end跳出循环时，a[end+gap] = tmp
int gap = 3;
int end;
int tmp = a[end + gap];
//end大于0保持条件成立
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
//循环一次end往前移动gap位置
end -= gap;
}
else {//当tmp>gap时候跳出循环
break;
}
}
a[end + gap] = tmp;单个数据比较后
2.进行这一趟的循环比较
当end为5的下标时候要停止循环
int gap = 3;
for (int i = 0; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
//end大于0保持条件成立
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
//循环一次end往前移动gap位置
end -= gap;
}
else {//当tmp>gap时候跳出循环
break;
}
}
a[end + gap] = tmp;
}3.最后一趟数据比较完以后，进行多趟数据的比较
void ShellSort(int* a, int n)
{
int gap = 3;
for (int j = 0; j < gap; j++)
{
for (int i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
//end大于0保持条件成立
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
//循环一次end往前移动gap位置
end -= gap;
}
else {//当tmp>gap时候跳出循环
break;
}
}
a[end + gap] = tmp;
}
}
}不同的代码代表着不同的思路---以上的思路是红色的排完绿色的排然后紫色排
下面的代码优化表示着，gap组数据，交替完成分组插入排序
void ShellSort(int* a, int n)
{
int gap = 3;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
//end大于0保持条件成立
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
//循环一次end往前移动gap位置
end -= gap;
}
else {//当tmp>gap时候跳出循环
break;
}
}
a[end + gap] = tmp;
}
}当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。此外希尔排序的时间复杂度大概是O(N^1.3)
void ShellSort(int* a, int n)
{
int gap = n;
while (gap>1)
{
//无论gap为奇数还是偶数时，一直除到最后gap=1时就是插入排序
gap /= 2;
gap = gap/3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
//end大于0保持条件成立
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
//循环一次end往前移动gap位置
end -= gap;
}
else {//当tmp>gap时候跳出循环
break;
}
}
a[end + gap] = tmp;
}
}
}输出结果
三、选择排序（调试）
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
下面代码进行优化---一次从待排序的数据元素中选出最大和最小的元素
看下面的代码，看着思路很正确其实不对，接下来学习->如何快速找到问题
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
//最小，最大数的坐标
int minI = begin;
int maxI = end;
//每遍历一遍，找到最小与最大
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]);
Swap(&a[end], &a[maxI]);
begin++;
end--;
}
}调试除了F10，F11会很麻烦
上面可以直接打印每一趟的数组，直接发现问题
直接按绿色箭头可以跳过循环，直接进入发现问题的上一级，之后进行逐步调试
直接跳过前3个循环，直接找到问题的源头
发现了一个问题--begin的坐标也为maxI的坐标，begin和minI交换后，maxI的坐标就发生了改变.
minI的坐标就变成了maxI的坐标
解决措施
如果begin == maxI就让maxI = minI
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
//最小，最大数的坐标
int minI = begin;
int maxI = end;
//每遍历一遍，找到最小与最大
for (int i = begin; i <= end; i++)
{
if (a[i] < a[minI])
{
minI = i;
}
if (a[i] > a[maxI])
{
maxI = i;
}
}
Swap(&a[begin], &a[minI]);
if (begin == maxI)
{
maxI = minI;
}
Swap(&a[end], &a[maxI]);
begin++;
end--;
print(a, n);
}
}四、快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
4.1思路一 (递归)
单趟排序
找比key大和小的位置
找到后就发生交换，一直到相遇
相遇后，相遇的位置与key的位置发生交换---->为啥交换
目的：key放到了最终位置------左边比key小右边比key大
为啥相遇位置比key要小？右边先走保证的
有两种情况：
L遇R：R先走，R在比key小的位置停下来了，L没有找到比key大的，就会跟R相遇，相遇位置R停下的位置，是比key小的位置
R遇L：第一轮R如果找不到小，R和L相遇在key
第一轮先交换，此时L的位置小于key，R的位置大于key，R找小，没有找到，跟L相遇，此时相遇的位置就是L比key小
情景一、L遇R
情景二、R遇L
之后利用二叉树的思想
以下是单趟排序的常规问题------接下来要找特殊问题（之后所有的题目都要先找常规问题在找特殊问题）
void PartSort(int* a, int left, int right)
{
int key = left;
while (left < right)
{
//right先走找小---->右边先走才能保证相遇位置比key小
while (a[right] > a[key])
{
right--;
}
//left再走，找大
while (a[left] < a[key])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
}情景一，右边全是比key大的
此时要修改while(a[left] < a[key])里面的条件要保障key<right
情景二， 与key下标相等的值
就会进行死循环
两种情况考虑好后，修改代码----->单趟排序无问题
void PartSort(int* a, int left, int right)
{
int key = left;
while (left < right)
{
//right先走找小
while (left < right && a[right] >= a[key])
{
right--;
}
//left再走，找大
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
}单趟排序结束后进行多趟排序
多趟排序
[ ]key[ ] left和right位置发生改变，只能提前保留一份 用begin和end保留
[begin key-1] key [key+1 end]
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left;
int end = right;
int key = left;
while (left < right)
{
//right先走找小
while (left < right && a[right] >= a[key])
{
right--;
}
//left再走，找大
while (left < right && a[left] <= a[key])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
key = left;
QuickSort(a, begin, key - 1);
QuickSort(a, key + 1, end);
}时间复杂度是O(N*logN) 每层遍历要进行N层，高度是logN
当有序的情况下，快速排序时间复杂度最坏是O(N^2)
每一趟要遍历N次高度从logN变成了N
导致时间复杂度变成了O(N^2)
接下来进行优化
4.1.1随机选key
1.选择一个随机下标
2.下标与left的值进行交换
void QuickSort(int* a, int left, int right)
{
// 区间只有一个值或者不存在就是最小子问题
if (left >= right)
return;
int begin = left, end = right;
//选区间中的随机数做key
int randi = rand() % (right - left + 1);
思考为啥加left
当进行子区间的时候加上left才是随机数的下标
randi += left;
Swap(&a[left], &a[randi]);
int keyi = left;
while (left < right)
{
// right先走，找小
while (left < right && a[right] >= a[keyi])
{
right--;
}
// left再走，找大
while (left < right && a[left] <= a[keyi])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[keyi]);
keyi = left;
// [begin, keyi-1]keyi[keyi+1, end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}4.1.2 三数取中
1.left mid right
2.以上三个下标进行比较，谁是中间值就为key
//三数取中 left mid right
int GetMidi(int* a ,int left,int right)
{
int mid = (left + right) / 2;
if (a[left] > a[right])
{
if (a[right] > a[mid])
{
return right;
}//a[right]<a[mid]
else if (a[mid] > a[left])
{
return left;
}
//a[right]<a[mid]
//a[mid]<a[left]
else {
return mid;
}
}//a[left]<a[right]
else
{
if (a[mid] < a[left])
{
return left;
}
//a[left]<a[right]
//a[mid]>a[left]
else if (a[right] < a[mid])
{
return right;
}
//a[left]<a[right]
//a[mid]>a[left]
//a[right]>a[mid]
else {
return mid;
}
}
}以上只是对有序数组进行了优化，但是数组元素全部相同，时间复杂度依旧是O(N^2)
4.1.3小区间优化
递归建立栈帧也是有消耗的---->尤其是最后次数的递归占的比例太大
最后一层递归占比50%最后第二层递归占比25%
为了减少递归的次数---->最后几层采用插入排序以来减少递归的次数
//小区间选择走插入，可以减少90%的递归
if (right - left + 1 < 10)
{
InsertSort(a + left, right - left + 1);
}思考为什么传递的是（a + left ）
和随机选key+left思路一样
4.2思路二 (递归)
4.2.1前后指针
非常牛非常简单的方法：推箱子
prev和cur关系
1.prev 紧跟 cur 一前一后
2.prev和cur之间是比key大的值
void QuickSort2(int* a,int left,int right)
{
if (left >= right)
return;
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
++prev;
Swap(&a[prev], &a[cur]);
}
++cur;
}
//单趟数据交换完以后直接换值然后换下标
Swap(&a[keyi], &a[prev]);
keyi = prev;
// [begin, keyi-1]keyi[keyi+1, end]
QuickSort2(a, left, keyi - 1);
QuickSort2(a, keyi + 1, right);
}4.3思路三(非递归)
用数据结构中的栈（重要）
栈里面存区间
void QuickSortNonR(int* a, 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);
// 单趟
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}五、 归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
5.1归并(递归)
步骤一、分治
采用的是后序，先计算左子树再计算再计算右子树
步骤二、归并
先，进行比较，得出有序数先给临时数组tmp
之后，进行数组的保存
把tmp中的有序数组赋值给a中，方便下次比较。
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++];
}
}
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;
}5.2归并(非递归 )
直接改循环
如果e1，b2超出范围那就停止归并
但是e2超出范围就要修改e2的值
void MergeSortNonR(int* a,int begin, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap<n)
{
for (int j = begin; j < n; j += 2 * gap)
{
int begin1 = j, end1 = begin1 + gap - 1;
int begin2 = end1 + 1, end2 = begin2 + gap - 1;
//超出范围作出改变
if (begin2 > n || end1 > n)
break;
if (end2 > n)
end2 = n - 1;
//插入
int i = j;
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));
}
gap = gap * 2;
}
return 0;
}六、非比较排序
6.1计算排序
计算排序就好比是投票计数时写正字
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,Range))
3. 空间复杂度：O(Range)
4. 稳定性：稳定
什么是稳定--->稳定好比 2 2 3 4 5 1 3
1 2 2 3 3 4 5 原来相等的两个元素前后相对位置在排序后依然不变
void CountSort(int* a, int n)
{
//找最大最小求范围
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
return;
}
//全部制为0
memset(count, 0, sizeof(int) * range);
// 统计次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
// 排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
}