常见算法之排序算法

简介

收集 排序 相关的常见算法

评价维度

• 运行效率：我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。
• 就地性：顾名思义，原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。
• 稳定性：稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格，第 1 列和第 2 列分别是姓名和年龄。在这种情况下，非稳定排序可能导致输入数据的有序性丧失。
• 自适应性：自适应排序能够利用输入数据已有的顺序信息来减少计算量，达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度。
• 是否基于比较：基于比较的排序依赖比较运算符（<、=、>）来判断元素的相对顺序，从而排序整个数组，理论最优时间复杂度为 O(nlog⁡n) 。而非比较排序不使用比较运算符，时间复杂度可达 O(n) ，但其通用性相对较差。

---

理想排序算法：运行快、原地、稳定、自适应、通用性好。

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

选择排序

原理：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

特性：

• 时间复杂度为 O(n^2)、非自适应排序
• 空间复杂度为 O(1)、原地排序
• 非稳定排序

代码实现:

两层遍历，将小的往左边交换

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  selectionSort(list);
  print(list);
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

void selectionSort(List<int> nums) {
  int n = nums.length;
  // 外循环：未排序区间未 [i, n-1]
  for (var i = 0; i < n - 1; i++) {
    // 内循环：找到未排序区间的最小值
    int k = i;
    for (var j = i + 1; j < n; j++) {
      // 记录最小元素索引
      if (nums[j] < nums[k]) k = j;
    }
    // 将该最小元素与未排序区间的首个元素交换
    int temp = nums[i];
    nums[i] = nums[k];
    nums[k] = temp;
  }
}

冒泡排序

原理：通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

特性：

• 时间复杂度为 O(n^2)、自适应排序
• 空间复杂度为 O(1)、原地排序
• 稳定排序

代码实现:

两层遍历，将大的往左边交换

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  bubbleSort(list);
  print(list);
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

// 冒泡排序
void bubbleSort(List<int> nums) {
  // 外循环：未排序区间为 [0,i]
  for (var i = nums.length - 1; i > 0; i--) {
    // 内循环：将未排序区间 [0,i] 中的最大元素交换至该区间的右端
    for (var j = 0; j < i; j++) {
      // 交换 nums[i] 与 nums[j+1]
      if (nums[j] > nums[j + 1]) {
        int tmp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
      }
    }
  }
}

插入排序

原理：我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置

特性：

• 时间复杂度为 O(n^2)、自适应排序
• 空间复杂度为 O(1)、原地排序
• 稳定排序

代码实现:

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  insertionSort(list);
  print(list);
}

// 插入排序
void insertionSort(List<int> nums) {
  // 外循环：已排序区间为 [0,i-1]
  for (var i = 1; i < nums.length; i++) {
    int base = nums[i], j = i - 1;
    // 内循环: 将 base 插入到已排序区间 [0,i-1] 中的正确位置
    while (j >= 0 && nums[j] > base) {
      // 将 nums[j] 向右移动一位
      nums[j + 1] = nums[j];
      j--;
    }
    nums[j + 1] = base;
  }
}

希尔排序（插入排序）

原理：是一种基于插入排序的排序算法，通过先比较较远的元素，再逐步减少间隔，最终转换为普通的插入排序。希尔排序通过使用间隔序列（或称步长）来对数组进行分组排序，减少逆序情况，提高排序效率。

特性：

• 时间复杂度，在最坏情况下（不良步长选择）为 **O(n^2)**，但在最佳情况下可以接近 O(nlogn)
• 空间复杂度为 O(1)、原地排序
• 不稳定排序

代码实现:

void main() {
  // 示例数组
  List<int> arr = [12, 34, 54, 2, 3];
  shellSort(arr);

  // 输出排序后的数组
  print("排序后的数组: $arr");
  // 排序后的数组: [2, 3, 12, 34, 54]
}

// 希尔排序
void shellSort(List<int> arr) {
  int n = arr.length;

  // 选择步长，通常从数组长度的一半开始
  for (var gap = n ~/ 2; gap > 0; gap ~/= 2) {
    // 使用插入排序对每个间隔为 gap 的分组进行排序
    for (var i = gap; i < n; i++) {
      int tmp = arr[i];
      int j;

      // 插入排序，将 arr[i] 插入到合适的位置
      for (j = i; j >= gap && arr[i - gap] > tmp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = tmp;
    }
  }
}

时间复杂度 - O(nlogn)

快速排序

原理：是一种基于分治策略的排序算法，快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

特性：

• 时间复杂度为 O(nlog⁡n)、非自适应排序
• 空间复杂度为 O(n)、原地排序
• 非稳定排序

代码实现:

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  quickSort(list, 0, list.length - 1);
  print(list);
}

// 元素交换
void _swap(List<int> nums, int i, int j) {
  int tmp = nums[i];
  nums[i] = nums[j];
  nums[j] = tmp;
}

// 哨兵划分
int _partition(List<int> nums, int left, int right) {
  // 以 nums[left] 为基数
  int i = left, j = right;
  while (i < j) {
    // 从右向左找首个小于基准数的元素
    while (i < j && nums[j] >= nums[left]) j--;
    // 从左向右找首个大于基准数的元素
    while (i < j && nums[i] <= nums[left]) i++;
    // 交换这两个元素
    _swap(nums, i, j);
  }
  // 将基准数交换至两个子数组的分界线
  _swap(nums, i, left);
  // 返回基准数的索引
  return i;
}

// 快速排序
void quickSort(List<int> nums, int left, int right) {
  // 子数组长度为 1 时终止递归
  if (left >= right) return;
  // 哨兵划分
  int pivot = _partition(nums, left, right);
  // 递归左子数组，右子数组
  quickSort(nums, left, pivot - 1);
  quickSort(nums, pivot + 1, right);
}

优化：

• 基数优化
• 尾递归优化

归并排序

原理：是一种基于分治策略的排序算法，包含“划分”和“合并”阶段。

1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

特性：

• 时间复杂度为 O(nlog⁡n)、非自适应排序
• 空间复杂度为 O(n)、非原地排序
• 稳定排序

代码实现:

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  mergeSort(list, 0, list.length - 1);
  print(list);
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

// 归并排序
void mergeSort(List<int> nums, int left, int right) {
  // 终止条件
  if (left >= right) return; // 当子数组长度为 1 时，终止递归
  // 划分阶段
  int mid = left + (right - left) ~/ 2; // 计算中点
  mergeSort(nums, left, mid); // 递归左子数组
  mergeSort(nums, mid + 1, right); // 递归右子数组
  // 合并阶段
  merge(nums, left, mid, right);
}

// 合并左子数组和右子数组
void merge(List<int> nums, int left, int mid, int right) {
  // 左子数组区间为 [left, mid],右子数组区间为 [mid+1, right]
  // 创建一个临时数组 tmp，用于存放合并后的结果
  List<int> tmp = List.filled(right - left + 1, 0);
  // 初始化左子数组和右子数组的起始索引
  int i = left, j = mid + 1, k = 0;
  // 当左右子数组还有元素时，进行比较并将较小的元素复制到临时数组中
  while (i <= mid && j <= right) {
    if (nums[i] < nums[j]) {
      tmp[k++] = nums[i++];
    } else {
      tmp[k++] = nums[j++];
    }
  }
  // 将左子数组和右子数组的剩余元素复制到临时数组中
  while (i <= mid) {
    tmp[k++] = nums[i++];
  }
  while (j <= right) {
    tmp[k++] = nums[j++];
  }

  // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
  for (var k = 0; k < tmp.length; k++) {
    nums[left + k] = tmp[k];
  }
}

堆排序

原理：是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。

1. 输入数组并建立小顶堆，此时最小元素位于堆顶。
2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

特性：

• 时间复杂度为 O(nlog⁡n)、非自适应排序
• 空间复杂度为 O(1)、原地排序
• 非稳定排序

代码实现:

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  headSort(list);
  print(list);
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

// 堆排序
void headSort(List<int> nums) {
  // 建堆操作：堆化除页节点以外的其他所有节点
  for (var i = nums.length ~/ 2 - 1; i >= 0; i--) {
    shiftDown(nums, nums.length, i);
  }

  // 从堆中提取最大元素，循环 n-1 轮
  for (var i = nums.length - 1; i > 0; i--) {
    // 交换根节点与最右节点（交换首元素和尾元素）
    int tmp = nums[0];
    nums[0] = nums[i];
    nums[i] = tmp;
    // 以根节点为起点，从顶至低进行堆化
    shiftDown(nums, i, 0);
  }
}

// 堆的长度为 n，从节点 i 开始，从顶至低堆化
void shiftDown(List<int> nums, int n, int i) {
  while (true) {
    // 判断节点 i，l，r 中值最大的节点，记为 ma
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int ma = i;
    if (l < n && nums[l] > nums[ma]) ma = l;
    if (r < n && nums[r] > nums[ma]) ma = r;
    // 若节点 i 最大或索引 l， r 越界，则无须继续堆化，跳出
    if (ma == i) break;
    // 交换两节点
    int temp = nums[i];
    nums[i] = nums[ma];
    nums[ma] = temp;
    // 循环向下堆化
    i = ma;
  }
}

时间复杂度 - O(n)

计数排序

原理：通过统计元素数量来实现排序，通常应用于整数数组。

特性：

• 时间复杂度为 O(n+m)、非自适应排序
• 空间复杂度为 O(n+m)、非原地排序
• 稳定排序

代码实现:

// 计数排序
// 简单实现，无法用于排序对象
import 'dart:math';

void main(List<String> args) {
  List<int> list = [1, 3, 6, 7, 2, 4, 5, 10, 9, 8];
  countingSortNaive(list);
  print(list);
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
}

void countingSortNaive(List<int> nums) {
  // 1. 统计数组最大元素 m
  int m = 0;
  for (var _num in nums) {
    m = max(m, _num);
  }
  // 2. 统计各数字的出现次数
  // counter[_num] 代表 _num 的出现次数
  List<int> counter = List.filled(m + 1, 0);
  for (var _num in nums) {
    counter[_num]++;
  }
  // 3. 便利 counter，将元素填入原数组 nums
  int i = 0;
  for (var _num = 0; _num < m + 1; _num++) {
    for (var j = 0; j < counter[_num]; j++, i++) {
      nums[i] = _num;
    }
  }
}

基数排序

原理：核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

特性：

• 时间复杂度为 O(nk)、非自适应排序
• 空间复杂度为 O(n+d)、非原地排序
• 稳定排序

代码实现:

void main(List<String> args) {
  List<int> list = [100, 103, 106, 107, 102, 104, 105, 109, 108];
  radixSort(list);
  print(list);
  // [100, 102, 103, 104, 105, 106, 107, 108, 109]
}

// 获取元素 _num 的第 k 位，其中 exp = 10^(k-1)
int digit(int _num, int exp) {
  // 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
  return (_num ~/ exp) % 10;
}

// 计数排序(根据 nums 第 k 位排序)
void countingSortDigit(List<int> nums, int exp) {
  // 十进制的范围位 0～9， 因此需要长度为 10 的桶数组
  List<int> counter = List<int>.filled(10, 0);
  int n = nums.length;
  // 统计 0~9 各数字的出现次数
  for (var i = 0; i < n; i++) {
    int d = digit(nums[i], exp);
    counter[d]++;
  }
  // 求前缀和，将“出现个数”转换为“数组索引”
  for (var i = 1; i < 10; i++) {
    counter[i] += counter[i - 1];
  }
  // 倒序遍历，根据桶内统计结果，将各元素填入 res
  List<int> res = List<int>.filled(n, 0);
  for (var i = n - 1; i >= 0; i--) {
    int d = digit(nums[i], exp);
    int j = counter[d] - 1; // 获取 d 在数组中的索引 j
    res[j] = nums[i]; // 将当前元素填入索引 j
    counter[d]--; // 将 d 的数量减 1
  }

  // 使用结果覆盖原数组 nums
  for (var i = 0; i < n; i++) nums[i] = res[i];
}

// 基数排序
void radixSort(List<int> nums) {
  // 获取数组的最大元素，用于判断最大位数
  // dart 中 int 的长度是 64 位的
  int m = -1 << 63;
  for (var _num in nums) {
    if (_num > m) m = _num;
  }

  // 按照地位到高位的顺序遍历
  for (var exp = 1; exp <= m; exp *= 10) {
    // 对数组元素的第 k 位执行计数排序
    // k = 1 -> exp = 1
    // k = 2 -> exp = 10
    // 即 exp = 10^(k-1)
    countingSortDigit(nums, exp);
  }
}

桶排序

原理：是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

特性：

• 时间复杂度为 O(n+k)
• 空间复杂度为 O(n+k)、非原地排序
• 桶排序是否稳定取决于排序桶内元素的算法是否稳定。

代码实现:

void main(List<String> args) {
  List<double> list = [0.26, 0.6, 0.49, 0.1, 0.27, 0.93, 0.7, 0.76, 0.95, 0.55];
  bucketSort(list);
  print(list);
  // [0.1, 0.26, 0.27, 0.49, 0.55, 0.6, 0.7, 0.76, 0.93, 0.95]
}

// 桶排序
void bucketSort(List<double> nums) {
  int k = nums.length ~/ 2;
  List<List<double>> buckets = List.generate(k, (index) => []);

  // 1.j将数组元素分配到各个桶中
  for (var _num in nums) {
    // 输入数据范围为 [0,1),使用 _num * k 映射到索引范围 [0, k-1]
    int i = (_num * k).toInt();
    // 将 _num 添加进桶 bucket_idx
    buckets[i].add(_num);
  }

  // 2. 对各个桶执行排序
  for (List<double> bucket in buckets) {
    bucket.sort();
  }

  // 3. 遍历桶合并结果
  int i = 0;
  for (List<double> bucket in buckets) {
    for (double _num in bucket) {
      nums[i++] = _num;
    }
  }
}