这么感觉我都忘了

排序

关于时间复杂度：

  • 平方阶 (O(n2))(O(n^2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
  • 线性对数阶 (O(nlog2n))(O(n log2n)) 排序: 快速排序、堆排序 和 归并排序；
  • O(n1+§))O(n1+§)) 排序，(§ 是介于 0 和 1 之间的常数): 希尔排序
  • 线性阶 (O(n))(O(n)) 排序: 基数排序，此外还有桶、箱排序。

关于稳定性：

  • 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

  • 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

冒泡排序

冒泡排序是一种简单直观的排序算法。重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

算法步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  3. 针对所有的元素重复以上的步骤，除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示

注意

  • 什么时候最快
    当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

  • 什么时候最慢
    当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  3. 重复第二步，直到所有元素均排序完毕。

动图演示

插入排序

算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）

动图演示

希尔排序

希尔排序是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

算法步骤

  1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

  2. 按增量序列个数 k，对序列进行 k 趟排序；

  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动图演示

举例

  1. 原始数组：8，9，1，7，2，3，4，5，6，0
  2. 初始增量：length/2=5，意味整个数组被分成5组，分别为[8,3] [9,5] [1,4] [7,6] [2,0]
  3. 进行直接插入排序：结果为：3,5,1,6,0,8,9,4,7,2
  4. 缩小增量： length/2/2=2，整个数组被分成两组，分别为[3,1,0,9,7] [5,6,8,4,2]
  5. 再进行直接插入排序: 结果为：0,2,1,4,3,5,7,6,9,8
  6. 继续缩小增量： 达到最小增量1，再进行一次插入排序就可以得到有序数组

归并排序

归并排序是建立在归并操作上的一种有效的排序算法

算法步骤

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

  4. 重复步骤 3 直到某一指针达到序列尾；

  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

算法思想

分而治之

  1. 假设现在有一组数：[8，4，5，7，1，3，6，2]
  2. 先将这一组数按照对半分的思想，分成[8,4,5,7],[1,3,6,2] 两组
  3. 继续对分成 [8,4],[5,7],[1,3],[6,2]
  4. 继续分成单个的数

上面已经将这组数“分”开，然后再“治”

  1. 两两比较，排序
  2. [4,8],[5,7],[1,3],[2,6]
  3. [4,5,7,8],[1,2,3,6]
  4. [1,2,3,4,5,6,7,8]

动图演示

快速排序

快速排序应该算是在冒泡排序基础上的递归分治法

在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来

算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

动图演示