木易

# Road Map

升级路线：

  • 模板题：912

  • 数组排序：15 -> 18

  • 快速排序：215 -> 786

  • 归并排序：493 -> 315 -> 327

  • 桶排序：1122 -> 164

  • 堆排序（即优先队列）：

    • 前 K 个最大的数：347 ->
    • 贪心：56 -> 252

# 排序算法

我们常说八大排序算法，实际上排序有非常多的算法

这里我们列举常用排序算法极其应用进行说明：

# 板子题

# 快排

快排的思想：递归+分治

不稳定排序，中间交换过程会打乱顺序

时间复杂度：最差 O(N^2)，平均 O(N^logN)

# 算法 1

  1. 取中点为轴（也可以选择其他点）
  2. 找到左边第一个大于等于轴的元素 A，找到右边第一个小于等于轴的元素 B
  3. 当 A 的下标小于 B 的下标时，交换
  4. 递归上述过程
void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1]; // 定义左右游标+轴
    while (i < j) {
        do i++; while (q[i] < x); // 找到左边第一个大于等于轴的位置
        do j--; while (q[j] > x); // 找到右边第一个小于等于轴的位置
        if (i < j) swap(q[i], q[j]); // 交换
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);  // 递归；注意这里要以j为基准（或者用i—1，i）防止出现死循环
}
1
2
3
4
5
6
7
8
9
10

# 算法 2

此算法更为直观

  • 选择一个轴（pivot），下标 i, j,通过不断移动下标、比较、交换，使得轴左边所有数据小于轴，右边所有数据大于轴；
  • 递归进行上述过程，直到所有数列长度为 0 或 1，排序结束；
  • 由于每次迭代过程，至少有一个值（轴）排好序，所以最终算法会终止；
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int l =0, r= nums.size()-1;
        recursive(nums, l, r);
        return nums;
    }
    void recursive(vector<int>& nums, int l, int r){
        if (l >= r) return;
        int pivot = partition(nums, l, r);
        recursive(nums, l, pivot-1);
        recursive(nums, pivot+1, r);
    }
    int partition(vector<int>& nums, int l, int r){
        int pivot = nums[l];
        while (l < r){
            while (nums[r] >= pivot && l < r) r--;
            nums[l] = nums[r];
            while (nums[l] < pivot && l <r) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
};
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

# 题目

  • Top-K 问题

# 归并排序

  • 归并排序的思想：递归+分治
  • 稳定排序
  • 时间复杂度：O(N^logN)

# 分治算法

将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立，且与原问题性质相同。求出子问题的解后进行合并，就可以得到原问题的解

一般步骤：

  1. 分解：将要解决的问题划分成若干规模较小的同类问题
  2. 求解：当子问题划分得足够小的时候，用较简单的方法解决
  3. 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解

# 算法模板

int t[100001];
void mergesort(int a[], int l, int r){
    if (l >= r) return;
    int mid = l+r>> 1;
    mergesort(a, l, mid), mergesort(a, mid+1, r);  // 递归 + 分治
    int i = l, j = mid+1, k= 0;
    while (i <= mid && j <= r){
        if (a[i] < a[j] ) t[k++] = a[i++];
        else t[k++] = a[j++];
    }
    while (i <= mid) t[k++] = a[i++];
    while (j <= r) t[k++] = a[j++];

    for (int i = l, j = 0; i<=r; i++, j++) a[i] = t[j];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 冒泡排序

# 算法思路

  • 进行len-1次冒泡
    • 第 k 次冒泡将倒数第 k 个元素排好序

# 代码实现

function bubbleSort(nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    // len - 1次冒泡
    for (let j = 0; j < nums.length - i - 1; j++) {
      // 依次比较相邻元素，进行冒泡，比较区间[0,len - 1 - i]
      if (nums[j] > nums[j + 1]) {
        let tmp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = tmp;
      }
    }
  }
  return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 桶排序

桶排序 的两个步骤：

  1. 分桶
  2. 合并

# 基数排序

  • 先按个位进行桶排序
  • 然后按十位进行桶排序
  • 然后按百位进行桶排序 ...
  • 直到所有位完成桶排序，最后的序列就是排好序的

比如：452，897，472，385，752

  • 按个位：452，472，752，385，897
  • 按十位：452，752，472，385，897

← 0x06_倍增 →