快速排序 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki

为什么说裸写quicksort能月薪1W?

裸写大作战

void QuickSort(
    const std::vector<int>::iterator first,
    const std::vector<int>::iterator last) {
  if (first == last || first + 1 == last) return;
  auto low = first + 1;
  auto high = last - 1;
  auto partition = first;
  while (low <= high) {
    while (*low < *partition) ++low;
    while (*high > *partition) --high;
    if (low < high) std::iter_swap(low, high);
  }
  std::iter_swap(first, low - 1);
  QuickSort(first, low - 1);
  QuickSort(high + 1, last);
}

QuickSort 接收的形参依旧贯彻左闭右开特征,此外我们假设这迭代器范围不包含重复的元素。那么先考虑两种极端情况:一是 [first, first), 即空集;二是 [first, second), 即元素只有一个。显然这两种情况都不需要排序,直接 return; 即可。

接着以第一个迭代器 first 为「基准数」,即 partition, 然后对 first + 1, last - 1 这个区间两端开始像中间逼近,不停地把「从左到右碰到且大于 *partition 的迭代器所指值」与「从右到左碰到且小于 *partition 的迭代器所指值」交换,只要这两个迭代器满足 low < high 关系。否则,就会跳出 while (low <= high) 循环,此时已经形成了两种区间,一个是所有元素均小于 *partition 的区间 [first + 1, low - 1), 二是所有元素均大于 *partition 的区间 [high + 1, last). 瞧瞧其中比较特殊的断点 low - 1high + 1, 再反观源代码中的双弹循环:

while (*low < *partition) ++low;
while (*high > *partition) --high;

就很容易看出,low 会卡在第一个大于 *partition 的迭代器上不动了,它后面就是整个所有元素均小于 *partition 的区间。同理,high 卡在第一个小于 *partition 的迭代器上,它前面则是所有元素均大于 *partition 的区间。所以事实上 lowhigh 正好相邻,且位置彼此颠倒了。由于 *partition 都大于 [first + 1, low - 1], 可以直接与 low - 1 上的迭代器交换。交换后,我们又得到一个小于 *partition 的新区间 [first, low - 1) 和一个大于 *partition 的新区间 [high - 1, last), 最后继续对两个区间递归排序。

于是,虽然所谓 partition 表面看起来不再像二分查找分割得那么整整齐齐了,然而其贯彻的「分治」思想依然与左闭右开范围相得益彰。

优化大作战

歼灭 bug

在学 Algorithm, Part I 时, 我只瞄了一眼快速排序原理,便花了半小时码出以上源代码,编译一次性通过,但运行有时莫名卡在死循环上。我再继续看课上的快速排序源代码,发现原来我遗漏了 partition 之后所有元素都小于/大于前者的极端情况,于是只要把 lowhigh 分别限定在 [first + 1, last) 与 (partition, last - 1] 就可以了,又是漂亮的半闭半开区间!

while (*low < *partition && low != last) ++low;
while (*high > *partition && high != first) --high;

顺便一提,其实没必要加 high != first, 因为当 high 递减到 partition 上时,就不再满足循环中的第一个条件 *high > *partition 了。

cutoff

当范围很小时,快速排序的效率倒不如时间复杂度为 N^2 的插入排序了。可以设个 cutoff, 当 last - first < cutoff, 就直接插入排序。不过我懒得实现插入排序,干脆用 std::sort() 代替算了(一本正经地划水中

shuffle

为了避免快速排序的时间复杂度在最坏情况下变成 N^2,可以在 partition 前对 [first + 1, last) 进行时间复杂度为 N 的 shuffle, 以让快速排序进入平均情况。可以用 std::random_shuffle.

median

Sedgewick 老师说,在 partition 之前,拿 first, first + (last - first) / 2last - 1 中的中位数替换掉 first, 能提高点效率。

反重复武装

为了对抗重复元素,我们需要开发反重复武装(握拳

一开始我想同时判断这四者:

  1. 代表小于 *partition 的区间尾后迭代器 less
  2. 代表等于 *partition 的区间尾后迭代器 equal
  3. 代表大于 partition 的区间首前迭代器 more
  4. partition

但如此同时比较,大大增加了复杂度,我想了半天也想不出行之有效的代码。只好蹭了教科书,发现其实只要比较 equal 和「基值」就行了,并按结果,该递增的递增,递减的递减:

while (equal <= more) {
  if (*equal < partition_value) {
    std::iter_swap(equal, less);
    ++equal;
    ++less;
  } else if (*equal > partition_value) {
    std::iter_swap(equal, more);
    --more;
  } else {
    ++equal;
  }
}

值得注意的是 less 可以初始化成 first, equal 则初始化为 first + 1, 不用担心一开始 *euqal 就小于 less 从而把「基」和 equal 交换掉,毕竟我们本来要塑造一个小于 [first, less) 的区间,所要只要事先用 partition_value 储存基上的值 *first 就可以了,而且又省了在循环之后交换 firstless - 1 的收尾工作。

最后,由于 less 本身就是小于 partition_value 的区间尾后元素,和普通快速排序实现不同,所以写第一个递归函数的参数要当心点:QuickSort(first, less);. 为了对称,第二个递归函数也如法炮制:QuickSort(equal, last);.

真・完美无暇之快速排序实现

#include <algorithm>

#include "insertion-sort.h"

// bad namespace scope while it is included in headfile
namespace quick_sort_h_ {

template <typename ForwardIterator>
ForwardIterator MedianOf3(
    ForwardIterator one,
    ForwardIterator two,
    ForwardIterator three) {
  return std::min_element(one, std::min_element(two, three));
}

constexpr int cutoff = 3;

}  // namespace

template <typename RandomIterator>
void QuickSort(
    RandomIterator first,
    RandomIterator last) {
  if (last - first < quick_sort_h_::cutoff) return InsertionSort(first, last);
  std::random_shuffle(first + 1, last);
  if (first + 2 < last) {
    auto median = quick_sort_h_::MedianOf3(
        first,
        first + (last - first) / 2,
        last - 1);
    std::iter_swap(first, median);
  }
  auto partition_value = *first;
  auto less = first;
  auto equal = first + 1;
  auto more = last - 1;
  while (equal <= more) {
    if (*equal < partition_value) {
      std::iter_swap(equal, less);
      ++equal;
      ++less;
    } else if (*equal > partition_value) {
      std::iter_swap(equal, more);
      --more;
    } else {
      ++equal;
    }
  }
  QuickSort(first, less);
  QuickSort(equal, last);
}

后续

  1. 引入模板技术。
  2. 正式实现 InsertionSort 并代替 std::sort().
  3. 替换 QuickSort(low, last); 成与 QuickSort(first, low - 1); 更对称的 QuickSort(high + 1, last);
  4. 成功开发出反重复武装,并归档为真・完美无瑕之快速排序实现。

LeetCode 242

Valid Anagram

马上就想到快速排序并比较,然后我特此开发了上文提到的反重复武装并投入实战:

class Solution {
public:
    void Swap(string::iterator first, string::iterator second) {
        auto temporary_value = *first;
        *first = *second;
        *second = temporary_value;
    }

    void QuickSort(string::iterator first, string::iterator last) {
        if (first == last || first + 1 == last) return;
        auto base = *first;
        auto less = first;
        auto equal = first + 1;
        auto more = last - 1;
        while (equal <= more) {
            if (*equal > base) {
                Swap(equal, more);
                --more;
            } else if (*equal < base) {
                Swap(equal, less);
                ++equal;
                ++less;
            } else {
                ++equal;
            }
        }
        QuickSort(first, less);
        QuickSort(equal, last);
    }

    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        QuickSort(s.begin(), s.end());
        QuickSort(t.begin(), t.end());
        if (s == t) return true;
    }
};

一如既往地一次性 Accepted. 不过出乎意料,我只击败了 44.74% C++ 用户。我以为高手直接用上了原汁原味的 std::sort, 便试试改用其函数,结果更大跌眼镜,我只击败了 4.07% 用户!搜了下,才发现原来还可以用 Hash 字词统计,其时间复杂度想必也是 n, 原来如此,原来如此……

播个小插曲:我质疑了 Is the word a anagram of itself?, 依评论来看,老外对 "anagram" 的定义也不一致,我还以为我要解锁「发现 LeetCode 题的错误」成就了呢。

LeetCode 75

Sort Colors

真没想到快速排序的思想还可以这样用,直接把 1 当反重复快速排序的基数用就行了:

class Solution {
public:
    void sortColors(vector<int>& nums) {
        if (nums.size() <= 1) return;
        auto less = nums.begin();
        auto equal = nums.begin();
        auto more = nums.end() - 1;
        while (equal <= more) {
            if (*equal > 1) {
                iter_swap(equal, more);
                --more;
            } else if (*equal < 1) {
                iter_swap(equal, less);
                ++less;
                ++equal;
            } else {
                ++equal;
            }
        }
    }
};

注意 *first 本身不再和基数一致了,是不确定的,所以和「已知 *first 本身就是基数」的常规快速排序不同,equal 得从 nums.begin() 开始迭代。

LeetCode 283

Move Zeros

马上就想到快速排序,直接把在迭代时所遇到其值为零的迭代器与 high 一一交换,同时递减后者。然而这就违背 in-place 原则了。

无奈之下,只好改用类插入排序的算法,耗时高达 204ms:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if (nums.size() <= 1) return;
        auto low = nums.begin();
        auto high = nums.end() - 1;
        auto iterator = low;
        while (low <= high) {
            if (*low == 0) {
                iterator = low;
                while (iterator < high) {
                    iter_swap(iterator, iterator + 1);
                    ++iterator;
                }
                --high;
            } else {
                ++low;
            }
        }
    }
};

我后来又想到反重复・快速排序,突然发现可以构造成一个迭代器区间 [low, equal),其值均等于零,[nums.begin(), low) 自然是一个其值皆非零的区间。接着,当 equal 还没迭代到 nums.end() 时,且其值 *equal 等于零,就 ++equal, 否则就再看看 [low, equal) 是不是一个空区间,若不是,则直接交换 lowequal. 最后不管区间是不是空的,都要再递增它们。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        auto less = nums.begin();
        auto equal = nums.begin();
        while (equal < nums.end()) {
            if (*equal == 0) {
                ++equal;
            } else if (less < equal) {
                iter_swap(less, equal);
                ++less;
                ++equal;
            } else {
                ++less;
                ++equal;
            }
        }
    }
};

这回时间复杂度只有 n 了,耗时为 20ms. 耶/

TODO: 有待确认时间复杂度排名。

⚠️ **GitHub.com Fallback** ⚠️