专业术语

  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
  • 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
  • 时间复杂度： 一个算法执行所耗费的时间。
  • 空间复杂度：运行完一个程序所需内存的大小。

各种算法时间复杂度一览表:

复杂度
图片解释:

  • n: 数据规模
  • k: “桶”的个数
  • In-place: 占用常数内存，不占用额外内存
  • Out-place: 占用额外内存

比较排序和非比较排序优劣对比

  1. 分类:
    • 比较排序: 快速排序、归并排序、堆排序、冒泡排序
    • 非比较排序: 计数排序、基数排序、桶排序
  2. 优劣:
    • 比较排序适用于各种规模的数据，也不在乎数据的分布，都能进行排序。
    • 非比较排序时间复杂度低，比较排序时间复杂度高。
    • 但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

冒泡排序O(n^2)

  1. 比较数组相邻2个数，若顺序不对，则调整顺序，然后对整个数组进行(n-1)次排序。
  2. 冒第一次，则可以选出数组最大数，冒第二次，则可选出第二大，以此类推。
  3. 可以做一个优化，如果一次比较中，没有做任何交换，则表示已经有序，停止继续。原因是两两比较，如果不是已经有序，不可能不交换。
    冒泡

以下均是比较排序:

选择排序O(n^2)

  1. 假设第一个数最小，从其余数里找，如果比第一个数小，则替换。
  2. 以此类推，找出所有最小，则拍完序。
    选择

插入排序

  1. 经过比较，把未排序的元素根据其大小，插入到已排序的相应位置即可。
  2. 核心是说，我跟上一个相比，如果比他小，我就开始在那个数组里面找位置，直到找到最小的地方，就放下。（一次冒泡）
    插入

希尔排序（缩小增量排序）

  1. 特点
    • 改进版的插入排序
    • 非稳定排序
    • 最坏情况有可能比插入排序还慢，因此尽量选择每一轮增量彼此互质。2^k - 1 => O(n^2/3); 4^k - 3*2^k + 1 O(n^3/4)
  2. 使用插入排序升级是因为有如下特征：
    • 数组有序时，操作次数很少（最好复杂度为o(n)可见）
    • 数组较小时候，操作次数少

归并排序

  1. 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
    • 分治法：把一片领土分解，分解为若干块小部分，然后一块块地占领征服。
    • 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并

快速排序

归并