3向QuickSort（荷兰国旗）
在这里，我们将看到快速排序技术，但我们将使用三向快速排序。基本的快速排序技术只是找到一个元素作为枢轴，然后围绕枢轴对数组进行分区，然后再对枢轴左右两侧的子数组进行递归。
三向快速排序类似，但分为三个部分。数组arr[1到n]分为三个部分。
arr[1至i]
arr[i+1，j]
arr[j+1，n]
算法
分区(arr,left,right,i,j)-
begin
if right – left <= 1, then
if arr[right] < arr[left], then
swap arr[right] and arr[left]
i := left
j := right
return
end if
mid := left, pivot = arr[right]
while mid <= right, do
if arr[mid] < pivot, then
swap arr[left], arr[mid]
increase left and mid by 1
else if arr[mid] = pivot, then increase mid by 1
else
swap arr[mid], arr[right]
decrease right by 1
done
i := left – 1
j := mid
endquicksort(arr,left,right)-
begin
if left >= right, then
return
end if
define i and j
partition(arr, left, right, i, j)
quicksort(arr, left, i)
quicksort(arr, j, right)
end示例
#include<iostream>
#include<vector>
using namespace std;
void partition(int arr[], int left, int right, int &i, int &j) {
if (right - left <= 1) {
if (arr[right] < arr[left])
swap(arr[right], arr[left]);
i = left;
j = right;
return;
}
int mid = left;
int pivot = arr[right];
while (mid <= right) {
if (arr[mid]<pivot)
swap(arr[left++], arr[mid++]);
else if (arr[mid]==pivot)
mid++;
else if (arr[mid] > pivot)
swap(arr[mid], arr[right--]);
}
i = left-1;
j = mid;
}
void quicksort(int arr[], int left, int right) {
if (left >= right) //1 or 0 elements
return;
int i, j;
partition(arr, left, right, i, j);
quicksort(arr, left, i);
quicksort(arr, j, right);
}
void display(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << " " << arr[i];
cout << endl;
}
int main() {
int a[] = {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4};
int n = sizeof(a) / sizeof(int);
display(a, n);
quicksort(a, 0, n - 1);
display(a, n);
}输出结果
4 9 4 3 1 9 4 3 9 4 3 1 4 1 1 3 3 3 4 4 4 4 4 9 9 9