0%

快速排序中Partition函数的两种实现版本

本文讲述了快速排序算法中Partition函数的两种实现版本:单向扫描和双向扫描。

双向扫描

平时常见的Partition实现版本应该是双向扫描。

该方法将第一个元素设为pivot,先从右到左扫描将小于pivot的元素交换到左边,再从左到右扫描将大于pivot的元素交换到右边,重复这个步骤直到扫描完毕。

C++的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
int partition2(vector<int>& nums, int low, int high) {
int pivot = nums[low];
while (low < high) {
while (low < high && nums[high] > pivot)
high--;
nums[low] = nums[high];
while (low < high && nums[low] < pivot)
low++;
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}

用此算法对[30, 24, 5, 58, 18, 36, 12, 42, 39]做一次划分:

单向扫描

笔者在最小K个数 - 力扣题解中第一次遇见Partition函数的单向扫描实现,特此记录。

该方法将待排序数组分为4部分,比privot小的,比pivot大的,尚未扫描的,pivot:(图中x就是pivot)

该方法的思路是,取最右端的元素为哨兵元素pivot,从下标j开始扫描,把小于pivot的元素都交换在下标i的左边。所以,下标i之前的元素值小于pivot,下标i和下标j之间的元素值大于pivot,下标j之后的元素尚未扫描。

C++的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; j++) {
if (nums[j] < pivot) {
i++;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[r]);
return i + 1;
}

用此算法对[2, 8, 7, 1, 3, 5, 6, 4]进行一次划分:

因为该版本的Partition函数是单向扫描,修改后可用于单链表的划分。

Reference

图解快速排序 - ShangyiChen - 博客园

快速排序之单项扫描法 - 喵星人与汪星人 - 博客园