排序

什么是排序

排序(Sort), 就是重新排列表中的元素,使表中的元素满足按关键字有序的过程.

输入: n各记录$R_1, R2, … R_n$,对应的关键字为$k_1, k_2, … , k_n$

输出: 输入序列的一个重排$R_1^{‘},R_2^{‘},…,R_n^{‘},$,使得有$k_1^{‘}<k_2^{‘}<,,,<k_n^{‘}$(也可以递减)

算法的稳定性

关键字相同的元素相对位置排序后不变,称之为稳定.

分类

  • 内部排序: 数据都在内存中—>关注时间复杂度,空间复杂度
  • 外部排序: 数据太多,无法全部被存入内存—> 关注I/O次数

概览

排序算法 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 稳定 优点 缺点 适用场景
冒泡排序 O(n) O(n²) O(n²) O(1) 是 简单，稳定；可检测有序性优化 效率低，交换次数多 小数据或接近有序的数据
选择排序 O(n²) O(n²) O(n²) O(1) 否 原地排序，交换次数少 比较次数多，不稳定 数据量小，交换成本高
插入排序 O(n) O(n²) O(n²) O(1) 是 稳定，适合小数据或部分有序 数据量大时效率低 小数据或基本有序的数据
希尔排序 O(n log n) O(n²) O(n^1.3) O(1) 否 改进的插入排序，中等规模高效 时间复杂度依赖步长序列 中等规模数据，权衡时间与空间
快速排序 O(n log n) O(n²) O(n log n) O(log n)（平均） 否 平均最快，原地排序 最坏情况差，不稳定 通用大规模数据，需优化基准选择
归并排序 O(n log n) O(n log n) O(n log n) O(n) 是 稳定，时间复杂度可靠 需额外空间 大数据，需稳定排序且内存足够
堆排序 O(n log n) O(n log n) O(n log n) O(1) 否 原地排序，时间复杂度稳定 缓存不友好，不稳定 需原地排序且避免快排最坏情况
计数排序 O(n + k) O(n + k) O(n + k) O(n + k) 是 非比较排序，数据范围小时极快 依赖数据范围，仅适用于整数/有限类型 小范围整数（如年龄、成绩排序）
基数排序 O(nk) O(nk) O(nk) O(n + k) 是 稳定，适合整数/字符串 需额外空间，对数据类型有要求 非比较排序，元素有固定基数（如数字、字符）
桶排序 O(n + k) O(n²) O(n + k) O(n + 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
function insertSort(arr) {
  // 第一个记录已经排好,因为只有它一个
  // 从第二个开始
  for (let i = 1; i < arr.length; i++) {
    // 记录当前值,方式被覆盖
    const current = arr[i];
    // 从当前值的前一位开始,如果大于当前值,则后移一位
    let j = i - 1;
    // 边界条件是数组开头
    while (j >= 0 && arr[j] > current) {
      // 将大于当前值的记录后移一位
      arr[j + 1] = arr[j];
      // 指针前移一位
      j--;
    }
    // 插入当前值
    arr[j + 1] = current;
  }
}
// 测试
let arr = [3, 4, 2, 1, 5, 6, 7, 8];
console.time();
insertSort(arr);
console.log(arr);
console.timeEnd();

// [
//   1, 2, 3, 4,
//   5, 6, 7, 8
// ]
// default: 1.196s
  • 空间复杂度: O(1)
  • 时间复杂度:
    • 最好情况:本来是有序的,共n-1趟处理,每次处理只需对比当前值和前一位的值,发现前一位的值小于当前值后,便不再对比.即每趟对比一次.所以共需要对比n-1此,时间复杂度为$O(n)$
    • 最坏情况:$O(n^2)$
    • 平均复杂度: $O(n^2)$
  • 稳定性: 稳定

C语言版本:

1

优化: 折半插入排序

思路: 先用折半查找找到应该插入的位置,再移动元素.

当low > high时,折半查找停止,应将[low, i-1]内的元素全部右移一位,并将current复制到low所指的位置,当arr[mid] === current时,为了保证排序算法的稳定性,应该把它当做arr[mid] < current,即要继续让low=mid+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
function insertPlusSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // 从下标为1开始遍历
    // 保存当前值防止被覆盖
    const current = arr[i];
    // 折半查找插入位置
    let low = 0; 
    let high = i - 1;
    while (low <= high) {
      let mid = (low + high) >> 1;
      if (arr[mid] <= current) {
        low = mid + 1;
      }else {
        high = mid - 1;
      }
    }
    // [low,i-1]的所有数都右移一位
    for (let j = i - 1; j >= low; j--) {
      arr[j + 1] = arr[j];
    }
    // 将当前值插入low位置
    arr[low] = current;
  }
}

// 测试
let arr = [3, 4, 2, 1, 5, 6, 7, 8];
console.time();
insertPlusSort(arr);
console.log(arr);
console.timeEnd();

// Debugger attached.
// [
//   1, 2, 3, 4,
//   5, 6, 7, 8
// ]
// default: 6.676ms