3路快速排序（荷兰国旗问题）

在这里，我们将看到快速排序技术，但我们将使用三路快速排序。基本的快速排序技术只是找到一个元素作为枢轴，然后围绕枢轴对数组进行分区，之后，在枢轴的左右子数组上递归。

三路快速排序类似，但有三个部分。数组arr[1到n]被分为三个部分。

• arr[1到i]
• arr[i + 1, j]
• arr[j + 1, n]

算法

partition(arr, left, right, i, j) −

begin
   if right – left <p>快速排序（arr，左，右） - </p><pre class="brush:php;toolbar:false;">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

Example

的中文翻译为：

示例

#include<iostream>
#include<vector>
using namespace std;
void partition(int arr[], int left, int right, int &i, int &j) {
   if (right - left  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 <h2>输出</h2>
<pre class="brush:php;toolbar:false;">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