【算法基础】快速排序算法的证明与边界分析

博主： Fivk
发布时间：2021 年 12 月 06 日
1402 次浏览
暂无评论
1284字数
分类：算法基础

### 算法证明

算法证明使用**算法导论** 里的**循环不变式** 方法

#### 快排模板(以j为分界)

快排属于分治算法，分治算法都有三步：

1. 分成子问题
2. 递归处理子问题
3. 子问题合并

```cpp
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);
    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}
```

#### 待证问题

while循环结束后，`q[l..j] <= x`,`q[j+1..r] >= x`

注:`q[l..j] <= x`意为`q[l],q[l+1]...q[j-1],q[j]`的所有元素都`<= x`

#### 证明

循环不变式：`q[l..i] <= x q[j..r] >= x`

1. 初始化

循环开始之前`i = l - 1, j = r + 1`

则`q[l..i],q[j..r]`为空，循环不变式显然成立

2. 保持

假设某轮循环开始前循环不变式成立，即`q[l..i] <= x, q[j..r] >= x`

执行循环体

```cpp
  do i++; while(q[i] < x);
  会使得 q[l..i-1] <= x, q[i] >= x
  
  do j--; while(q[j] > x);
  会使得 q[j+1..r] >= x, q[j] <= x
  
  if(i < j) swap(q[i], q[j]);
  会使得 q[l..i] <= x, q[j..r] >= x
```

所以，i和j更新之后，下一次循环开始之前，循环不变式依然成立

注意:由于使用do-while循环,所以`i`和`j`一定会!!!自增!!!,使得循环会继续下去,但是如果采用while循环(`i`和`j`的初始化做出对应的变更),`i`和`j`在特殊情况下不自增的话,循环就会卡死

例如:

```cpp
  while(q[i] < x) i++;
  while(q[j] > x) j--;
当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环
```

3. 终止

循环结束时，`i >= j`
正常情况下，按照循环不变式，我们应该会觉得结果已经显然了
因为`i >= j，q[l..i] <= x, q[j..r] >= x`
所以按照`j`来划分的话，`q[l..j] <= x, q[j+1..r] >= x`是显然的
可是，最后一轮循环有点特殊，因为**最后一轮循环的if语句一定不会执行**
因为最后一轮循环一定满足 i >= j,不然不会跳出while循环的，所以if语句一定不执行
**正确分析** ：
由于最后一轮的if语句一定不执行
所以，只能保证`i >= j`和`q[l..i-1] <= x, q[i] >= x`和`q[j+1..r] >= x, q[j] <= x`
由`q[l..i-1] <= x，i >= j(i-1 >= j-1)` 和 `q[j] <= x` 可以得到 `q[l..j] <= x`
又因为`q[j+1..r] >= x`
所以，`q[l..j] <= x,q[j+1..r] >= x`,**问题得证**
**总结** :只有最后一轮循环结束时，循环不变式不成立，其余的循环都是成立的
但最终要求的问题还是解决了
**注意** :循环结束时要记得检查是否存在数组越界/无限递归的情况
所以还需要证明 `j` 最终的取值范围是`[l..r-1]`(即不存在`n`划分成`0`和`n`的无限递归情况),分析过程在分析`5`

### 边界情况分析

#### 分析

快排属于**分治算法** ，最怕的就是 `n分成0和n，或 n分成n和0`,这会造成**无限划分**

1. 以`j`为划分时，`x`不能选`q[r]` (若以`i`为划分,则`x`不能选`q[l]`)

假设 `x = q[r]`

关键句子`quick_sort(q, l, j), quick_sort(q, j + 1, r);`

由于`j`的最小值是`l`,所以`q[j+1..r]`不会造成无限划分

但`q[l..j]`(即quick_sort(q, l, j))却可能造成无限划分，因为j可能为r

举例来说，若`x`选为`q[r]`，数组中`q[l..r-1] < x`,

那么这一轮循环结束时`i = r, j = r`，显然会造成无限划分

2. `do i++; while(q[i] < x)`和`do j--; while(q[j] > x)`不能用`q[i] <= x` 和 `q[j] >= x`
   假设`q[l..r]`全相等
   则执行完`do i++; while(q[i] <= x);`之后，`i`会自增到`r+1`
   然后继续执行`q[i] <= x` 判断条件，造成数组下标越界(但这貌似不会报错)
   并且如果之后的`q[i] <= x (此时i > r)` 条件也不幸成立，
   就会造成一直循环下去(亲身实验)，造成内存超限`(Memory Limit Exceeded)`
3. `if(i < j) swap(q[i], q[j])`能否使用 `i <= j`
   可以使用`if(i <= j) swap(q[i], q[j]);`
   因为 `i = j` 时，交换一下`q[i],q[j]` 无影响，因为马上就会跳出循环了
4. 最后一句能否改用`quick_sort(q, l, j-1), quick_sort(q, j, r)`作为划分(用`i`做划分时也是同样的道理,)
   不能
   根据之前的证明，最后一轮循环可以得到这些结论
   `j <= i` 和 `q[l..i-1] <= x, q[i] >= x` 和 `q[j+1..r] >= x, q[j] <= x`
   所以，`q[l..j-1] <= x` 是显然成立的，
   但`quick_sort(q, j, r)`中的`q[j]` 却是 `q[j] <= x`，这不符合快排的要求
   另外一点，注意`quick_sort(q, l, j-1), quick_sort(q, j, r)`可能会造成无线划分
   当`x`选为`q[l]`时会造成无限划分，报错为(MLE),
   如果手动改为 `x = q[r]`,可以避免无限划分
   但是上面所说的`q[j] <= x` 的问题依然不能解决，这会造成 `WA (Wrong Answer)`
5. `j`的取值范围为`[l..r-1]`

证明:

假设 `j` 最终的值为 `r` ,说明只有一轮循环(两轮的话 `j` 至少会自减两次)

说明`q[r] <= x` (因为要跳出`do-while`循环)

说明 `i >= r `(while循环的结束条件), `i` 为 `r` 或 `r + 1`(必不可能成立)

说明 `i` 自增到了 `r` , 说明 `q[r] >= x 和 q[l..r-1] < x`,

得出 `q[r] = x 和 q[l..r-1] < x` 的结论,但这与 `x = q[l + r >> 1]`**矛盾**

**反证法** 得出 `j < r`

假设 `j` 可能小于 `l` 说明 `q[l..r] > x` ,**矛盾**

**反证法** 得出 `j >= l`

所以 `j`的取值范围为`[l..r-1]`,不会造成无限划分和数组越界

6. `while`循环的结束条件能不能改成`i <= j`

顺带一提用`i`做划分时的模板

```cpp
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 >> 1];//注意是向上取整,因为向下取整可能使得x取到q[l]
    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, i - 1), quick_sort(q, i, r);
    //不用q[l..i],q[i+1..r]划分的道理和分析4中j的情况一样
}
```

作者：醉生梦死
链接：https://www.acwing.com/solution/content/16777/
来源：AcWing

</div>

最后修改：2021 年 12 月 06 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【算法基础】快速排序算法的证明与边界分析

Fivk • 2021 年 12 月 06 日

### 算法证明

算法证明使用**算法导论** 里的**循环不变式** 方法

#### 快排模板(以j为分界)

快排属于分治算法，分治算法都有三步：

1. 分成子问题
2. 递归处理子问题
3. 子问题合并

#### 待证问题

while循环结束后，`q[l..j] <= x`,`q[j+1..r] >= x`

注:`q[l..j] <= x`意为`q[l],q[l+1]...q[j-1],q[j]`的所有元素都`<= x`

#### 证明

循环不变式：`q[l..i] <= x q[j..r] >= x`

1. 初始化

循环开始之前`i = l - 1, j = r + 1`

则`q[l..i],q[j..r]`为空，循环不变式显然成立

2. 保持

假设某轮循环开始前循环不变式成立，即`q[l..i] <= x, q[j..r] >= x`

执行循环体

所以，i和j更新之后，下一次循环开始之前，循环不变式依然成立

例如:

```cpp
  while(q[i] < x) i++;
  while(q[j] > x) j--;
当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环
```

3. 终止

### 边界情况分析

#### 分析

快排属于**分治算法** ，最怕的就是 `n分成0和n，或 n分成n和0`,这会造成**无限划分**

1. 以`j`为划分时，`x`不能选`q[r]` (若以`i`为划分,则`x`不能选`q[l]`)

假设 `x = q[r]`

关键句子`quick_sort(q, l, j), quick_sort(q, j + 1, r);`

由于`j`的最小值是`l`,所以`q[j+1..r]`不会造成无限划分

但`q[l..j]`(即quick_sort(q, l, j))却可能造成无限划分，因为j可能为r

举例来说，若`x`选为`q[r]`，数组中`q[l..r-1] < x`,

那么这一轮循环结束时`i = r, j = r`，显然会造成无限划分

证明:

假设 `j` 最终的值为 `r` ,说明只有一轮循环(两轮的话 `j` 至少会自减两次)

说明`q[r] <= x` (因为要跳出`do-while`循环)

说明 `i >= r `(while循环的结束条件), `i` 为 `r` 或 `r + 1`(必不可能成立)

说明 `i` 自增到了 `r` , 说明 `q[r] >= x 和 q[l..r-1] < x`,

得出 `q[r] = x 和 q[l..r-1] < x` 的结论,但这与 `x = q[l + r >> 1]`**矛盾**

**反证法** 得出 `j < r`

假设 `j` 可能小于 `l` 说明 `q[l..r] > x` ,**矛盾**

**反证法** 得出 `j >= l`

所以 `j`的取值范围为`[l..r-1]`,不会造成无限划分和数组越界

6. `while`循环的结束条件能不能改成`i <= j`

顺带一提用`i`做划分时的模板

```cpp
void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;

作者：醉生梦死
链接：https://www.acwing.com/solution/content/16777/
来源：AcWing

</div>

【算法基础】快速排序算法的证明与边界分析

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

【Fivk】文章归档

回忆刚入天柱二中的我

【开发工具】IDEA新版本新建SpringBoot项目JDK版本选择问题

【数据结构】图论算法_图的连通性问题

今天又是24小时的一天

【开发技巧】基于Spring单例创建对象的实现

【踩坑日志】java.lang.NullPointerException: null

【算法基础】快速排序算法的证明与边界分析

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【算法基础】快速排序算法的证明与边界分析

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款