算法之美-排序

发表于 | 分类于 | 热度 | 字数统计 7,778

排序对于任何一个程序员来说，可能都不会陌生。你学的第一个算法可能就是排序，大学里的 C 入门就是写的它吧？排序是非常重要的，但是排序算法太多了，有很多可能你连名字都没听说过，比如猴子排序、睡眠排序、面条排序等。
我这里就只看最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

排序算法 时间复杂度 是否基于比较
冒泡、插入、选择 O(n^2) 是
快排、归并 O(nlogn) 是
桶、计数、基数 O(n) 否

算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）就是特指空间复杂度是 O(1) 的排序算法，可以理解为不需要开辟很多空间的算法。

然后还有一个稳定性的概念，简单说就是排序前后，相等的元素还是原来的顺序不变，这个性质其实很重要，实际中我们都是对对象的某个属性排序，如果还能保证顺序就省事很多。
比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？
借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。
两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

实际上，刚讲的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static void bubbleSort(int[] arr) {
  int size = arr.length;
  if (size <= 1) return;

  for (int i = 0; i < size - 1; i++) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < size - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        // 表示有数据交换
        flag = true;
      }
    }
    // 没有数据交换，提前退出
    if (!flag) break;
  }
}

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

对于一个给定的初始序列，移动操作的次数总是固定的。

插入排序

描述下过程就是：首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间；
初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
重复这个过程，直到未排序区间中元素为空，算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void insertionSort(int[] arr) {
  int size = arr.length;
  if (size <= 1) return;

  for (int i = 1; i < size; i++) {
    // 要插入的数
    int value = arr[i];
    // 有序区间的末尾
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (arr[j] > value) {
        arr[j + 1] = arr[j];  // 数据移动
      } else {
        break;
      }
    }
    // 插入数据
    arr[j + 1] = value;
  }
}


// 熟练后 for 循环可以简化：
while (j >= 0 && array[j] > key) {
  array[j + 1] = array[j];
  j--;
}

for (; j >= 0 && arr[j] > temp; j-- ) {
  arr[j + 1] = arr[j];
}

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

对于一个给定的初始序列，移动操作的次数总是固定的。

为什么插入更受欢迎

把他们循环的最多次的代码拿出来比较下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

// 插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

不要小看少的这两句语句，在数据量大的时候，就能带来显著的差距，所以尽量做到极致的话当然会选择插入排序，另外，如果喜欢插入排序，可以看看极致的改进版：希尔排序，不过它是非稳定的。

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void selectionSort(int[] data) {
  int temp;
  // 只循环到倒数第二个即可，最后一个没数可比
  for (int i = 0; i < data.length - 1; i++) {
    for (int j = i + 1; j < data.length; j++) {
      if (data[i] > data[j]) {
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
      }
    }
  }
}

这里要说明一下，选择排序是一种原地排序算法，但不是稳定的排序算法。

归并排序

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
这就是分治思想，分而治之，跟递归思想有点像。

然后重点说下将两个已经有序的数组拼装起来，我们可以先申请一个临时数组 tmp，大小与原数组 A 相同。我们用两个游标 i 和 j，分别指向 A[p…q] 和 A[q+1…r] 的第一个元素。
比较这两个元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我们就把 A[i] 放入到临时数组 tmp，并且 i 后移一位，否则将 A[j] 放入到数组 tmp，j 后移一位。
直到其中一个子数组中的所有数据都放入临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class MergeSort {

  // 归并排序算法, a是数组，n表示数组大小
  public static void mergeSort(int[] a, int n) {
    mergeSortInternally(a, 0, n - 1);
  }

  // 递归调用函数
  private static void mergeSortInternally(int[] a, int p, int r) {
    // 递归终止条件
    if (p >= r) return;

    // 取p到r之间的中间位置q,防止（p+r）的和超过int类型最大值
    int q = p + (r - p) / 2;
    // 分治递归
    mergeSortInternally(a, p, q);
    mergeSortInternally(a, q + 1, r);

    // 将A[p...q]和A[q+1...r]合并为A[p...r]
    merge(a, p, q, r);
  }

  private static void merge(int[] arr, int s1, int middle, int arrEnd) {
    int start1 = s1;
    int start2 = middle + 1;

    // 申请一个大小跟a[p...r]一样的临时数组
    int[] tmp = new int[arrEnd - s1 + 1];
    // 临时数组的索引
    int k = 0;

    while (start1 <= middle && start2 <= arrEnd) {
      if (arr[start1] <= arr[start2]) {
        tmp[k++] = arr[start1++];
      } else {
        tmp[k++] = arr[start2++];
      }
    }

    // 判断哪个子数组中有剩余的数据，默认设为第一个剩余
    int start = start1;
    int end = middle;
    if (start2 <= arrEnd) {
      // 改变为第二个剩余
      start = start2;
      end = arrEnd;
    }

    // 将剩余的数据拷贝到临时数组tmp
    while (start <= end) {
      tmp[k++] = arr[start++];
    }

    // 将tmp中的数组拷贝回a[p...r]
    for (start1 = 0; start1 <= arrEnd - s1; ++start1) {
      arr[s1 + start1] = tmp[start1];
    }
  }
}

它是稳定的算法，只要保证合并时稳定就好了。
它不是原地排序算法，所以快排更加出名一些，即使它的最好情况下的时间复杂度要优于快排。

快速排序

快排利用的也是分治思想，乍看和归并差不多，其实思想还是有差别的，快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
当区间缩小为 1 的时候就可以认为它有序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class QuickSort {

  // 快速排序，a是数组，n表示数组的大小
  public static void quickSort(int[] a, int n) {
    quickSortInternally(a, 0, n - 1);
  }

  // 快速排序递归函数，p,r为下标
  private static void quickSortInternally(int[] a, int p, int r) {
    if (p >= r) return;

    int q = partition(a, p, r); // 获取分区点
    quickSortInternally(a, p, q - 1);
    quickSortInternally(a, q + 1, r);
  }

  private static int partition(int[] a, int p, int r) {
    int pivot = a[r];
    int left = p;
    for (int right = p; right < r; ++right) {
      if (a[right] < pivot) {
        if (left == right) {
          ++left;
        } else {
          int tmp = a[left];
          a[left++] = a[right];
          a[right] = tmp;
        }
      }
    }

    // 交换 pivot，返回缩小后区间的最后一个（新 pivot）
    int tmp = a[left];
    a[left] = a[r];
    a[r] = tmp;

    System.out.println("i=" + left);
    return left;
  }
}

快排并不是一个稳定的算法，它是一个原地排序算法；
可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

快排 B 站有个视频讲的不错：https://www.bilibili.com/video/av39093184

桶排序

桶排序，顾名思义，会用到“桶”，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

他的时间复杂度是 O(n)，只不过对数据的要求比较苛刻。
首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。
理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

如果数据不能平均分，集中在一个桶里，为了避免时间复杂度的退化，那么你只能继续拆分。

计数排序

计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
计数排序的算法思想就是这么简单，跟桶排序非常类似，只是桶的大小粒度不一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 计数排序，arr 是数组，size 是数组大小。假设数组中存储的都是非负整数。
public static void countingSort(int[] arr, int size) {
  if (size <= 1) return;

  // 查找数组中数据的范围
  int max = arr[0];
  for (int i = 1; i < size; ++i) {
    if (max < arr[i]) {
      max = arr[i];
    }
  }

  // 申请一个计数数组 countArr，下标大小 [0,max]，初始化为 0
  int[] countArr = new int[max + 1];
  for (int i = 0; i <= max; ++i) {
    countArr[i] = 0;
  }

  // 计算每个元素的个数，放入 countArr 中
  for (int i = 0; i < size; ++i) {
    countArr[arr[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    countArr[i] = countArr[i - 1] + countArr[i];
  }

  // 临时数组 temp，存储排序之后的结果
  int[] temp = new int[size];
  // 计算排序的关键步骤
  for (int i = size - 1; i >= 0; --i) {
    int index = countArr[arr[i]] - 1;
    temp[index] = arr[i];
    countArr[arr[i]]--;
  }

  // 将结果拷贝给 arr 数组
  System.arraycopy(temp, 0, arr, 0, size);
}

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数（小数就先乘以倍数，负数就先加成正数）。

例如，对 50 万考生的成绩排名，假设满分是 900 最低是 0，数据范围很小，可以搞 901 个桶，然后将这些考试分布进这些桶里，并不需要排序，只需要扫描，时间复杂度是 O(n)。

基数排序

我们再来看这样一个排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
对于手机号，再用之前的桶排序就不合适了，因为它太大了，刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。
借助稳定排序算法，这里有一个巧妙的实现思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。
不过要保证在每一位的排序中，算法要是稳定的。
每一位的排序就可以用上面的桶排序了~这样时间复杂度也是 O(n).

那么对于不等长的数据怎么排序（字符串为例）？我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据 ASCII 码，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序（O(n)）算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

堆排序

堆排序是一种原地的、不稳定的、时间复杂度为 O(nlogn) 的排序算法，甚至堆排序比快速排序的时间复杂度还要稳定，但是，在实际的软件开发中，快速排序的性能要比堆排序好。

什么是堆

堆是一种特殊的树，只要满足这两点，它就是一个堆：

  • 堆是一个完全二叉树；
  • 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

第一点，堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。
对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

关于树的介绍，我之前写过一篇，点我跳转

实现一个堆

完全二叉树比较适合用数组来存储，用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。
为了方便计算，通常会把数组的 1 号索引作为根，也就是前面空一个，数组中下标为 i 的节点的左子节点，就是下标为 i∗2 的节点，右子节点就是下标为 i∗2+1 的节点，父节点就是下标为 i/2 的节点。

通过调整，让其满足堆的特性的过程就叫“堆化”，堆化实际上有两种，从下往上和从上往下；
例如从下往上的，先插入到数组的最后，然后与父节点比较，不符合规则就交换，然后再跟父节点比较，直到合适为止。
删除的话也有一个巧妙的方法，直接把最后一个替换到删除的元素上，然后进行调整。

实现堆排序

首先，我们需要将数组原地建成一个堆，思路这里说一种，假设数组 size 是 10，编号就是 0-9：
我们从后面开始，按照规律 8、9 所对应的父节点的索引是 4，所以我们比较 4 是不是比 8 和 9 的数大，如果小就交换最大的；
然后继续找 6、7 对应的父节点 3，它们三个再比较，重复上面的步骤，最终就形成了符合规律的树，也就是堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
// 需要注意，此算法数组需要空出第一个元素来
public static void sort(int[] a, int n) {
  buildHeap(a, n);
  int k = n;
  while (k > 1) {
    swap(a, 1, k);
    --k;
    heapify(a, k, 1);
  }
}

private static void buildHeap(int[] a, int n) {
  for (int i = n / 2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
    if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

private static void swap(int[] arr, int a, int b) {
  int temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。
有点类似删除操作，然后最大的就找出来了，依次往前，最终1就是个从小到大的有序数组了。

总结&应用

至于说为什么堆排序不如快排效率高，可以从两点来说：
堆排序数据访问的方式没有快速排序友好，因为不是顺序访问，Cpu 缓存表示很无奈。
对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序，就算是原本有序的数组，在堆化过程也会打乱的。

  • 优先级队列
    在优先级队列中，就不是先进先出了，用堆来实现是最直接、最高效的。这是因为，堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。
    很多时候，它们只是概念上的区分而已。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。

  • 利用堆求 Top K
    我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。
    如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
    这样每次只需要跟堆顶数比较即可，因为它肯定是全堆最小的。

  • 利用堆求中位数
    对于静态数据，当然数组求一下最好了，也不会变；如果是动态数据：
    我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。
    也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 n/2 个数据存储在大顶堆中，后 n/2 个数据存储在小顶堆中。
    如果 n 是奇数，情况是类似的，大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2 个数据。
    这样，大顶堆中的堆顶元素就是我们要找的中位数。

    下面就是插入新数据了，如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；如果新加入的数据大于等于小顶堆的堆顶元素，我们就将这个新数据插入到小顶堆。
    这个时候就有可能出现，两个堆中的数据个数不符合前面约定的情况，这个时候，我们可以从一个堆中不停地将堆顶元素移动到另一个堆，通过这样的调整，来让两个堆中的数据满足上面的约定。
    例如将小顶堆的堆顶元素移动到大顶堆的堆顶。

举几个例子，合并有序小文件的时候，我们可以从很多小文件先取第一个，构建一个小顶堆，每次从堆顶取出最小的放入合并后的文件，再找到这个元素来自那个文件读取下一个。
定时任务的时候，为了避免频繁扫描，可以根据时间来构造小顶堆，这样就知道最早执行的时间，避免多余的扫描。

PS：最后中位数说的那个约定：如果 n 是偶数，两个堆中的数据个数都是 n/2；如果 n 是奇数，大顶堆有 n/2+1 个数据，小顶堆有 n/2 个数据。

其他

如果对小规模数据进行排序，可以选择时间复杂度是 O(n^2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。

例如在 JDK8 中，排序函数并不是仅仅使用一种算法，在元素小于 47 的时候用插入排序，大于 47 小于 286 用双轴快排，大于 286 用 timsort 归并排序，并在 timesort 中记录数据的连续的有序段的的位置，若有序段太多，也就是说数据近乎乱序，则用双轴快排，当然快排的递归调用的过程中，若排序的子数组数据数量小，用插入排序。

娱乐时间

下面就来给看看猴子排序、睡眠排序、面条排序（太蠢不说 2333），别笑。。。

睡眠排序

构造 n 个线程，它们和这 n 个数一一对应。初始化后，线程们开始睡眠，等到对应的数那么多个时间单位后各自醒来，然后输出它对应的数。这样最小的数对应的线程最早醒来，这个数最早被输出。等所有线程都醒来，排序就结束了。能脑洞大开想出此算法的，绝壁天才啊。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 如果只需要输出
public class SleepSort {  
  public static void main(String[] args) {  
    int[] arr = {1,4,7,3,8,9,2,6,5};
    //创建指定长度的线程数组
    SortThread[] sortThreads = new SortThread[arr.length];  
    //指定每个线程数组的值
    for (int i = 0; i < sortThreads.length; i++) {  
      sortThreads[i] = new SortThread(arr[i]);  
    } 
    //开启每个线程
    for (int i = 0; i < sortThreads.length; i++) {  
      sortThreads[i].start();  
    }  
  }  
}

class SortThread extends Thread{  
  int s = 0;  
  public SortThread(int s){  
    this.s = s;  
  }  
  public void run(){  
    try {  
      sleep(s*10+10);  //睡眠指定的时间
    } catch (InterruptedException e) {  

      e.printStackTrace();  
    }  
    //输出该数
    System.out.println(s);  
  }  
} 


// 就算需要拿到顺序的数组，也有办法
public class SleepSort {
  public static void main(String[] args){
    int[] nums={9,7,2,6,15,8};
    SleepSort.sort(nums);
    for(int n:nums)
      System.out.printf("%d   ",n);
  }

  public static void sort(int[] nums){
    Sleeper.idx=0;
    Sleeper.output=new int[nums.length];
    for(int i=0;i<nums.length;i++)
      new Sleeper(nums[i]).start();
    try {
      // 主线程需要睡足够的时间，等他们都排好
      // 当然可以使用其他 join、循环检查等方法
      Thread.sleep(100);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    for(int i=0;i<nums.length;i++)
      nums[i]=Sleeper.output[i];
  }
}

class Sleeper extends Thread{
  public static int[] output;
  public static int idx;

  private int sleep_time;

  public Sleeper(){
    this.sleep_time=0;
  }
  
  public Sleeper(int sleep_time){
    this.sleep_time=sleep_time;
  }
  
  @Override
  public void run(){
    try{
      Thread.sleep(this.sleep_time);
    }catch(InterruptedException e){
      e.printStackTrace();
    }
    output[idx++]=this.sleep_time;
  }
}

猴子排序

随机打乱数组，检查是否排好序，若是，则输出，否则再次打乱，再检查…最佳情况 O(n)，平均 O(n*n!)，最坏可执行直到世界的尽头。
无限猴子定理 ：一只猴子随机敲打打字机键盘，如果时间足够长，总是能打出特定的文本，比如莎士比亚全集。
用伪代码表示很简洁：

1
2
while(! isOrdered(nums))
    shuffle(nums);
喜欢就请我吃包辣条吧！

评论框加载失败，无法访问 Disqus

你可能需要魔法上网~~