技术文档排序算法

排序算法

算法

内容

https://visualgo.net/zh/sorting

排序时间复杂度总结

冒泡排序

Bubble Sort

给定一个 N 个元素的数组，冒泡排序将：

比较一对相邻元素（a，b），
如果两项的大小关系不正确，交换这两个数（在本例中为a > b），
重复步骤1和2，直到我们到达数组的末尾（最后一对是第 N-2 和 N-1 项，因为我们的数组从零开始）
到目前为止，最大项将在最后的位置。然后我们将 N 减少1，并重复步骤1，直到 N = 1。

method bubbleSort(array A, integer N) // 标准版本
  for each R from N-1 down to 1 // 重复 N-1 次迭代
    for each index i in [0..R-1] // '未排序区域'，O(N)
      if A[i] > A[i+1] // 这两个不是非递减顺序
        swap(a[i], a[i+1]) // 在 O(1) 中交换它们

时间复杂度 O(N^2)->O(N)

比较和交换需要的时间由一个常数限制，我们称之为 c。然后，在（标准）冒泡排序中有两个嵌套循环。外循环正好运行 N-1 次迭代。但是内循环的运行时间越来越短：

当 R=N-1 时，(N−1) 次迭代（比较和交换），
当 R=N-2 时，(N−2) 次迭代， ...，
当 R=1 时，1 次迭代（然后完成）。因此，总的迭代次数 = (N−1)+(N−2)+...+1 = N*(N−1)/2 总时间 = cN(N−1)/2 = O(N^2).

改进：如果我们在内循环中没有交换，那就意味着数组已经排序，我们可以在那个点停止冒泡排序。（对于有序数组时间复杂度是O(N)) 讨论：尽管这使冒泡排序在一般情况下运行得更快，但这个改进的想法并没有改变冒泡排序的O(N^2)时间复杂度...为什么呢？

选择排序

Selection Sort O(N^2)

给定 N 个项目和 L = 0 的数组，选择排序将：

在 [L ... N-1] 范围内找出最小项目 X 的位置，
用第 L 项交换第 X 项，
将下限 L 增加1并重复步骤1直到 L = N-2。

method selectionSort(array A[], integer N)
  for each L in [0..N-2] // O(**N**)
    let X be the index of the minimum element in A[L..N-1] // O(**N**)
    swap(A[X], A[L]) // O(1)，X 可能等于 L (没有实际交换)

插入排序

Insertion Sort

从第二张牌开始，手里只拿一张牌，将其插入到前面正确的排序位置，
对所有牌重复上一步。

method insertionSort(array A[], integer N)
  for i in [1..N-1] // O(N)
    let X be A[i] // X is the next item to be inserted into A[0..i-1]
    for j from i-1 down to 0 // this loop can be fast or slow
      if A[j] > X
        A[j+1] = A[j] // make a place for X
      else
        break
    A[j+1] = X // insert X at index j+1

时间复杂度 O(N)-O(N^2)

外循环执行 N-1 次，这很明显。但内循环执行的次数取决于输入：

在最好的情况下，数组已经排序并且 (a [j]> X) 总是为假。所以不需要移位数据，并且内部循环在O（1）时间内运行，
在最坏的情况下，数组被反向排序并且 (a [j]> X) 总是为真。插入始终发生在数组的前端，并且内部循环在O（N）时间内运行。

因此，最佳情况时间是O(N × 1) = O(N) ，最坏情况时间是O(N × N) = O(N2).

归并排序

分治法

分而治之算法（Divide and Conquer，缩写为D＆C）通过以下步骤解决（某种类型的）问题 - 比如我们的排序问题：

划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
解决步骤：结合较小的子问题的结果来解决较大的原始问题。

Merge Sort

归并并排序是分而治之的排序算法。划分步骤很简单：将当前数组分成两半（如果 N 是偶数，则将其完全平等，或者如果 N 是奇数，则一边多一项），然后递归地对这两半进行排序。

method mergeSort(array A, integer low, integer high)
  // 要排序的数组是 A[low..high]
  if (low < high) // 基本情况：low >= high (0 或 1 个项目)
    int mid = (low+high) / 2
    mergeSort(a, low  , mid ) // 分成两半
    mergeSort(a, mid+1, high) // 然后递归排序它们
    merge(a, low, mid, high) // 征服：合并子程序

method merge(array A, integer low, integer mid, integer high)
  // 子数组1 = a[low..mid], 子数组2 = a[mid+1..high], 都已排序
  int N = high-low+1
  create array B of size N // 讨论：为什么我们需要一个临时数组b？
  int left = low, right = mid+1, bIdx = 0
  while (left <= mid && right <= high) // 合并过程
    if (A[left] <= A[right])
      B[bIdx++] = A[left++]
    else
      B[bIdx++] = A[right++]
  while (left <= mid)
    B[bIdx++] = A[left++] // 剩余部分，如果有的话
  while (right <= high)
    B[bIdx++] = A[right++] // 剩余部分，如果有的话
  for (int k = 0; k < N; ++k)
    A[low+k] = B[k]; // 复制回去

时间复杂度 O(log N)

第一层：20 = 1 次调用 merge( )，每次包含 N / 21 个项目，时间复杂度 O（20 x 2 x N / 21）= O(N) 第二层：21 = 1 次调用 merge( )，每次包含 N / 22 个项目，时间复杂度 O（21 x 2 x N / 22）= O(N) 第三层：22 = 1 次调用 merge( )，每次包含 N / 23 个项目，时间复杂度 O（22 x 2 x N / 23）= O(N) ... 第 log N 层：2 ^（log N-1）（或N / 2）调用merge( ) ），其中N / 2 ^ log N（或1）个项目，O（N）第 log N 层：2logN - 1 = 1 次调用 merge( )，每次包含 N / 2logN （或1）个项目，时间复杂度 O（22 x 2 x N / 23）= O(N)

共计有 log N 层，每层工作量都为 O(N) ，因此总体时间复杂度为 O(N log N)。

稍后我们会看到这是在基于比较的排序算法中最佳的一种，即我们无法做得比这更好。

优缺点

优点

无论输入的原始顺序如何，归并排序中最重要的部分是其O（N log N）性能保证。就这样，没有任何针对性的测试用例可以使归并排序对于N个元素数组运行比O（N log N）更长的时间。因此，归并排序非常适合大数组的排序，因为O（N log N）比前面讨论的O（N2）排序算法增长得慢得多。

缺点

然而，归并排序有几个不太好的部分。首先，从零开始实现并不容易（虽然我们不必这样做）。其次，它在归并操作期间需要额外的O（N）内存。(空间复杂度比较高？) 顺便说一句，如果你有兴趣看看为解决这些（经典）归并排序不那么好的部分做了什么，你可以阅读这个。

快速排序

快速排序是另一个分而治之的排序算法。快速排序的分治步骤与归并排序完全相反

Quick Sort

划分步骤：选择第一个项目p（称为枢轴）然后将A[i..j]的项目划分为三部分：A[i..m-1]，A[m]和A[m+1..j]。

A[i..m-1]（可能为空）包含小于（或等于）p的项目。
A[m] = p，即，索引m是数组a排序顺序中p的正确位置。
A[m+1..j]（可能为空）包含大于（或等于）p的项目。然后，递归排序这两部分。

method quickSort(array A, integer low, integer high)
  if (low < high)
    int m = partition(a, low, high) // O(N)
    // A[low..high] ~> A[low..m–1], pivot, A[m+1..high]
    quickSort(A, low, m-1); // 递归排序左子数组
    // A[m] = pivot 在分区后已经排序
    quickSort(A, m+1, high); // 然后排序右子数组

int partition(array A, integer i, integer j)
  int p = a[i] // p 是枢轴
  int m = i // S1 和 S2 最初为空
  for (int k = i+1; k <= j; ++k) // 探索未知区域
    if ((A[k] < p) || ((A[k] == p) && (rand()%2 == 0)))  { // 情况 2+3
      ++m
      swap(A[k], A[m]) // 交换这两个索引
    // 注意我们在情况 1: A[k] > p 时不做任何事情
  swap(A[i], A[m]) // 最后一步，交换枢轴和 a[m]
  return m // 返回枢轴的索引

时间复杂度

在partition(A, i, j)中，只有一个for循环，它迭代了(j-i)次。由于j可以大到N-1，i可以小到0，所以partition的时间复杂度是O(N)。快速排序的时间复杂度取决于partition(A, i, j)被调用的次数。

最坏情况

第一次分区需要 O(N) 的时间，将 A 分为 0, 1, N-1 个项目，然后向右递归。第二次分区需要 O(N-1) 的时间，将 A 分为 0, 1, N-2 个项目，然后再次向右递归。 ... 直到最后，第 N 次分区将 A 分为 0, 1, 1 个项目，快速排序递归停止。

这是经典的 N+(N-1)+(N-2)+...+1 模式，它是 O(N^2)

最好情况（极少）

当分区总是将数组分成两个相等的一半时，就会发生快速排序的最佳情况，如归并排序。当发生这种情况时，递归的深度只有 O(log N)。由于每个级别进行 O(N) 比较，时间复杂度为 O(N log N)。

随机快速排序

与快速排序相同，除了在执行分区算法之前，它随机选择A[i..j]之间的枢轴，而不是总是确定性地选择A[i]（或[i..j]之间的任何其他固定索引）。

计数排序

假设：如果要排序的项目是小范围的整数，我们可以计算每个整数（在这个小范围内）的出现频率，然后通过循环该小范围来有序输出各项。

用上面的 [1...9] 范围内的示例数组中尝试 Counting Sort，因此我们只需要计算整数1出现的次数，整数2出现的次数，...，整数9出现的次数，然后遍历1到9。如果整数 y 的频率为 x，则打印出整数 y 的 x 个副本。

计算频率时间复杂度为 O(N)，有序输出结果的时间复杂度为 O(N + k)，其中 k 是输入的整数范围，在本例中为 9-1+1 = 9。计数排序（Counting Sort）的时间复杂度为 O(N + k)，如果 k 很小，那么它就是 O(N)。

由于内存限制，当 k 相对较大时，我们将无法执行计数排序（Counting Sort）的计数部分，因为我们需要存储 k 个整数出现的次数。

基数排序

假设：如果要排序的项目是具有大范围但少位数的整数，我们可以将计数排序的思想与基数排序相结合，以实现线性时间复杂度。

在基数排序中，我们将要排序的每个项目视为一个由w位数字组成的字符串（如果需要，我们会在位数少于w位的整数前面填充零）。

从最低有效位（最右边）到最高有效位（最左边），我们遍历N个项目，并根据当前位将它们放入10个队列中（每个数字[0..9]一个队列），这类似于一个_修改过的_计数排序