《数据结构与算法之美》基础篇笔记（二）

摘要：极客时间《数据结构与算法之美》基础篇笔记，冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序
常见排序算法时间复杂度

递归

递归需要满足的三个条件：
1、一个问题的解可以分解为几个子问题的解
2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3、存在递归终止条件
递归的关键是要写出递归公式，找到终止条件。遇到递归，要把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
递归代码简洁高效，但是要警惕堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等。可以将已经求解过得值保存下来，后面的计算先看下是否有对应的结果，这样可以避免重复计算

排序

排序算法的关注点：
一、排序算法的执行效率
1、最好情况、最坏情况、平均情况时间复杂度。要排序的数据有的有序，有的无序，为了更好的对比就全部区分下
2、时间复杂度的系数、常数 、低阶。在实际的软件开发中，排序的数据规模比较小，因而也要考虑这些因素
3、比较次数和交换（或移动）次数。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动
二、排序算法的内存消耗
内存消耗可以通过空间复杂度来衡量。空间复杂度是 O(1) 的排序算法被称为原地排序
三、排序算法的稳定性
如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
稳定性举例：订单排序，希望优先按金额从小到大排序，同金额的按时间从早到晚排序。先按照时间排序，然后借助稳定性算法按照金额排序。因为稳定性算法不会将相同金额的订单更换位置，所以相同金额的订单仍然是时间早的在前面，时间晚的在后面

冒泡排序（Bubble Sort）

冒泡排序只会操作相邻的两个数据，判断这两个值是否满足大小关系要求，不满足就交换。sort.js

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
// java 冒泡排序，a 表示数组，n 表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
  for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j + 1]) { // 交换
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

// js
function bubbleSort(arr) {
  if (arr.length <= 1) return
  for (let i = 0; i < arr.length; i++) {
    let hasChange = false
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
        hasChange = true
      }
    }
    // 如果 false 说明所有元素已有序
    if (!hasChange) break
  }
}

冒泡每次操作只涉及到相邻元素操作，只需要常量级的临时空间，空间复杂度为 O(1)，是原地排序算法。
当两个相邻数据不满足大小关系时才交换位置，如果两个值相等则不交换，是稳定排序算法。
最好情况下，数据是有序的，只需要一次冒泡操作即可结束，时间复杂度为 O(n)。最坏情况下，数据刚好是倒序排列，时间复杂度为 O(n^2)。平均时间复杂度需要结合概率论知识计算，还可以通过“有序度”和“逆序度”这两个概念来进行分析

有序度和逆序度

有序度是数组中具有有序关系的元素对的个数。用数学表达式表示：

1
有序元素对：a[i] <= a[j], 如果 i < j

比如要排序数组的初始状态为4，5，6，3，2，1，有序元素对有 (4，5) (4，6)(5，6)，有序度为3
一个完全有序的数组的有序度叫满有序度，比如1，2，3，4，5，6，有序度为 n*(n-1)/2 => 15
逆序度的定义正好跟有序度相反（默认从小到大为有序）。用数学表达式表示：

1
逆序元素对：a[i] > a[j], 如果 i < j

可以得到一个公式：逆序度 = 满有序度 - 有序度
泡排序包含两个操作原子：比较和交换。每次交换有序度都会 +1，逆序度是确定的，所以交换次数也是确定的，如上例中交换次数为 15-3=12
对于包含 n 个数据的数组进行排序，最好情况下，有序度为 n(n-1)/2，不需要交换。最坏情况下，有序度为 0，需要 n(n-1)/2 次交换。取个中间值需要 n(n-1)/4 次交换，而比较操作更多，两个 for 循环遍历比较的复杂度上限为 O(n^2)，所以平均时间复杂度为 O(n^2)

插入排序（Insertion Sort）

插入算法的核心思想：将数组分为已排序区间和未排序区间，初始已排序区间只有数组的第一个元素，然后取未排序区间的元素在已排序区间找到合适位置插入，并保证已排序区间的数据一直有序。重复这个过程，直到未排序区间数据为空。
插入排序包含比较和移动两种操作，对于不同的的查找插入方法（从头到尾，从尾到头）的比较次数是有区别的，但是一个给定的初始序列，移动操作的次数是固定的，等于其逆序度。sort.js

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
// java 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;
  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      // 从小到大排序，前者大则交换
      if (a[j] > value) {
        a[j+1] = a[j];
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

// js
function insertionSort(arr) {
  if (arr.length <= 1) return
  for (let i = 1; i < length; i++) {
    let value = arr[i]
    let j = i - 1
    // 若 arr[i] 前有大于arr[i]的值的化，向后移位，腾出空间，直到一个 <=arr[i] 的值
    while (j >= 0) {
      if (arr[j] > value) {
        arr[j + 1] = arr[j] // 移动
        j--
      } else {
        break
      }
    }
    // for (j; j >= 0; j--) {
    //   if (arr[j] > temp) {
    //     arr[j + 1] = arr[j]
    //   } else {
    //     break
    //   }
    // }
    arr[j + 1] = value // 插入数据
  }
}

插入排序不需要额外的存储空间，空间复杂度为 O(1)，是原地排序算法。对于值相同元素，我们可以选择将后面出现的元素插入到前面出现元素的后面，所以是稳定的排序算法
最好情况下，数据已经是有序的，这样每次只需比较一次即可确认要插入的位置，从头到尾遍历一次，时间复杂度为 O(n)。最坏情况下，所有数据是倒序排列，每次插入都相当于在序列第一个位置上插入，时间复杂度为 O(n^2)。插入排序的每次插入操作都相当于在数组中插入一个数据，需要执行 n 次，数组的插入平均时间复杂度为 O(n)，则插入排序的平均时间复杂度为 O(n^2)。插入排序比冒泡排序的赋值交换操作少：冒泡交换数据需要三个，插入需要一个

选择排序（Selection Sort）

选择排序也分已排序区间和未排序区间，但每次排序都会从未排序区间找到最小元素并将其放到已排序区间的末尾。sort.js

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
// java 选择排序，a 表示数组，n 表示数组大小
public void selectionSort(int[] a, int n) {
  if (n <= 1) return;
  for (int i = 0; i < n - 1; ++i) {
    // 查找最小值
    int minIndex = i;
    for (int j = i + 1; j < n; ++j) {
      if (a[j] < a[minIndex]) {
        minIndex = j;
      }
    }

    // 交换，将最小值排到有序区间末尾
    int tmp = a[i];
    a[i] = a[minIndex];
    a[minIndex] = tmp;
  }
}

// js
function selectionSort (arr)  {
  if (arr.length <= 1) return
  // 需要注意这里的边界, 因为需要在内层进行 i+1 后的循环，所以外层需要 数组长度 -1
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j // 找到整个数组的最小值
      }
    }
    // 交换位置
    const temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }
  return 
}

选择排序的空间复杂度为 O(1)，是一种原地排序算法。最好、最坏、平均情况时间复杂度都为 n(n^2)，不管是不是有序的都需要从头进行遍历并且每次都要找到最小值。每次遍历都会找到无序区间的最小值并发生位置交换，无法保证相等数值的相对位置不变，因而选择排序不是一种稳定排序算法。冒泡、插入、选择排序的平均时间复杂度都为 O(n^2)，比较高，适合小规模的数据排序

归并排序（Merge Sort）

归并排序的核心思想是分治思想：将数据分成两组，两组分别排序，最后再整合在一起。分治算法一般都是用递归来实现的。归并排序的处理过程是由下到上的，先处理子问题，然后再合并

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// 伪代码：归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return
  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}
merge(A[p...r], A[p...q], A[q+1...r]) {
  var i := p，j := q+1，k := 0 // 初始化变量i, j, k
  var tmp := new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
  while i<=q AND j<=r do {
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++等于i:=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }
  // 判断哪个子数组中有剩余的数据
  var start := i，end := q
  if j<=r then start := j, end:=r
  // 将剩余的数据拷贝到临时数组tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }
  // 将tmp中的数组拷贝回A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

// java：归并排序算法, a 是数组，n 表示数组大小
public void mergeSort(int[] a, int n) {
  mergeSortInternally(a, 0, n-1);
}
// 递归调用函数
public 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);
}
public void merge(int[] a, int p, int q, int r) {
  int i = p;
  int j = q+1;
  int k = 0; // 初始化变量 i, j, k
  int[] tmp = new int[r-p+1]; // 申请一个大小跟a[p...r]一样的临时数组
  while (i<=q && j<=r) {
    if (a[i] <= a[j]) {
      tmp[k++] = a[i++]; // i++等于i:=i+1
    } else {
      tmp[k++] = a[j++];
    }
  }
  // 判断哪个子数组中有剩余的数据
  int start = i;
  int end = q;
  if (j <= r) {
    start = j;
    end = r;
  }
  // 将剩余的数据拷贝到临时数组tmp
  while (start <= end) {
    tmp[k++] = a[start++];
  }
  // 将tmp中的数组拷贝回a[p...r]
  for (i = 0; i <= r-p; ++i) {
    a[p+i] = tmp[i];
  }
}

// js
function mergeSort(arr) {
  // 当任意数组分解到只有一个时返回。
  if (arr.length <= 1) return arr
  const middle = Math.floor(arr.length / 2) // 找到中间值
  const left = arr.slice(0, middle) // 分割数组
  const right = arr.slice(middle)
  // 递归 分解 合并
  return mergeArr(mergeSort(left), mergeSort(right))
}
function mergeArr(left, right) {
  let temp = []
  let leftIndex = 0
  let rightIndex = 0
  // 判断2个数组中元素大小，依次插入数组
  while (left.length > leftIndex && right.length > rightIndex) {
    if (left[leftIndex] <= right[rightIndex]) {
      temp.push(left[leftIndex])
      leftIndex++
    } else {
      temp.push(right[rightIndex])
      rightIndex++
    }
  }
  // 合并多余数组
  return temp.concat(left.slice(leftIndex),right.slice(rightIndex))
}

对比合并两个有序数组时，如果有相同的元素，将前面数组的数据先放到新数组中，这样保证相同元素的前后顺序不变。也就说这样的归并排序的是稳定的排序算法。
归并算法的时间复杂度比较复杂，递归部分的复杂度可以表示为

1
T(a) = T(b) + T(c) + K

解决问题 a 的时间是 T(a)，解决分解后问题 b、c 的时间为 T(b)、T(c)，K 为将子问题 b、c 结果合并为 a 结果消耗的时间。
假设对 n 个数据归并排序的时间为 T(n)，那么分解成两个子数组排序的时间都为 T(n/2)，合并两个有序数组的时间复杂度为 O(n)，那么归并排序的时间复杂度为

1
2
T(1) = C // n = 1 时不用排序，耗时为常量级用 C 表示
T(n) = 2 * T(n/2) + n  // n > 1

根据这个公式一步一步分解推导可得：

1
2
3
4
5
T(n) = 2 * T(n/2) + n
     = 2 * (T(n/4) + n/2) + n
     = 2 * (2 * (T(n/8) + n/4) + n/2) + n
     ......
     = 2^k* T(n/2^k) + k * n

当 T(n/2^k) = T(1) 时，得到 k = log2(n)，将 k 值带入公式得到 T(n) = nC + nlog2(n)，则时间复杂度为 O(nlogn)。归并排序的时间复杂度与原始数据的有序度无关，最好、最坏与平均时间复杂度均为 O(nlogn)，但归并排序不是原地排序算法：递归合并时只有一个函数在运行，函数中申请的临时内存空间最多有 n 个数据大小，因此空间复杂度为 O(n)，也因此应用不广泛

快速排序（Quicksort)

快排也是利用分治思想：一组数据从中间选择任意一个数据作为 pivot 分区点，遍历数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。这样将数据分成三部分，然后根据分治、递归的思想，将两侧的数据再次分别递归排序，直到区间缩小为 1，则说明数据都排有序了。如果不考虑空间消耗，分区函数可以很简单：申请两个临时数组分别拷贝大于 pivot 和小于 pivot 的数据，最后将两个数组中的数据顺序拷贝到原始数组中。但这样快速排序就不是原地排序，可以换一种方法：交换。交换不仅减少额外的空间，而且比插入的速度更快。快排的处理过程是由上到下的，先分区，然后再处理子问题，跟归并排序正好相反

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
// 伪代码，A是数组，n表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 递归函数 p、r 为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}
// 原地分区函数
partition(A, p, r) {
  pivot := A[r]
  i := p
  for j := p to r-1 do {
    if A[j] < pivot {
      swap A[i] with A[j]
      i := i+1
    }
  }
  swap A[i] with A[r]
  return i
}

// js
function swap(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

// 获取 pivot 交换完后的 index
function partition(arr, pivot, left, right) {
  const pivotVal = arr[pivot]
  let startIndex = left
  for (let i = left; i < right; i++) {
    if (arr[i] < pivotVal) {
      swap(arr, i, startIndex)
      startIndex++
    }
  }
  swap(arr, startIndex, pivot)
  return startIndex
}

// 传入数组及对应的起止索引
function quickSort(arr, left, right) {
  if (left < right) {
    let pivot = right
    let partitionIndex = partition(arr, pivot, left, right)
    quickSort(arr, left, partitionIndex - 1 < left ? left : partitionIndex - 1)
    quickSort(arr, partitionIndex + 1 > right ? right : partitionIndex + 1, right)
  }
}

快排是一种原地排序算法，但它并不是一种稳定算法，因为分区的过程中涉及交换，假如两个相同切比 pivot 大的值都在比 pivot 小的值前面，前面一个相同的值可能会与后面一个小于 pivot 的值进行交换：6(1)、8、7、6(2)、3、5、9、4，一次分区后变成:3、4、7、6(2)、6(1)、5、9、8。
如果每次选择的 pivot 都正好能将数组分成大小相近的两小区间个，那么快排的时间复杂度递推公式与归并排序是一样的，时间复杂度也是 O(nlogn)，也是最好情况时间复杂度。但如果数组是已经有序的，且每次选择最后（最大）的那个元素作为 pivot，那么每次分区都是不均等的。这样大约需要 n 次分区操作，每次都是将最后一个元素分开，平均每次分区要遍历大约 n/2 个元素，此时快排的时间复杂度为 O(n^2)，也是最快情况时间复杂度。快排在大部分情况下的时间复杂度都可以做到 O(nlogn)，只在极端情况下才会退化到 O(n^2)
问题：O(n) 时间复杂度内求无序数组中的第 K 大元素。利用分治和分区的思想，选择数组区间 A[0…n-1]的最后一个元素 A[n-1] 作为 pivot，对数组 A[0…n-1] 原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。如果 p+1 = K，那 A[p] 就是要求解的元素，如果 K > p+1, 说明第 K 大元素出现在 A[p+1…n-1] 区间，如果 K < p+1，那我们就在 A[0…p-1]区间查找。按照这个思路递归查找即可。遍历需要的时间： n + n/2 + n/4 + … + 1 = 2n - 1，则时间复杂度为 O(n)。另一种方法：遍历数组每次将最小值放到前面，执行 K 次即可找到，但这样做的时间复杂度为 O(K*n)，当 K 比较小时，与前一个方法性能差不多，但是当 K 比较大为 n/2 时，时间复杂度就是 O(n^2) 了

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
// 第 K 大的数
function kthNum(arr, K) {
  const len = arr.length;
  // 判断 K 是否在数组内
  if (K > len) {
    return -1;
  }
  let p = partition(arr, 0, len - 1);
  while (p + 1 !== K) {
    if (p + 1 > K) {
      p = partition(arr, 0, p - 1);
    } else {
      p = partition(arr, p + 1, len - 1);
    }
  }
  return arr[p];
}

// 获取分组后第 k 大的数所在区间的起始或终止索引
function partition(arr, start, end) {
  let i = start;
  let pivot = arr[end];
  for (let j = start; j < end; j++) {
    if (arr[j] < pivot) {
      swap(arr, i, j);
      i += 1;
    }
  }
  swap(arr, i, end);
  return i;
}

// 交换
function swap(arr, i, j) {
  if (i === j) return;
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

桶排序（Bucket sort）

桶排序核心思想：将数据分配到几个有序的桶里，每个桶里的数据再单独排序，之后把数据按照顺序顺序依次取出组成有序序列。桶排序的时间复杂度为 O(n)，原理：n 个数据平均分配到 m 个桶中，每个桶分到 k = n/m 个数据。每个桶使用快排，时间复杂度为 O(k * logk)，m 个桶的时间复杂度为 O(m * k * logk) = O(n * log(n/m))，当 m 非常接近 n 时，桶排序的时间复杂度就接近 O(n)
桶排序的要求非常苛刻：
1、数据要很容易就能划分成 m 个桶，而且桶于桶之间有着天然的大小关系
2、数据在每个桶的分布是比较均匀的，极端情况下分配到一个桶里的时间复杂度就退化成 O(nlogn)

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
// 将数组中的数据，按桶进行划分，将相邻的数据划分在同一个桶中，每个桶用快排或插排算法进行排序，最后整合每个桶中的数据
function bucketSort(array, bucketSize = 5) {
	if (array.length < 2) {
		return array
	}
	const buckets = createBuckets(array, bucketSize)
	return sortBuckets(buckets)
}

// 分桶处理数据
function createBuckets(array, bucketSize) {
  let minValue = array[0]
  let maxValue = array[0]
  // 遍历数组，找到数组最小值与数组最大值
  for (let i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i]
    } else if (array[i] > maxValue) {
      maxValue = array[i]
    }
  }
  // 根据最小值、最大值、桶的大小，计算得到桶的个数
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
  // 建立一个二维数组，将桶放入buckets中
  const buckets = []
  for (let i = 0; i < bucketCount; i++) {
    buckets[i] = []
  }
  // 计算每一个值应该放在哪一个桶中
  for (let i = 0; i < array.length; i++) {
    const bucketIndex = Math.floor((array[i] - minValue) / bucketSize)
    buckets[bucketIndex].push(array[i])
  }
  return buckets
}

// 合并桶数据方法
function sortBuckets(buckets) {
  const sortedArray = []
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i] != null) {
      insertionSort(buckets[i])
      sortedArray.push(...buckets[i])
    }
  }
  return sortedArray
}

// 插入排序
function insertionSort(arr) {
  const { length } = arr // 数组解构赋值
  if (length <= 1) return
  for (let i = 1; i < length; i++) {
    let value = arr[i]
    let j = i - 1
    while (j >= 0) {
      if (arr[j] > value) {
        arr[j + 1] = arr[j] // 移动
        j--
      } else {
        break
      }
    }
    arr[j + 1] = value // 插入数据
  }
}

桶排序比较适合用在外部排序中，即数据存储在外部磁盘，数量大而内存有限，无法将所有数据加载到内存中。例如将 10G 的订单数据按照金额大小排序，而内存没有这么大。此时，现将数据扫描一遍，获取到金额范围，然后按照金额范围平均划分到 100 个区间（桶）里。理想情况下金额是均匀分布，但实际上是小金额的订单较多。小金额的订单范围继续划分为更小的区间，直到所有的文件都可以读入内存。进入内存后用快排排序，最后再按从小到大的照顺序依次读取每个区间的订单数据并存入一个文件，这样文件中的订单数据就是按金额大小排序的

计数排序（Counting sort）

计数排序更像是桶排序的一种特殊情况。当排序 n 个数据，所处的范围并不大，比如从 0 到 k，可以划分成 k+1 个桶，每个桶内的数据都是相同的，省掉了桶内排序的时间。
计数排序主要是使用一个数组来计数：数组 A = [2, 5, 3, 0, 2, 3, 0, 3]，要对 A 从小到大排序可以这么做： 0 到 5 划分 6 个桶，桶内数据个数由数组 B 表示，则 B = [2, 0, 2, 3, 0, 1]。对 B 数组顺序求和得到数组 C = [2, 2, 4, 7, 7, 8]，数组 C 即为小于等于当前元素的数值个数。此时，遍历数组 A，先取到 2，对应数组 C 中的 C[2]，即小于等于 2 的数值有 4 个，把 2 放到新数组 D 的第 4 的位置后 C[2] 减 1，表示还有 3 个小于等于 2 的数值。遍历完数组 A 后得到的数组 D = [0(A[6]), 0(A[3]), 2(A[4]), 2(A[0]), 3(A[7]), 3(A[5]), 3(A[2]), 5(A[1])] 即为排序后的数据，此时数组 B = [0, 2, 2, 4, 7, 7]。利用数组 B 来计算对应元素的个数（位置）就是计数算法

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
// java 计数排序，a 是数组，n 是数组大小
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

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

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

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

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

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

  // 将结果拷贝给a数组
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

// js 没有生成数组 C，直接使用数组 B 对数组进行排序
function countingSort(array){
  if (array.length <= 1) return

  // 获取最大值，用以生成对应长度的数组 B
  const max = findMaxValue(array)
  const counts = new Array(max + 1)

  // 计算每个元素的个数，放入到 counts 桶中（即数组 B），补充数组 B 的内容
  // counts 下标是元素，值是元素个数
  array.forEach(element => {
    if (!counts[element]) {
      counts[element] = 0
    }
    counts[element]++
  })

  // i 是元素, count 是元素个数，遍历数组 B 给新数组 array 赋值
  let sortedIndex = 0
  counts.forEach((count, i) => {
    while (count > 0) {
      array[sortedIndex] = i
      sortedIndex++
      count--
    }
  })
  // 返回排序后的数组
  return array
}

// 查找最大值
function findMaxValue(array) {
  let max = array[0]
  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i]
    }
  }
  return max
}

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。因为计数排序只能用于非负整数排序，所以排序的数据必须都处理成不改变相对大小的非负整数。比如：有两位小数的数据需要先乘以 100 转化成整数再排序；数据范围是 [-100, 100] 的先加 100 转化为非负数再排序

基数排序（Radix sort）

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，按照每位来排序的排序算法要是稳定的。每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n)。比如：10 万个手机号码排序，使用快排的时间复杂度为 O(nlogn)。借助稳定排序算法，从后向前分别排序。每一位的排序都可以使用桶排序或者计数排序，这样时间复杂度为 O(n)，需要 k 次排序就是 O(k * n)。手机号共 11 位，时间复杂度接近 O(n)。如果字符并不都一样长的话，可以使用 0 将短字符补齐到长字符，因为所有字符的 ASCII 值都比 0 大。
有些排序问题可以不使用排序算法就可以排序，比如：对 D，a，F，B，c，A，z 这个字符串进行排序，所有小写字母在前，大写字母在后，但大小写字母内部不要求有序。如果还有数字，要求数字在两者之间怎么办？
方法：使用 a、b 两个指针，a 指针从前向后遍历，遇到大些字母停下，b 指针从后向前遍历，遇到小写字母停下，然后交换 a、b 指针对应的元素。重复操作直到两个指针相交。有数字时，将数字和小写字母归为一类，将其与大些字母分开，然后再遍历一次将小写字母和数字排序。具体过程：a 指针仍是从前向后遍历，遇到大写字母停下，但 b 指针是遇到小写字母或者数字停下，交换两者对应元素，a、b 指针相交后，此时小写字母和数字在前，大些字母在后。然后再次遍历 a 指针遇到数字停下，b 指针遇到小写字母停下，交换指针对应元素，a、b 指针再次相交后，此时的字符串就是小写字母在前，数字在中间，大些字母在后

排序优化

实现一个通用的、高性能的 排序函数，先看几种排序算法的特性：

时间复杂度稳定排序原地排序
冒泡排序O(n²)是是
插入排序O(n²)是是
选择排序O(n²)否是
快速排序O(nlogn)否是
归并排序O(nlogn)是否
桶排序O(n)是否
计数排序O(k+n)k是数据范围是否
基数排序O(dn)d是维度是否
虽然线性排序算法的时间复杂度比较低，但是其适用场景比较特殊，要写一个通用的排序算法，不能适用线性排序。对于小规模数据进行排序，可以使用时间复杂度为 O(n²) 的算法，但是对于大规模数据进行排序，使用 O(nlong) 的算法更加高效。为了兼容任意规模数据的排序，一般首选时间复杂度为 O(nlogn) 的排序算法来实现。堆排序和快速排序应用比较多，但归并排序由于空间复杂度为 O(n) 应用比较少。但是快速排序在最坏情况下的时间复杂度为 O(n²)，我们需要一些方法来优化。快速排序 O(n²) 时间复杂度的原因是分区点选的不合理造成的，优化快速排序的要从分区点着手： 1、三数取中法。从首、尾、中间分别取一个点，三者比较大小，选取中间值作为分区点。如果数据很多，可以改为“五数取中”或者“十数取中”。这样每隔固定长度取出的数进行比较得到的分区点，肯定比单纯取某一个数据更好； 2、随机法。每次从要排序的区间内随机抽取一个元素作为区分点，不能保证每次分区点都很好，但从概率的角度来讲，每次分区点也不会都很差，平均情况下分区点还比较好。 快排还有另外一个问题：快排递归时要警惕内存溢出。为了避免快排递归过深而堆栈过小，导致堆栈溢出，有两种解决方法： 1、限制递归深度，一旦递归超过了我们设置的阈值，就停止递归 2、在堆上模拟实现一个函数调用栈，手动模拟入栈、出栈的过程，这样就没有系统栈大小的限制

C 中的 qsort()函数

qsort() 会优先使用归并排序来排序输入的函数，因为归并排序的空间复杂度为 O(n)，对于小数据量的排序，比如 1、2kb，用空间换取时间问题不大。但是要排序的数据量比较大时时候，qsort() 会改为快速排序算法来排序，同时采用“三数取中法”选择分区点，并在堆上模拟栈避免递归过深导致的内存溢出问题。实际上，当要排序的区间中元素个数小于等于 4 时，qsort() 就退化为插入排序并利用哨兵简化代码。在小规模数据面前，O(n²) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长，因为 O(nlogn) 是省略了低阶、系数、常数的，在没有省略之前是 O(knlogn + c)，而 k 和 c 有可能还是比较大的数。因此，对于小规模数据的排序，一般选择简单、不需要递归的插入排序算法。

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

持续学习