3-Way快速排序（荷兰国旗算法）算法详细代码实现 _快速排序

本文概述

C ++
C#
C ++
C#

简单的QuickSort
在简单快速排序算法中, 我们选择一个元素作为枢轴, 围绕枢轴对数组进行分区, 然后在枢轴的左右两侧递归获得子数组。
考虑具有许多冗余元素的阵列。例如, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 1, 4, 4, 4}。如果在"简单快速排序"中选择4作为枢轴, 我们将只修复一个4并递归处理剩余的事件。
3种方式的快速排序的想法是处理枢轴的所有事件, 它基于
荷兰国旗算法。

In 3 Way QuickSort, an array arr[l..r] is divided in 3 parts: a) arr[l..i] elements less than pivot. b) arr[i+1..j-1] elements equal to pivot. c) arr[j..r] elements greater than pivot.

【3-Way快速排序（荷兰国旗算法）算法详细代码实现】下面是上述算法的实现。
C ++

// C++ program for 3-way quick sort #include < bits/stdc++.h> using namespace std; /* This function partitions a[] in three parts a) a[l..i] contains all elements smaller than pivot b) a[i+1..j-1] contains all occurrences of pivot c) a[j..r] contains all elements greater than pivot */ void partition( int a[], int l, int r, int & i, int & j) { i = l - 1, j = r; int p = l - 1, q = r; int v = a[r]; while ( true ) { // From left, find the first element greater than // or equal to v. This loop will definitely // terminate as v is last element while (a[++i] < v) ; // From right, find the first element smaller than // or equal to v while (v < a[--j]) if (j == l) break ; // If i and j cross, then we are done if (i > = j) break ; // Swap, so that smaller goes on left greater goes // on right swap(a[i], a[j]); // Move all same left occurrence of pivot to // beginning of array and keep count using p if (a[i] == v) { p++; swap(a , a[i]); } // Move all same right occurrence of pivot to end of // array and keep count using q if (a[j] == v) { q--; swap(a[j], a[q]); } } // Move pivot element to its correct index swap(a[i], a[r]); // Move all left same occurrences from beginning // to adjacent to arr[i] j = i - 1; for ( int k = l; k < p; k++, j--) swap(a[k], a[j]); // Move all right same occurrences from end // to adjacent to arr[i] i = i + 1; for ( int k = r - 1; k > q; k--, i++) swap(a[i], a[k]); } // 3-way partition based quick sort void quicksort( int a[], int l, int r) { if (r < = l) return ; int i, j; // Note that i and j are passed as reference partition(a, l, r, i, j); // Recur quicksort(a, l, j); quicksort(a, i, r); } // A utility function to print an array void printarr( int a[], int n) { for ( int i = 0; i < n; ++i) printf ( "%d" , a[i]); printf ( "\n" ); } // Driver code int main() { int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 }; int size = sizeof (a) / sizeof ( int ); // Function Call printarr(a, size); quicksort(a, 0, size - 1); printarr(a, size); return 0; }

// C# program for 3-way quick sort using System; class GFG { // A function which is used to swap values static void swap< T> ( ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; } /* This function partitions a[] in three parts a) a[l..i] contains all elements smaller than pivot b) a[i+1..j-1] contains all occurrences of pivot c) a[j..r] contains all elements greater than pivot */ public static void partition( int [] a, int l, int r, ref int i, ref int j) { i = l - 1; j = r; int p = l - 1, q = r; int v = a[r]; while ( true ) { // From left, find the first element greater // than or equal to v. This loop will definitely // terminate as v is last element while (a[++i] < v) ; // From right, find the first element smaller // than or equal to v while (v < a[--j]) if (j == l) break ; // If i and j cross, then we are done if (i > = j) break ; // Swap, so that smaller goes on left greater // goes on right swap( ref a[i], ref a[j]); // Move all same left occurrence of pivot to // beginning of array and keep count using p if (a[i] == v) { p++; swap( ref a , ref a[i]); } // Move all same right occurrence of pivot to // end of array and keep count using q if (a[j] == v) { q--; swap( ref a[j], ref a[q]); } } // Move pivot element to its correct index swap( ref a[i], ref a[r]); // Move all left same occurrences from beginning // to adjacent to arr[i] j = i - 1; for ( int k = l; k < p; k++, j--) swap( ref a[k], ref a[j]); // Move all right same occurrences from end // to adjacent to arr[i] i = i + 1; for ( int k = r - 1; k > q; k--, i++) swap( ref a[i], ref a[k]); } // 3-way partition based quick sort public static void quicksort( int [] a, int l, int r) { if (r < = l) return ; int i = 0, j = 0; // Note that i and j are passed as reference partition(a, l, r, ref i, ref j); // Recur quicksort(a, l, j); quicksort(a, i, r); } // A utility function to print an array public static void printarr( int [] a, int n) { for ( int i = 0; i < n; ++i) Console.Write(a[i] + " " ); Console.Write( "\n" ); } // Driver code static void Main() { int [] a = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 }; int size = a.Length; // Function Call printarr(a, size); quicksort(a, 0, size - 1); printarr(a, size); } // This code is contributed by DrRoot_ }

输出如下

4944194494414 1144444444999

谢谢乌特卡什建议上述实现。
另一种实现使用荷兰国旗算法
C ++

// C++ program for 3-way quick sort #include < bits/stdc++.h> using namespace std; void swap( int * a, int * b) { int temp = *a; *a = *b; *b = temp; } // A utility function to print an array void printarr( int a[], int n) { for ( int i = 0; i < n; ++i) printf ( "%d " , a[i]); printf ( "\n" ); } /* This function partitions a[] in three parts a) a[l..i] contains all elements smaller than pivot b) a[i+1..j-1] contains all occurrences of pivot c) a[j..r] contains all elements greater than pivot */ // It uses Dutch National Flag Algorithm void partition( int a[], int low, int high, int & i, int & j) { // To handle 2 elements if (high - low < = 1) { if (a[high] < a[low]) swap(& a[high], & a[low]); i = low; j = high; return ; } int mid = low; int pivot = a[high]; while (mid < = high) { if (a[mid] < pivot) swap(& a[low++], & a[mid++]); else if (a[mid] == pivot) mid++; else if (a[mid] > pivot) swap(& a[mid], & a[high--]); } // update i and j i = low - 1; j = mid; // or high+1 } // 3-way partition based quick sort void quicksort( int a[], int low, int high) { if (low > = high) // 1 or 0 elements return ; int i, j; // Note that i and j are passed as reference partition(a, low, high, i, j); // Recur two halves quicksort(a, low, i); quicksort(a, j, high); } // Driver Code int main() { int a[] = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 }; // int a[] = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, 64, // 11, 41}; int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // int a[] = {91, 82, 73, 64, 55, 46, 37, 28, 19, 10}; // int a[] = {4, 9, 4, 4, 9, 1, 1, 1}; int size = sizeof (a) / sizeof ( int ); // Function Call printarr(a, size); quicksort(a, 0, size - 1); printarr(a, size); return 0; }

// C# program for 3-way quick sort using System; class GFG { // A function which is used to swap values static void swap< T> ( ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; } // A utility function to print an array public static void printarr( int [] a, int n) { for ( int i = 0; i < n; ++i) Console.Write(a[i] + " " ); Console.Write( "\n" ); } /* This function partitions a[] in three parts a) a[l..i] contains all elements smaller than pivot b) a[i+1..j-1] contains all occurrences of pivot c) a[j..r] contains all elements greater than pivot */ // It uses Dutch National Flag Algorithm public static void partition( int [] a, int low, int high, ref int i, ref int j) { // To handle 2 elements if (high - low < = 1) { if (a[high] < a[low]) swap( ref a[high], ref a[low]); i = low; j = high; return ; } int mid = low; int pivot = a[high]; while (mid < = high) { if (a[mid] < pivot) swap( ref a[low++], ref a[mid++]); else if (a[mid] == pivot) mid++; else if (a[mid] > pivot) swap( ref a[mid], ref a[high--]); } // update i and j i = low - 1; j = mid; // or high+1 } // 3-way partition based quick sort public static void quicksort( int [] a, int low, int high) { if (low > = high) // 1 or 0 elements return ; int i = 0, j = 0; // Note that i and j are passed as reference partition(a, low, high, ref i, ref j); // Recur two halves quicksort(a, low, i); quicksort(a, j, high); } // Driver code static void Main() { int [] a = { 4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4 }; // int[] a = {4, 39, 54, 14, 31, 89, 44, 34, 59, 64, // 64, 11, 41}; int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, // 10}; int[] a = {91, 82, 73, 64, 55, 46, 37, 28, // 19, 10}; int[] a = {4, 9, 4, 4, 9, 1, 1, 1}; int size = a.Length; // Function Call printarr(a, size); quicksort(a, 0, size - 1); printarr(a, size); } // This code is contributed by DrRoot_ }

输出如下

4 9 4 4 1 9 4 4 9 4 4 1 4 1 1 4 4 4 4 4 4 4 4 9 9 9

谢谢
阿迪亚·戈尔(Aditya Goel)
为此实施。
参考：
http://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf
http://www.sorting-algorithms.com/quick-sort-3-way
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。