几种常用排序算法

1 基本概念

排序是处理数据的一种最常见的操作，所谓排序就是将数据按某字段规律排列，所谓的字段就是数据节点的其中一个属性。比如一个班级的学生，其字段就有学号、姓名、班级、分数等等，我们既可以针对学号排序，也可以针对分数排序。

• 稳定性 在一组无序数据中，若两个待排序字段一致的数据，在排序前后相对位置不变，则称排序算法是稳定的，否则是不稳定的。（应该是原先有序的在排序中会不会出现改变）

• 内排序与外排序 如果待排序数据量不大，可以一次性全部装进内存进行处理，则称为内排序，若数据量大到无法一次性全部装进内存，而需要将数据暂存外存，分批次读入内存进行处理，则称为外排序。

2 选择排序

遍历两层，复杂度较高

3 插入排序

减少队列和构建新的队列，新的队列插入算法可以优化。

4 希尔排序

插入排序的升级版，一开始分成几组，每组内部排序，逐步减少分组数量。

5 冒泡排序

复杂度比选择排序好一些

6 快速排序

几个做法：

两端往中间走：在l>k>r时交换；

挖坑移树法：也是两端往中间走，将Key位腾出来，存放L和R碰到的大和小的数据，

前后指针（交换小的在前）：如图，重点讲，是前面两种做法的进化版，目前也是用的比较多的。

思路：

大原则（跟前面一样）：用一个Key来分割所有数据成为“<K<”，然后继续前后分别递归继续；

分割时：用一个cur游标，从头找到尾，找出小的数据放到“后面队列”，用一个Prev（后面队列的车头）来推动大的数据将cur发现的小数交换到后面。