参考

精简归纳：https://www.drflower.top/posts/6a923688/

入门图解：

https://blog.csdn.net/weixin_50651363/article/details/120070517

https://blog.csdn.net/kexuanxiu1163/article/details/103051357

内部排序

冒泡排序

我们先固定队尾。进行多次遍历，每一次遍历途中两两比较、两两交换，直到确定到最后1位。下一次还是从头开始遍历，但是之确定到倒数第2位…直到第1位为止。

可以优化，如果某次遍历产生了0次交换，那么可以提前结束遍历。比如排序有序数组时，一次遍历就结束了。

选择排序

我们先固定队头。将队列分为2个部分，前面是排序完的部分、后面是待排序部分，每一次遍历都是去找待排序部分的最小值，放到排序完部分的队尾。

Q:冒泡排序与选择排序哪个效率高？
A:两者时间复杂度都时候O(n)，但冒泡排序在内存循环交换，选择排序在外循环交换，一般而言选择排序效率更高。

插入排序

我们先固定队头。将队列分为2个部分，前面是即刻排序完的部分、后面是待排序部分，每一次遍历都是去待排序部分取第一个数字，保持插入后仍然有序地插入到前面的部分中。

希尔排序

插入排序的改进。选定一个整数增量序列：{a1,a2,…,1}，其中最大的a1<=list.Count()，最小为1。

这里为了理解选取好1/2序列，也就是{count/2,count/4,…,1}。然后每隔count/2的数为一组进行排序，会分割成很多个内部不相邻的队列，分别对他们进行插入排序。

归并排序

分治思想。简单来说就是，两两分组+指针。

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.重复步骤 3 直到某一指针达到序列尾。

按上面的操作，进行递归，两两分组直至每一组都是1个数，不能再分为止。

快速排序

也是分治思想。简单来说就是，基准值+2个指针，让L指针左侧的数永远小于基准值、让R指针右侧的数永远大于基准值。

1.先选定一个基准值povit，然后放2个指针Left和Right到最左和最右。

2.对比L指针的值和povit，如果L小就是合理的，L指针右移，直至大于povit再停止；

3.当L指针停止后，开始移动R指针，如果R指向的值大就是合理的，R指针左移，直至小于povit再停止。

4.如果L和R都停止了，那么就将L、R指向的值互换，之后重启第2步继续右移L。

5.在2、3步中，如果发现L指针已经和R指针重合了，那么就证明本次分治下的排序结束。之后把L指针的值和povit的值进行交换就可以。

在上述完成后，最终结果会变成povit放在某个确定位置，而这个位置左侧的元素都小于povit，右边的元素都大于povit。所以这其实是在确定povit的最终位置。之后继续同样操作来排序povit左侧和右侧的2个队列，直至无可划分。

优化：1.想办法让povit取到中值（三数中值法）

更细的步骤拆分和优化点

堆排序

这个排序本身很简单，难点在于将堆用数组表现出来。所以分2部分说。

用数组表示堆

堆：一个完全二叉树。完全二叉树就是从上到下、从左到右，直到最后一个结点为止，没有一个结点是空着的二叉树。
大顶堆：一个堆，每个节点都能保证父>子。小顶堆：一个堆，每个节点都能保证父<子。
shift_down(结点k)：一个用来确定结点位置的方法。将结点k和它的2个孩子中的最大值做位置交换，然后让它继续和孩子比较，直至它比2个孩子都大。

从堆的概念可以直到，你可以对堆从上到下、从左到右进行编号，编成0,1,2,…,n。这刚好对应着下标。而某个结点k的2个孩子，刚好对应结点2k+1、2k+2。

堆排序

对数组化后的堆H[0……n-1]进行操作。

1.排出一个大顶堆；

2.把堆顶和堆尾交换，然后调用shift_down(0)来确保这还是一个大顶堆；

3.再把换到堆尾（也就是最大数）的那个数移除出堆，放到一个临时队列的尾部。堆结点数量-1。

重复1-3直至最后一个结点被移除。这个临时队列就是最终的排序结果。

外部排序

外部排序是指内存中无法直接完成的大数据排序。是一种分治思想，当分到能在内存中排序的大小之后，再对其用内部排序。

桶排序

把数组遍历一遍，取出min和max值，将其范围划分为n个桶。桶内用内部排序排完之后，再把每个桶按顺序串起来。

计数排序

计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

1.找出序列中最大值和最小值，开辟Max-Min+1的辅助空间。
2.最小的数对应下标为0的位置，遇到一个数就给对应下标处的值+1。
3.遍历一遍辅助空间，就可以得到有序的一组序列。

基数排序

排序先把所有数字位数统一，不够的在前面用0补齐。

然后从后往前，一位一位的排，直至第一位。注意，放的时候先放，拿的时候也先拿，这样才能保持顺序，具体看动画吧。