理解快速排序算法过程

快排一瞥

快排通常是一中非常高效的排序算法,并且其常规实现也非常简单,往往很容易理解其思路并写出实现码,前提是需要解决递归这种思考方式。

1. 排序思路

开始的时候,我们从整个数列中“任意”找出一个数作为基准数(pivot),接着拿剩余的数挨个与这个基准数比较,比它小的放在它左边,比它大的放在它右边,这便完成了一次划分(partition)。结果是我们把原来的整个数列以基准数为中点分成了两个子数列(当把子数列当成一个整体的时候,此时整个序列是有序的)。接下来要对这两个子数列做的事情和刚刚对整个数列做的事情一样……一直到子数列只有一个数的时候,自然成序,整个数列也在这一次次划分动作中完成排序

每次划分结束会形成一个有序列

再具体一点描述的话:“对整个数列施行一次划分,把小于pivot的子列看成一个新的数列,回到这句话的开头,把大于pivot的子列看成一个新的数列,回到这句话的开头”。如果大家在认真读这句话的话,你至少是读不到当前这句话的,它是读不完的。从程序的角度看,这陷入了无穷递归,最终导航到stackoverflow(.com)。从上面的描述中,我们发现是有一个结束点的,换句话说,当数列只剩一个数的时候,我们觉得划分这个动作的意义已经消失了,这时low_ptr==high_ptr

快排伪过程

2. 图解快排过程

先给出一个待排序的数列[2, 1, 6, 4, 8, 5]。按照思路,我们需要从中找一个元素作为基准数,这里我们使用最后一个元素5作为基准数,至于为什么偏偏是最后一个元素,我们下面会结合算法性能再讨论。

原始序列

实际上,我们有两个需要图解的地方,一个是快排的递归部分,一个是划分算法部分。递归部分借助划分算法不断向下进行,直到当前待划分的数列中仅剩一个元素。递归部分更像一个执行控制流,而真正的执行由划分部分完成。

快排递归部分图解

下面我们用图解的方式看看划分部分是怎样实现的,我们拿上面图解中的第一步(也就是对整个原始序列进行划分那一步)来举例。

实现划分部分的数据结构

具体实现上我们借助几个变量记录索引(index)来完成比较和交换操作,prev初始为-1,这就是它在图中指向第一个元素之前的原因,它会始终记录最近一个小于pivot的值的索引;curr初始为0,也就是指向第一个元素,它会向后挨个取元素(除pivot以外),然后每拿到一个元素都会与pivot进行比较,如果小于pivot就把prev更新到这个元素处,如果大于pivot则什么也不做。

建议大家用纸笔模拟一下这个过程,结果便是划分操作的输出,随着最后一步——将pivot换到prev++的位置,pivot将数列划分成小于自己与大于自己的两个部分。

划分过程中的一次比较与交换操作

3. 基准数(Pivot)

基准数并没有什么最佳的选择方式,依旧取决于待排序数的数理性质,上面我们总是使用数列中最后一个元素作为基准数,实际上也可以总是使用第一个,或使用中间那个,再或者每次都随机选择一个。

使用不同的选择方式是为了算法性能,如果原来的数列是一个倒序的数列,再总是用最后一个元素作为基准数,性能会怎样?这个时候每次划分的结果总是n-1个元素和0个元素,并且每次划分的代价都是 Θ (元素数),所以此时算法运行时间的递归式为 T(n)=T(n−1)+Θ(n),解为T(n)=Θ(n2)。 这便是快排最坏情况下的时间复杂度。

理想情况下,选择的基准数总是能够将当前数列分成两等份,此时 算法运行时间递归式为 T(n)=2T(n/2)+Θ(n),解为T(n)=Θ(nlgn)。为了朝这个方向努力,应该结合待排序数列的数理性质来确定基准数的选择策略。另外,使用随机选择的方式至少可以极大程序的避免最坏情况的出现。

4. 代码实现

def quick_sort(collection: list) -> list:
    if len(collection) < 2:
        return collection
    pivot =  collection.pop()
    greater: list[int] = []
    lesser: list[int] = []
    for element in collection:
        (greater if element > pivot else lesser).append(element)
    return quick_sort(lesser) + [pivot] + quick_sort(greater)

if __name__ == "__main__":
    nums = [2, 1, 6, 4, 8, 5]
    print(*quick_sort(nums))
#include <iostream>
#include <vector>
#include <random>
#include <ctime>

using namespace std;

int partition(int collection[], int low, int high) {
	int prev = low - 1;
	int pivot = collection[high];

	for (int curr = low; curr < high; ++curr) {
		if (collection[curr] < pivot) {
			++prev;
			
			swap(collection[prev], collection[curr]);
		}
	}
	swap(collection[++prev], collection[high]);

	return prev;
}

void quick_sort(int collection[], int low, int high) {
	if (low < high) {
		int pivot_index = partition(collection, low, high);
		quick_sort(collection, low, pivot_index - 1);
		quick_sort(collection, pivot_index + 1, high);
	}
}

int main() {
	int collection[] = { 2, 1, 6, 4, 8, 5 };
	quick_sort(collection, 0, 5);
	for (int i = 0; i < 6; ++i)
		cout << collection[i] << ",";
}

5. 参考

快速排序的时间和空间复杂度

QuickSort – GeeksForGeeks

理解希尔排序算法过程

插入排序总览

之前的文章已经讲解了直接插入排序算法的过程,当时也指出了直接插入排序存在的问题:每插入一个元素都需要进行大量的移动操作,这导致这种算法的性能不算高。既然原因已经找到了,其它几种插入算法实际上都是针对这个问题提出了自己的优化方式。这篇文章就来讲解其中有名的一个——希尔排序

1. 排序思路

我们先”随意“找一个间隔(gap),对待排序的数列按这个间隔取数,这会从原数列中筛选出一个新的数列,我们对这个新的数列执行直接插入排序。然后,我们再找一个比之前间隔略小的一个间隔(gap-2),把上面这个过程再来一遍,…. 最后,我们将这个间隔取成1(gap-n = 1),仍然进行一次上面的过程,这样便排序完成。

希尔排序的算法思路大概如此,只用文字描述可能不够直观,下面结合例子和图解来详细说说这个过程。

2. 图解排序过程

正式开始前我们先给出一个间隔列[701, 301, 132, 57, 23, 10, 4, 1]。我们暂时先不纠结这个间隔列是怎么来的,这并不妨碍我们使用它。

接下来要准备一个例子,我们随手写下一个数字列[0, 5, 3, 2, 2, 8],把它作为我们这个过程的主角。现在我们的任务是:借助间隔列将希尔排序算法作用于此数字列,以达到排序之目的

待排序的数列(用不同颜色区分是两个不同的数字2)

首先,我们从间隔列中取一个间隔,但这里只有6个数字,所以可用的间隔只有4和1,毕竟我们没有办法从一个只有6个数字的数列中找出间隔为10(>=6)的两个数字。并且我们要先使用最大可用间隔,这里也就是gap=4。这表示我们接下来需要从原数列中每隔4个数取一个数,组成一个新的数列,也就是像下面那样做:

每隔4个数取一个数组成了两个新的数列

现在,我们得到两个新的数列:[0,2][5,8]。按照思路,我们需要对这两个数列执行直接插入排序,因为这两个数列实际上是有序的,所以我们执行完直接插入排序过程后,它们并没有什么不同。

间隔取4的情况我们已经进行完了(尽管从表面上看,我们似乎什么都没做),下面应该让间隔取1了(最后一个使用的间隔一定是1),这表示我们需要从原数列中每隔1个数取一个数,这意味着什么?我们接下来的新数列就是原数列本身:

每隔1个数取一个数组成的新数列必定是原数列本身

按照思路,接下来我们需要对这个新数列执行直接插入排序,这样的结果当然是整个数列变成了有序数列(升序)。

最终得到的有序数列

这其实说明了为什么我们无论使用怎样的间隔列,我们必须保证最后一个间隔得是1,因为只有这样我们才能在最后一次排序时至少对所有数组成的数列进行一次直接插入排序,从而保证最后得到的数列是有序的。到这里,可能有人会觉得矛盾,单从上面这个例子看,还不如一开始就对整个数列进行一次直接插入排序,一步到位,做的工作更少;另外,既然迟早会对整个数列执行一次直接插入排序,为什么还要使用间隔排序这多此一举呢?

答案在于,我们前面所进行的间隔排序会影响最后一次对整个数列的排序过程,更进一步说,前面的动作减少了最后一次排序元素时可能移动的次数。希尔排序对直接插入排序减少元素移动次数的改进也正体现在这里。从道理上理解,我们前面的每一次间隔排序都使整个数列从整体上更有序,这样当我们最后对整个数列进行直接插入排序时,往往要比一开始就使用直接插入排序所进行的工作量(移动元素)要少。

3. 间隔列

上面使用了一个凭空给出的间隔列[701, 301, 132, 57, 23, 10, 4, 1]。经过上面的分析,我们也隐隐能察觉到,如果前一次间隔排序的效果更好,那么对后一次排序直至最后一次对整个数列的排序的工作最减少都有更大的作用。没错,希尔排序性能的好坏,很大程序上取决于使用一组怎样的间隔列,很不幸的是,计算不出一个这样的间隔列,它在给任何数列排序时都能达到最佳效果

那么,退而求其次,目前为止,有一些效佳的间隔列供我们使用,比如上面我们所使用的 [701, 301, 132, 57, 23, 10, 4, 1] 。这是 Marcin CiuraBest Increments for the Average Case of Shellsort一文中提出的一种较佳的希尔排序间隔列策略,这是一个经验间隔列,这表示,没法用一个明确的公式来概括它,这样当我们待排序的数列有10000个元素时,就需要找到10000内的那个最大可用间隔,这显然不太方便。另一个是大家可能听说过的是Knuth’s sequence,用公式表示为(3^k-1)/2,这代表了这样一组间隔[..., 1093, 364, 121, 40, 13 ,4, 1]

这当然不是间隔列的全部故事,正如维基百科Shellsort条目中的一段话:

The question of deciding which gap sequence to use is difficult. Every gap sequence that contains 1 yields a correct sort (as this makes the final pass an ordinary insertion sort); however, the properties of thus obtained versions of Shellsort may be very different. Too few gaps slows down the passes, and too many gaps produces an overhead.

引自 https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

那里也列出了迄今为止,人们所探索的大多数可用间隔列。

4. 代码实现

def shell_sort(collection):
    gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    for gap in gaps:
        for i in range(gap, len(collection)):
            insert_value = collection[i]
            print(insert_value)
            j = i
            while j >= gap and collection[j-gap] > insert_value:
                collection[j] = collection[j-gap]
                j -= gap
            if j != i:
                collection[j] = insert_value
    return collection

if __name__ == "__main__":
    print(*shell_sort([0, 5, 3, 2, 2, 8]))
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Marcin Ciura's gap sequence
const vector<int> gaps({ 701, 301, 132, 57, 23, 10, 4, 1 });

void shell_sort(vector<int>& ivec) {
	auto feat_gap = find_if(gaps.cbegin(), gaps.cend(), 
		[&](auto gap) { return gap < ivec.size(); });

	for (auto gap_iter = feat_gap; gap_iter != gaps.cend(); ++gap_iter) {
		for (int i = *gap_iter; i < ivec.size(); ++i) {
			int insert_value = ivec.at(i);
			int j = i;
			while (j >= *gap_iter && ivec.at(j - *gap_iter) > insert_value) {
				ivec[j] = ivec.at(j - *gap_iter);
				j -= *gap_iter;
			}
			if (j != i)
				ivec[j] = insert_value;
		}
	}
}

int main() {
	//vector<int> nums({ 0, 5, 3, 2, 2, 8 });
	vector<int> nums({ 3, 6, 1, 4, 8, 2 });
	shell_sort(nums);
	for(auto n : nums) 
		cout << n << ", ";
}

从代码中可以看出,内层for是直接插入排序的过程,而外层for控制着每次所生成数列使用之间隔。

5. 参考

Shellsort – Wikipedia

Fastest gap sequence for shell sort?

All Algorithms implemented in Python

ShellSort – GeeksforGeeks