《编程珠玑》第11章 排序

本文主要针对《编程珠玑》第11章中的快速排序算法阅读做一点记录。

  • 快速排序是一种分治算法:排序数组时,将数组分成两个小部分,其中一部分大于数组中的某个值,另一部分不大于这个值,然后对这两个部分进行递归排序。
  • 下面使用下标(从0开始)和表示待排序部分的上界和下界,递归结束的条件是带排序部分的元素个数小于2,即
  • 为了围绕值对数组进行划分,下面分别讨论几种方案。

1. 一个简单的快速排序

  • 划分数组时,我们需要维护如下图所示的一个循环不变式。

    a

    这里维护一个下标,使得所有小于的元素在的一端,所有大于等于的元素在另一端。

    在检查第个元素时必须考虑两种情况。如果,那么一切正常,不变式依然成立;如果,可以让增加1,然后交换,重新获得不变式。

  • 循环终止时,可以得到:

    b

  • 最后交换,可以得到:

    c

  • 目前都是选取第1个元素作为的,一个极端的情况是数组已经按升序排好了,那么我们需要进行次划分,每次划分的时间复杂度为,最后就是的复杂度。因此这里使用随机选择划分元素来获得更好的性能。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
void QuickSort1(vector<int>& nums, int l, int u){
if(l >= u) return;
swap(nums[l], nums[rand() % (u-l+1) + l]);
int target = nums[l], mid = l;
for(int i = l + 1; i <= u; ++i){
if(nums[i] < target){
swap(nums[++mid], nums[i]);
}
}
swap(nums[mid], nums[l]);
QuickSort1(nums, l, mid - 1);
QuickSort1(nums, mid + 1, u);
}

2.一个更好的划分方法

  • 这里使用双向划分来加快每次循环时的速度,循环不变式如下:

    d

    下标初始化为待划分数组的两端,主循环里有两个内循环,第一个内循环将向右移过小元素,遇到时停止;第二个内循环将向左移过大元素,遇到时停止。最后主循环检查这两个下标是否交叉,没有的话交换它们。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void QuickSort2(vector<int>& nums, int l, int u){
if(l >= u) return;
swap(nums[l], nums[rand() % (u-l+1) + l]);
int target = nums[l], i = l, j = u + 1;
while(i < j){
while(i < u && nums[++i] < target);
while(j > l && nums[--j] >= target);
if(i >= j) break;
swap(nums[i], nums[j]);
}
swap(nums[l], nums[j]);
QuickSort2(nums, l, j - 1);
QuickSort2(nums, j + 1, u);
}

3.习题:使用“宽支点”划分函数的快速排序

  • 题目要求我们实现一个“宽支点”划分函数,使得每次的划分结果如下图所示:

    e

  • 这里使用3个下标来维护循环不变量,如下图所示:

    f

    下标表示小于部分的最右端点,下标表示大于部分的最左端点,下标是等于部分的右端点,3个下标分别初始化为。每次循环时将增加1,如果,那么让增加1,并交换,循环式保持不变;如果,那么让减少1,并交换,但是循环式不一定可以保持不变,因为不一定等于,这里就需要将减少1,退回到原来的位置,继续维护不变式。

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void QuickSort3(vector<int>& nums, int l, int u){
if(l >= u) return;
swap(nums[l], nums[rand() % (u-l+1) + l]);
int target = nums[l], i = l, start = l - 1, end = u + 1;
while(i < end){
if(nums[i] < target)
swap(nums[i], nums[++start]);
else if (nums[i] > target)
swap(nums[i--], nums[--end]);
++i;
}
QuickSort3(nums, l, start);
QuickSort3(nums, end, u);
}

4. 3个算法的性能考察

  • 这里生成含1千万个随机整数的数组来测试3个算法的性能,结果如下:

    g

    这里算法2的性能最优,算法2次之,而算法3的性能最差,是算法2的2倍还多。原因也是显而易见的,算法2的双向划分显著降低了swap操作的次数,而算法3中交换在多数情况都是破坏不变式的,增加了很多swap的操作。

5. 习题:寻找数组中第k小的元素

  • 这题的解法有很多,比如排序整个数组,然后输出第个元素;

  • 或者使用一个限定大小为的大根堆,依次考察数组元素,如果堆不满,则插入;如果堆满并且大于堆顶值,则不插入堆;如果堆满并且小于等于堆顶值,则先插入再删除堆顶。

  • 这里最优的做法是使用快速排序里的划分函数。在一次划分结束之后,如果,则输出;如果,则递归在前半部分寻找;否则递归在后半部分寻找。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int findKth(vector<int>& nums, int l, int u, int k){
    if(l > u) return -1;
    swap(nums[l], nums[rand() % (u-l+1) + l]);
    int target = nums[l], i = l, j = u + 1;
    while(i < j){
    while(i < u && nums[++i] < target);
    while(j > l && nums[--j] > target);
    if(i >= j) break;
    swap(nums[i], nums[j]);
    }
    swap(nums[l], nums[j]);
    if(j == (k - 1))
    return j;
    else if(j > (k - 1))
    return findKth(nums, l, j-1, k);
    else
    return findKth(nums, j+1, u, k);
    }
------------- 本文结束 感谢您的阅读 -------------

本文标题:《编程珠玑》第11章 排序

文章作者:Perry

发布时间:2019年08月31日 - 11:35

最后更新:2019年09月19日 - 13:48

原始链接:https://perry96.com/archives/39c888b.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%