常见的排序算法分为以下四种，插入排序，选择排序，交换排序，归并排序。
一、插入排序
(一)直接插入排序
直接插入排序，将一段数组看做被分成已排序序列和未排序序列，排序过程是从未排序序列的元素开始，该元素与已排序序列的元素从后向前扫描，找到第一个小于（或大于）该元素的已排序项，然后将该未排序项插入到已排序序列中的适当位置。
void InsertSort(int* a, int n)
{
//最后一组，[0, n-2]
for (int i = 0; i < n - 1; i++)//是n不是n-1！！！
{
int end = i;
int tmp = a[end + 1];
//[0,end]是有序的，从end+1开始插入
while (end >= 0)
{
if (tmp < a[end])//比tmp值大的，往后挪
{
a[end + 1] = a[end];
end--;
}
else
{
//不在里面放是因为，如果要插入的，比所有值都小
//end此时为-1，循环结束，跳不到else
break;
}
}
a[end + 1] = tmp;
}
}(二)希尔排序
希尔排序是针对直接插入排序的改进
将数组元素分为gap组，即每隔gap个的元素为一组，组内排序，然后修改gap值，当gap为1时，就是直接插入排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap = gap / 2;//除几都可以，除3比较好，但是最后不能保证是1
gap = gap / 3 + 1;//这样就保证了最后结果一定是1
for (size_t i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
OP()把打印注释
//printf("gap:%2d->", gap);
//PrintArray(a, n);
}
}二、选择排序
(一)选择排序
选择排序，遍历整个数组，每次选择出最大的
进行升级，每次遍历找出最小最大的
注意下面代码中的
if (begin == maxi)
maxi = mini;
这个是很有必要的
比如说begin开始是最大值，和mini交换之后，接下来最大maxi要和begin进行交换，但是begin此时的值不是最大值
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i < end; i++)//从begin+1是因为，自己跟自己比没意义，<end也是
{
if (a[i] > a[maxi])
maxi = i;
if (a[i] < a[mini])
mini = i;
}
Swap(&a[begin], &a[mini]);
if (begin == maxi)
maxi = mini;
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}(二)堆排序
void AdjustDown(int* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
// 向下调整建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}三、交换排序
(一)冒泡排序
两层循环，内层单趟是找出最大的
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
//里面是单趟
int flag = 0;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j - 1], &a[j]);
flag = 1;
}
}
if (flag == 0)
break;
}
}(二)快速排序
1、hora方法
以第一个数为key，将比key小的元素放在基准元素的左边，将比key大的元素放在基准元素的右边。
遍历结束后，key左边所有的都比key小，右边都比key大，key就排序完成了，然后在递归调用快排函数排序左右两侧。
但是这样有个问题，假如数组一开始就有序，那么排序的深度很大（需要递归多次），这就可以使用三数取中来优化代码，left，right，以及(left+right)/2这三个是数的下标，找到中间值给left进行交换。
同时，快排的递归调用类似于满二叉树，后三层递归次数占总次数很大，可以使用小区间优化，当该区间元素个数不够时，使用一种排序方法排序，这里选择直接插入排序，（直接插入排序在小规模数据上表现良好）。
int GetMidi(int* a, int left, int right)
{
//取得是大小在中间的值
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
return midi;
else if (a[left] < a[right])//走到这里说明a[left] < a[midi], a[right] < a[midi]
return right;
else
return left;
}
else//a[left] >= a[midi]
{
if (a[midi] > a[right])
return midi;
else if (a[left] < a[right])
return left;
else
return right;
}
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);//a+left是因为InsertSort需要数组起始地址
}
else
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
// 右边找小
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 左边找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
}//while运行完，左边全是比key小，右边全是比key大
Swap(&a[keyi], &a[begin]);
keyi = begin;
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}2、前后指针方法
prev和cur
cur先向右移动，找到比key小的，然后++prev，交换prev和cur的值
遍历一遍，prev最后位置左边，都是比key值小的，跟Quick相似，左边全比他小，右边比key大
int PartSort2(int* a, int left, int right)
{
三数取中
//int midi = GetMidi(a, left, right);
//Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)//还在区间
{
//由于一开始紧挨着，后面判断是为了防止自己交换
//顺序也不能反，如果a[cur] > a[keyi]，就不会执行后面的，也就是说cur++但是prev不++
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
//不要写else，cur无论什么情况都要++
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);//a+left是因为InsertSort需要数组起始地址
}
else
{
int keyi = PartSort2(a,left,right);//修改此处即可
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}3、非递归方法
快排非递归 -- 数据用栈模拟（队列也可以，队列先进先出，数据就不用倒着进）
用栈类似于DFS（深度优先遍历）
用队列类似于BFS（广度优先遍历 -- 二叉树的广度就是层序遍历）
递归会建立栈帧，（溢出跟深度有关）
在递归里，栈帧存的核心数据是 -- 区间（所以非递归方式，栈存放区间）
循环每走一次，取栈顶区间，进行单趟排序，右左子区间入栈（右左是因为栈后进先出）
函数调用是在栈区取空间（栈只有8M）
数据结构的栈空间不够去扩容是在堆（堆在32位下是2G）
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 = PartSort2(a, begin, end); // [begin, keyi - 1] keyi [keyi + 1, end] // 先入右[keyi + 1, end] if (keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi + 1); } //再入左[begin, keyi - 1] if (begin < keyi - 1) { STPush(&st, keyi - 1); STPush(&st, begin); } } }
四、归并排序
假设把数组分成两段，如果左右区间有序，两个指针指向左右区间第一个，一个比另一个小，就比所有的小
把小的尾插到一个tmp数组
类似二叉树的后序，有序就归并，无序就递归
1、递归
void _MergeSort(int* a, int* tmp, int begin, int end)//_从习惯和风格上是子函数
{
//只有一个值，返回
if (begin >= end)
return;
int midi = (begin + end) / 2;
//[begin , midi] [midi + 1, end] -- 有序就可以进行归并
//不能是[begin , midi - 1] [midi, end]!!!
//假设begin=0，end=1，此时midi=0，如果-1得到的分组就是[0,-1]，[0,1]
//[偶数，偶数+1]分组得到，[偶数，偶数]，[偶数，偶数+1] -- [偶数，偶数+1]一直出现，造成栈溢出x
//子问题递归来实现有序
_MergeSort(a, tmp, begin, midi);
_MergeSort(a, tmp, midi + 1, end);
//归并
int begin1 = begin, end1 = midi;
int begin2 = midi+1, end2 = end;
int i = begin;
//有一个满足是结束的条件，while循环里要写继续的条件！！！
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++];
//数据还在tmp数组中，需要拷贝回去memcpy
//不是拷整个区间，是begin到end
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail!");
return;
}
_MergeSort(a, tmp, 0, n-1);
free(tmp);
tmp = NULL;
}2、非递归
使用非递归 -- 一开始每两个数归并，然后每四个数归并...把递归倒着看
gap -- 每组归并数据的数据个数(gap是其中一组归并数据的个数)
gap, gap 这样归并，所以数据个数*2
[i, i + gap -1], [gap + i,i + 2*gap - 1]
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)//i代表每组归并的起始位置
{
//[begin1,end1][begin2,end2]
//end = 起点 + 个数 - 1
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + gap * 2 - 1;
printf("[%d, %d] [%d, %d]", begin1, end1, begin2, end2);
//第二组都越界 -- [begin1,end1] n [begin2,end2]
if (begin2 >= n)
{
break;
}
//第二组begin2没越界，end2越界，需要修正一下继续归并 -- [begin1,end1][begin2, (n) end2]
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, (end2 - i + 1) * sizeof(int));
}
gap *= 2;
printf("\n");
}
free(tmp);
tmp = NULL;
}五、各个排序的时间复杂度及稳定性
稳定性指的是相同的值排完后，相对顺序不变
直接插入排序
两层循环
时间复杂度O(N^2)，每次插入大约移动一半元素
最坏时间复杂度O(N^2)，数组完全逆序
稳定，因为插入操作不会改变相同元素的相对顺序
希尔排序
时间复杂度O(N^1.3) - O(N^2)，O(N^1.3)即可
最坏时间复杂度O(N^2)，取决于分组情况gap
不稳定，元素的移动可能跨越多个间隔，导致相同元素相对顺序改变
选择排序
时间复杂度O(N^2)，每次插入大约移动一半元素
最坏时间复杂度O(N^2)，数组完全逆序
不稳定，每次选择最小元素并交换，会改变相同元素的相对顺序
堆排序
时间复杂度O(nlogn)，
最坏时间复杂度O(nlogn)，
由于堆的调整操作，无论输入数组的初始状态如何，时间复杂度不变
不稳定，在调整堆的过程中，会交换元素，可能改变相同元素的相对顺序
冒泡排序
时间复杂度O(N^2)，
最坏时间复杂度O(N^2)，当数组完全逆序时
稳定，相邻元素比较和交换，相同元素不会交换位置
快速排序
时间复杂度O(nlogn)，
最坏时间复杂度O(N^2)，当每次选择的基准元素都为当前子数组中的最大或最小元素时，导致划分极不均衡，递归深度达到最大
不稳定，分区过程中，基准元素的交换可能导致相同元素相对顺序改变
归并排序
时间复杂度O(nlogn)，
最坏时间复杂度O(nlogn)，
无论数组初始状态如何，通过不断将数组对半划分并合并，所以其时间复杂度不会变
稳定，在合并过程中，可以保证相同元素的相对顺序不变
while (begin1 <= end1 && begin2 <=end2)
{
if (a[begin1] <= a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
if中的<=，=可以确保相同值时相对顺序不变(递归非递归都是这个=)
