快速排序与快速选择

快速排序与快速选择

快速排序

本文中的快速排序算法来自于 YouTube 视频:Quicksort

中心思想

快速排序的思想是分而治之。随机选取一个元素 pivot,然后对数据进行原地重排,使得数据变为如下形式:pivot 左侧元素均比 pivot 小,右侧元素均比它大。然后分别对左右两侧的元素进行该操作,不断递归。

通常选取数组最后一个元素作为 pivot,但是最坏情况的时间复杂度会达到 O(n2),优化方法是随机选取 pivot 后与最后的元素进行交换。

算法流程

对于长度为 n - 1 的数组,定义以下三个值。

pivot:位于 n - 1 的元素(序列最后一个元素),是进行数组分割的中间值。

spliter:是最终分割序列的元素位置,从 0 开始。每次发现位于 current 的元素小于 pivot 时向后移动 1;完成一次排序扫描后,将 pivot 元素交换至 spliter 位置,分别对其分割出的前后元素序列进行递归排序。

current:当前进行比较的元素位置,从 0 开始,在循环中向后不断移动。每次循环中此元素与 pivot 比较,如果小于 pivot 则与 spliter 位置的元素进行交换。最后在 pivot 前停止。

开始时 spliter = current = 0,arr[current] = 5 < pivot = 6,交换 arr[spliter] 与 arr[current],实际上没有发生交换;spliter++。

现在 spliter = current = 1,arr[current] = 2 < pivot = 6,交换,spliter++。

过程同上。

此时 spliter = current = 3,arr[current] = 7 > pivot = 6,不进行交换。

此时 spliter = 3,current = 4,arr[current] = 3 < pivot = 6,需要交换 arr[current] 与 arr[spliter],并且 spliter++。

交换完成后 spliter = current = 4。此时 current 元素位于 pivot 之前一位,循环结束。需要将 arr[current] 与 pivot 元素进行交换。

交换完成后,本次 quickSort 函数调用结束。

本次函数运行的结果:pivot 位于两端序列中间,前面的序列元素均比 pivot 小,后面的序列元素均比 pivot 大。此时分别对这两段序列运行 quickSort 函数。

前一段的子序列排序完成后,序列再次被位于 spliter 位置的 pivot 分开,再次对前后两个序列进行分别递归。

对于长度为 0 或 1 的序列,需要进行额外判断,以防止递归出错。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T>
void quickSort(T *t, int n)
{
if (n <= 1)
{
return;
}
int split = 0;
for (int i = 0; i < n - 1; i++)
{
if (t[i] < t[n - 1])
{
swap(t[i], t[split]);
split++;
}
}
swap(t[split], t[n - 1]);
quickSort(t, split);
quickSort(t + split + 1, n - split - 1);
}

快速选择

快速选择是一种从序列中选取大小为第 n 位的元素的方法。快速排序和快速选择都是 C. A. R. Hoare (东尼霍尔)提出的,二者也有相似之处。

快速选择的总体思路与快速排序一致,选择一个元素作为基准来对元素进行分区,将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是,快速选择并不递归访问双边,而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度,从O(nlogn)至O(n),不过最坏情况仍然是O(n2)。

以上引自维基百科

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
template <class T>
T quickSelect(T *t, int n, int idx, int des)
{
if (n <= 1)
{
if (idx + n == des)
{
return *(t + n);
}
}
int split = 0;
for (int i = 0; i < n - 1; i++)
{
if (t[i] < t[n - 1])
{
swap(t[i], t[split]);
split++;
}
}
swap(t[split], t[n - 1]);
if (idx + split == des)
{
return *(t + split);
}
else if (idx + split > des)
{
return quickSelect(t, split, idx, des);
}
else
{
return quickSelect(t + split + 1, n - split - 1, idx + split + 1, des);
}
}