参考

精简归纳: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部分说。

用数组表示堆

  1. 堆:一个完全二叉树。完全二叉树就是从上到下、从左到右,直到最后一个结点为止,没有一个结点是空着的二叉树。
  2. 大顶堆:一个堆,每个节点都能保证 父>子。 小顶堆:一个堆,每个节点都能保证 父<子。
  3. 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补齐。

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

时间复杂度