目录 冒泡排序： 插入排序 希尔排序： 堆排序： 选择排序 快速排序： 挖坑法： 前后指针法： 左右指针法 快速排序非递归 归并排序： 非递归： 排序总结：
排序是非常重要的内容，一般来说，我们经常用到的也就是十大排序，如图所示
按照比较类和非比较类又可以分为： 
冒泡排序：冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。 作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来
1.1算法描述 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2.动图展示 
3.图解展示： 
4.代码实现： void BubbleSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
}
}
}
}4.冒泡排序的优化： 如果我们的冒泡排序比较了一圈之后发现没有发生交换，说明此时已经有序了。我们就可以退出循环。
void BubbleSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int flag = 1;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
flag = 0;
swap(a[j], a[j + 1]);
}
}
if (flag) {
break;
}
}
}5.复杂度分析 时间复杂度：O（N^2) 若数组为倒序，即所有的轮次都必须执行完（最坏情况），比较次数为 n-1 + n-2 +...+ 1 = n(n-1)/2，交换次数与比较次数相同，所以时间复杂度为O(N^2)。 空间复杂度:O(1) 稳定性：插入排序是稳定的排序算法，满足条件nums[j] > nums[j + 1]才发生交换，这个条件可以保证值相等的元素的相对位置不变
插入排序插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。 按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1.1算法描述： 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）
2.2 动图展示 
3.图解展示： 
4.代码实现： void Insert(int* a, int n)
{
for (int i = 0; i < n - 1; i++) {
int j = 0;
int tmp = a[i + 1];
for (j = i; j >= 0 && tmp < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = tmp;
}
}或者也可以这样写，这样写逻辑更清晰： void Insert(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;
}
}5.复杂度分析： 希尔排序：希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
1.算法描述： 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 按增量序列个数 k，对序列进行 k 趟排序； 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
2.2动图展示： 
3.图解展示： 
或者： 
4.代码实现： void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++) {
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;
}
}
} 5.复杂度分析： 1、时间复杂度：O(N^2)
希尔排序最坏的时间复杂度依然为 O ( N 2 )
但其能够有效改善直接插入排序序列无序且长度大时的大长度数列移位。希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能，本文使用的是希尔增量，还有 Hibbard 增量，时间复杂度为 O(N^1.5) 也可以认为是O ( N^log N)空间复杂度：O(1)
未借助其它辅助空间。 稳定性分析：
与直接插入排序不同，希尔排序中的分组插入可能导致顺序移位。 所以，插入排序是稳定的排序算法。
堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
1.算法描述： ① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列 先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素。
再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
直到无序区只有一个元素为止。
2.动图展示： 
3.图解展示： 1.预备知识： 堆的结构可以分为大根堆和小根堆，是一个完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆
2.大根堆和小根堆： 性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如下图
对应成数组便是：
3.堆的一些基本性质： 查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么 1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数） 2.左孩子索引：2*i+1 3.右孩子索引：2*i+2 所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质： 大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2) 小根堆：arr(i)<arr(2*i+1) &&="" arr(i)<arr(2*i+2)
4.堆的构造 将无序数组构造成一个大根堆（升序用大根堆，降序就用小根堆） 假设存在以下数组
主要思路：第一次保证0~0位置大根堆结构（废话），第二次保证0~1位置大根堆结构，第三次保证0~2位置大根堆结构...直到保证0~n-1位置大根堆结构（每次新插入的数据都与其父结点进行比较，如果插入的数比父结点大，则与父结点交换，否则一直向上交换，直到小于等于父结点，或者来到了顶端） 插入6的时候，6大于他的父结点3，即arr(1)>arr(0)，则交换；此时，保证了0~1位置是大根堆结构，如下图：
插入8的时候，8大于其父结点6，即arr(2)>arr(0),则交换；此时，保证了0~2位置是大根堆结构，如下图
插入5的时候，5大于其父结点3，则交换，交换之后，5又发现比8小，所以不交换；此时，保证了0~3位置大根堆结构，如下图
插入7的时候，7大于其父结点5，则交换，交换之后，7又发现比8小，所以不交换；此时整个数组已经是大根堆结构
此时，我们已经得到一个大根堆，下面将顶端的数与最后一位数交换，然后将剩余的数再构造成一个大根堆
此时最大数8已经来到末尾，则固定不动，后面只需要对顶端的数据进行操作即可，拿顶端的数与其左右孩子较大的数进行比较，如果顶端的数大于其左右孩子较大的数，则停止，如果顶端的数小于其左右孩子较大的数，则交换，然后继续与下面的孩子进行比较 下图中，5的左右孩子中，左孩子7比右孩子6大，则5与7进行比较，发现5<7，则交换；交换后，发现5已经大于他的左孩子，说明剩余的数已经构成大根堆，后面就是重复固定最大值，然后构造大根堆
|
