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

2021年3月21日17:26:08 发表评论 1,055 次浏览

本文概述

简单的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.

下面是上述算法的实现。

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#

// 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_
}

输出如下

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

谢谢乌特卡什建议上述实现。

另一种实现使用荷兰国旗算法

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#

// 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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: