大四的萌新辣！

快速排序

Posted on Edited on In Valine:

今天来介绍一种常用的排序算法 — 快速排序
…如果你和我讲sort那请你忽略这篇文章…

快速排序思想

快速排序主要采用的思想是分而治之,主要步骤有以下三部分：

  • 确定分界点

    $x = a[l]$还是$x = a[r]$还是$x = a[(l + r)>> 1]$

  • 调整区间 划分成为两个区间 使得：

    1. 划分点$x$ 左边所有的数均小于等于$x$
    2. 划分点$x$ 右边所有的数均大于等于$x$

保证满足上述两条即可 如果等于$x$ 实际在左右均可。

  • 递归

    递归处理划分的两个区间即可。

快速排序模板

快速排序中有许多边界问题，因此最好背过一种模板 可以避免绝大多数边界情况的模板即可。

下边提供一种快速排序的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void quick_sort(vector <int>& arr, int l, int r) {
    if(l >= r) {
        return ;
    }
    int x = arr[(l + r) >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        do {i++;} while(arr[i] < x);
        do {j--;} while(arr[j] > x);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

快速排序常见问题

在这里，我们会遇到较多的边界处理情况，例如：

如果我们写quick_sort(arr, l, j) 和 quick_sort(arr, j + 1, r)， 那我们相当于是以$j$为界限划分，这时候取得$x$的值的时候，我们不可以选择$a[r]$作为分界点，实际上，我们不可以选择区间的右端点作为分界点，因此我们不可以在确定x的时候写x = arr[r]和x = arr[(l + r + 1) >> 1],只可以写x = arr[l] 和 x = arr[(l + r) >> 1].

  • 选$j$为分界点 取到中间或者左边界 正确分析情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//不过不建议这种写法 因为可能会导致每次选择的时候
//都是左端点 对于一个排好序的数组最坏情况下 时间
//复杂度可以达到O(n^2)
void quick_sort(vector <int>& arr, int l, int r) {
    if(l >= r) {
        return ;
    }
    int x = arr[l], i = l - 1, j = r + 1;
    while(i < j) {
        do {i++;} while(arr[i] < x);
        do {j--;} while(arr[j] > x);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 完美写法
void quick_sort(vector <int>& arr, int l, int r) {
    if(l >= r) {
        return ;
    }
    int x = arr[(l + r) >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        do {i++;} while(arr[i] < x);
        do {j--;} while(arr[j] > x);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

如果我们写quick_sort(arr, l, i - 1) 和 quick_sort(arr, i, r)， 那我们相当于是以$i$为界限划分，这时候取得$x$的值的时候，我们不可以选择$a[l]$作为分界点，实际上，我们不可以选择区间的左端点作为分界点，因此我们不可以在确定x的时候写x = arr[l]和x = arr[(l + r) >> 1],只可以写x = arr[r] 和 x = arr[(l + r + 1) >> 1].

  • 选$i$为分界点 取到中间或者左边界 陷入死循环情况

  • 选$i$为分界点 取到中间或者右边界 正确分析情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//不过不建议这种写法 因为可能会导致每次选择的时候
//都是左端点 对于一个逆序排好序的数组最坏情况下 时
//间复杂度可以达到O(n^2)
void quick_sort(vector <int>& arr, int l, int r) {
    if(l >= r) {
        return ;
    }
    int x = arr[r], i = l - 1, j = r + 1;
    while(i < j) {
        do {i++;} while(arr[i] < x);
        do {j--;} while(arr[j] > x);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
    }
    quick_sort(arr, l, i - 1);
    quick_sort(arr, i, r);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 完美写法
void quick_sort(vector <int>& arr, int l, int r) {
    if(l >= r) {
        return ;
    }
    int x = arr[(l + r + 1) >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        do {i++;} while(arr[i] < x);
        do {j--;} while(arr[j] > x);
        if(i < j) {
            swap(arr[i], arr[j]);
        }
    }
    quick_sort(arr, l, i - 1);
    quick_sort(arr, i, r);
}

以上就是选取基准值以及划分边界的边界易错情况。

划分的时候我们划分的两个区间不可以有交集

因此我们我们不可以$i$和$j$交叉使用.

即只可以使用：

  • 以$i$划分
    1. (l, i - 1)和(i, r)
    2. (l, i)和(i + 1, r)
  • 以$j$划分
    1. (l, j - 1) 和(j, r)
    2. (l, j)和(j + 1, r)

然后上边四种情况有两种是不可以使用的 会出现边界问题

注意划分的时候是：

  • (l, j)和(j + 1, r)
  • (l, i - 1)和(i, r)

而不是：

  • (l, j - 1)和(j, r)
  • …

等其他情况…

模拟样例即可发现数组越界的情况辣~~~

如果出现while(i <= j)的写法也是不正确的

如下图所示 会发生死循环的情况：

  • 采用while(i <= j)的写法 情况分析

重点

此处对于陷入死循环的情况是由于函数执行后并没有缩短区间长度，导致无限递归，并不属于一个性质 只是一个边界情况qwq 并且除了快排 在其他地方基本不会遇到……因此没有必要过于纠结……

快排时间复杂度分析

具体计算emm 待补 参见算法导论[实际是我还不会qwq]

快排总结

事实证明：

sort 天下第一！！！（破音~）