《编程珠玑》第11章(续)快速排序-宽支点划分

之前针对《编程珠玑》的排序算法章节写了一篇博文,采用了3中不同的划分算法来实现快速排序。最后的一个划分方式是使用“宽支点”划分法,即把待排序数组分成三个部分,但是最后取得的效果却差强人意。结合之前的分析,这两天在闲暇的时候想到了改进的方法,代码实现出来发现性能确实得到了改善,所以写出来做一个记录。

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);
    }
  • 造成这个算法效率不高的原因就是我在上图中用标记的步骤,的多次回退给算法带来了很多不必要的比较和交换存在。下面的图是我上次对几种实习方法的效率测试,这里的运行时间是指对1千万个随机整数进行排序的时间,算法3就是上面我给出的代码,可以看出这个算法的效率是很惨不忍睹了。

2.第二次给的改进,分成4段

  • 现在我想的一个方法是把待排序数组分成4段,分别是。然后再把两端的部分放到中间,最后再进行递归排序。

    首先说明一下如何把待排序数组划分出4段。

2.1划分数组

  • 这里使用了两个从两端分别向中靠拢的指针来遍历元素,并维护了下图所示的不变量。

    这里的分别表示待排序数组的起始和终止下标,而下标表示左边部分的右边界,同样的表示右边部分的左边界,最后的就是用来遍历元素的。

  • 现在简单说明一下怎么维护左半部分的不变量,对应的右半部分类比一下就行。

    考虑位置的元素,如果它还是,那就继续向右推进;如果,那就把它和位置的元素进行互换,对应的还要把进行自增;如果,那就需要把它和发现的的元素进行互换。下面给出这个步骤的代码实现。

    1
    2
    3
    4
    5
    6
    7
    8
    while(i < j && nums[++i] <= target) {
    if(nums[i] == target)
    swap(nums[++first], nums[i]);
    }
    while(j > i && nums[--j] >= target) {
    if(nums[j] == target)
    swap(nums[--second], nums[j]);
    }

2.2把两端的部分合并到中间

  • 现在考虑如何把两端的部分合并到中间来,同样的,还是用左半部分来简单说明一下。

    这里的想法也很简单,对于元素的个数比元素的个数少时,就把的元素和对应数目的左端元素进行互换;相反的,对于元素的个数比元素的个数多时,就把的元素和对应数目的左端元素进行互换。

    这里需要先实现一个交换数组两个子部分的函数。

    1
    2
    3
    4
    5
    //交换从beg1和beg2开始的n个元素,要求beg1 + n <= beg2
    void SwapVec(vector<int>& nums, int beg1, int beg2, int n) {
    for(int i = 0; i < n; ++i)
    swap(nums[beg1 + i], nums[beg2 + i]);
    }

    接下来是实现合并两个的部分的代码。

    1
    2
    3
    4
    5
    int len = min(first - begin + 1, i - first - 1);
    SwapVec(nums, begin, i - len, len);

    len = min(second - j, end - second + 1);
    SwapVec(nums, j, end - len + 1, len);

2.3完整的代码

  • 现在给出这个算法的完整代码。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    //交换从beg1和beg2开始的n个元素,要求beg1 + n <= beg2
    void SwapVec(vector<int>& nums, int beg1, int beg2, int n) {
    for(int i = 0; i < n; ++i)
    swap(nums[beg1 + i], nums[beg2 + i]);
    }

    //对nums中从begin到end下标之间的元素进行快速排序
    void QuickSort4(vector<int>& nums, int begin, int end) {
    if (begin >= end) return;

    int target = nums[begin], i = begin, first = begin, j = end + 1, second = end + 1;
    while(i < j) {
    while(i < j && nums[++i] <= target) {
    if(nums[i] == target)
    swap(nums[++first], nums[i]);
    }
    while(j > i && nums[--j] >= target) {
    if(nums[j] == target)
    swap(nums[--second], nums[j]);
    }

    if(i >= j) break;
    swap(nums[i], nums[j]);
    }

    int len = min(first - begin + 1, i - first - 1);
    SwapVec(nums, begin, i - len, len);

    len = min(second - j, end - second + 1);
    SwapVec(nums, j, end - len + 1, len);


    if((len = i - first) > 1)
    QuickSort4(nums, begin, begin + len - 1);
    if((len = second - j) > 1)
    QuickSort4(nums, end - len + 1, end);

    }

3.效率测试

  • 现在同样的使用1千万个随机整数来测试这两种“宽支点”划分的排序算法的性能,测试结果如下图所示。

    这里可以明显发现运行时间得到了改善,说明我们的改进也是非常有效的。但是效果还是比之前的前两个要略差,原因也很容易找到,主要的耗时都用在合并两个的部分。

  • 所以有时候越是简单粗暴的算法往往越有可能取得较好的性能,算法的优化目标也只有一个,那就是用最简单的思路和最高效的代码来解决问题。

------------- 本文结束 感谢您的阅读 -------------

本文标题:《编程珠玑》第11章(续)快速排序-宽支点划分

文章作者:Perry

发布时间:2019年11月25日 - 15:35

最后更新:2019年11月25日 - 22:44

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

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

0%