快速排序相关问题

[happyvictorwu]

快速排序

算法

快速排序

均摊时间：O(nlogn) & 空间：O(logn)

• 在数组选一个数v(选中间的)，把数组左边变成<=v，右边变成>=v,使用分治的思想，分别对左边和右边进行快速排序
• 理论上最优的策略是以他的中位数来做为划分依据, 让其划分得均匀

注意：partition返回的是j，而不是i。

解释：
partition 返回j的原因：
partition假如以中点向下取整(l + r >> 1), 只剩下两个数的时候(如 1 2) 就会以左边的1为基准值x，i 和 j 最后会cross over，因为是do while循环， i会到2的位置， j会到1的位置。 这样左边(l, j)是小于等于1， 右边(i, r)是大于等于1.这样不会死循环。若返回i就会发生划分的左边死循环，一直是(1, 2)划分，无限递归下去。

若要返回i， 跟二分很像，则需要以中点向上取整(l + r + 1 >> 1)。 同理，还是以数组剩下两个元素（1， 2）为例， 基准值x取2. 当i, j cross over之后， 左边小于等于2为(l, i - 1), 右边大于等于2为(i， r)。

为什么写do while 循环, 尝试例子数组排序 1 2 1 , 死循环. 因为交换完的时候就卡住了.

• 向下取整

int partition(int a[], int l, int r) {
    int x = a[l + r >> 1];   //  下取整
    int i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (a[i] < x);
        do --j; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    return j;    // 一定是j
}

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quick_sort(a, l, p);   // 划分区间
    quick_sort(a, p + 1, r);
}

• 向上取整

int partition(int a[], int l, int r) {
    int x = a[l + r + 1 >> 1];   // 上取整
    int i = l - 1, j = r + 1;
    while (i < j) {
        do ++i; while (a[i] < x);
        do --j; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    return i;   // 一定是i
}

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int p = partition(l, r);
    quick_sort(l, p - 1);   // 划分区间
    quick_sort(p, r);
}

应用

第k小的数

在无序数组中找第k小的数字

int partition(int a[], int l, int r) {
    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    return j;
}

int quick_sort(int a[], int l, int r, int k) {
    if (l == r) return a[l];
    
    int p = partition(a, l, r);
    int leftNum = p - l + 1;  // 左边比基准值小的个数
    if (leftNum >= k) return quick_sort(a, l, p, k);   // 从左边找第k个的数
    return quick_sort(a, p + 1, r, k - leftNum);   // 从右边找第k - leftNum的数, 因为左边已经有leftNum个数了
}