Isih pantas 3 hala (masalah bendera Belanda)

Di sini kita akan melihat teknik isihan pantas tetapi kita akan menggunakan isihan pantas tiga cara. Teknik quicksort asas hanya mencari elemen sebagai pangsi, kemudian membahagikan tatasusunan di sekeliling pangsi, dan selepas itu, berulang pada subbarray kiri dan kanan pivot.

Isihan pantas tiga hala adalah serupa, tetapi mempunyai tiga bahagian. Tatasusunan arr[1 hingga n] dibahagikan kepada tiga bahagian.

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

algoritma

pembahagian(arr, kiri, kanan, i, j) −

begin
   if right &ndash; 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 &ndash; 1
   j := mid
end

ialah:

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

Salin selepas log masuk

#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);
}

Salin selepas log masuk

Atas ialah kandungan terperinci Isih pantas 3 hala (masalah bendera Belanda). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!