GabWiki

Appearance

排序 ​

快速排序 ​

  1. 找到分界点 p（有三种选择：q[l]、q[l + r >> 1]、q[r]）。
  2. 将区间 [l,r] 划分为两段， 使得分界点左边所有数 Left≤p，分界点右边所有数 Right≥q。
  3. 递归地排序左右两边：sort(Left)、sort(Right)。

应用：【快速选择】第k个数

Java
void quickSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int p = nums[l + (r - l >> 1)], i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (nums[i] < p);
        do --j; while (nums[j] > p);
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quickSort(nums, l, j);
    quickSort(nums, j + 1, r);
}
void quickSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int p = nums[l + (r - l >> 1)], i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (nums[i] < p);
        do --j; while (nums[j] > p);
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quickSort(nums, l, j);
    quickSort(nums, j + 1, r);
}
C++
void quick_sort(int nums[], int l, int r) {
    if (l >= r) return;
    int p = nums[l + (r - l >> 1)], i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (nums[i] < p);
        do --j; while (nums[j] > p);
        if (i < j) swap(nums[i], nums[j]);
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}
void quick_sort(int nums[], int l, int r) {
    if (l >= r) return;
    int p = nums[l + (r - l >> 1)], i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (nums[i] < p);
        do --j; while (nums[j] > p);
        if (i < j) swap(nums[i], nums[j]);
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

归并排序 ​

  1. 把区间 [l,r] 从中点(mid = l + r >> 1)分割为 [l,mid] 以及 [mid+1,r]。
  2. 递归排序左右两边：sort(l, mid)、sort(mid + 1, r)。
  3. 归并，将左右两个有序序列合成为一个有序序列。

应用：【归并排序】逆序对的数量

Java
int[] tmp; // 全局开一个与nums一样长的数组(在主函数中赋值)

void mergeSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l >> 1);
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
 	while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
}
int[] tmp; // 全局开一个与nums一样长的数组(在主函数中赋值)

void mergeSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l >> 1);
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
 	while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
}
C++
int tmp[N]; // 全局开一个与nums一样长的数组

void merge_sort(int nums[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l >> 1);
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
}
int tmp[N]; // 全局开一个与nums一样长的数组

void merge_sort(int nums[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l >> 1);
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    }
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= r) tmp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
}