几种常用排序算法

1 基本概念

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

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

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

  2 选择排序

  

  遍历两层，复杂度较高

  3 插入排序

  

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

  4 希尔排序

  

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

  5 冒泡排序

  

  复杂度比选择排序好一些

  6 快速排序

  

  几个做法：

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

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

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

  

  思路：

  大原则（跟前面一样）：用一个Key来分割所有数据成为“