本文概述
- C ++
- C#
- C ++
- C#
在简单快速排序算法中, 我们选择一个元素作为枢轴, 围绕枢轴对数组进行分区, 然后在枢轴的左右两侧递归获得子数组。
考虑具有许多冗余元素的阵列。例如, {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#
// 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#
// 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
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 推荐（5本最有竞争力的编程书籍）
- 如何实现3路合并排序（代码和算法实现）
- 用Java打印异常消息的3种不同方式
- Win8系统IE10添加flash支持的技巧
- Win8如何运用内置超级管理员账户登录系统？
- Win8下载商店应用时出错0x80200024的处理办法
- Win8系统Fresh Paint点击添加纸张后程序停止响应怎样办？
- Win8虚拟内存无法全部加载如何处理？
- Win8.1系统删除微软账户信息的办法