# 快速排序中的Hoare vs Lomuto分区方案详细介绍

## 本文概述

Lomuto的分区方案：

``````partition(arr[], lo, hi)
pivot = arr[hi]
i = lo     // place for swapping
for j := lo to hi – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[hi]
return i``````

## C ++

``````/* C++ implementation QuickSort using Lomuto's partition
Scheme.*/
#include<bits/stdc++.h>
using namespace std;

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition( int arr[], int low, int high)
{
int pivot = arr[high];    // pivot
int i = (low - 1);  // Index of smaller element

for ( int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;    // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted, low  --> Starting index, high  --> Ending index */
void quickSort( int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void printArray( int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf ( "%d " , arr[i]);
printf ( "\n" );
}

// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof (arr)/ sizeof (arr[0]);
quickSort(arr, 0, n-1);
printf ( "Sorted array: \n" );
printArray(arr, n);
return 0;
}``````

## Java

``````// Java implementation QuickSort
// using Lomuto's partition Scheme
import java.io.*;

class GFG
{
static void Swap( int [] array, int position1, int position2)
{
// Swaps elements in an array

// Copy the first position's element
int temp = array[position1];

// Assign to the second element
array[position1] = array[position2];

// Assign to the first element
array[position2] = temp;
}

/* This function takes last element as
pivot, places the pivot element at its
correct position in sorted array, and
places all smaller (smaller than pivot)
to left of pivot and all greater elements
to right of pivot */
static int partition( int []arr, int low, int high)
{
int pivot = arr[high];

// Index of smaller element
int i = (low - 1 );

for ( int j = low; j <= high- 1 ; j++)
{
// If current element is smaller
// than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of
// smaller element
Swap(arr, i, j);
}
}
Swap(arr, i + 1 , high);
return (i + 1 );
}

/* The main function that
implements QuickSort
arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */
static void quickSort( int []arr, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1 );
quickSort(arr, pi + 1 , high);
}
}

/* Function to print an array */
static void printArray( int []arr, int size)
{
int i;
for (i = 0 ; i < size; i++)
System.out.print( " " + arr[i]);
System.out.println();
}

// Driver Code
static public void main (String[] args)
{
int []arr = { 10 , 7 , 8 , 9 , 1 , 5 };
int n = arr.length;
quickSort(arr, 0 , n- 1 );
System.out.println( "Sorted array: " );
printArray(arr, n);
}
}

// This code is contributed by vt_m.``````

## Python3

``````''' Python3 implementation QuickSort using Lomuto's partition
Scheme.'''

''' This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot '''
def partition(arr, low, high):

# pivot
pivot = arr[high]

# Index of smaller element
i = (low - 1 )
for j in range (low, high):

# If current element is smaller than or
# equal to pivot
if (arr[j] < = pivot):

# increment index of smaller element
i + = 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1 ], arr[high] = arr[high], arr[i + 1 ]
return (i + 1 )

''' The main function that implements QuickSort
arr --> Array to be sorted, low --> Starting index, high --> Ending index '''
def quickSort(arr, low, high):
if (low < high):

''' pi is partitioning index, arr[p] is now
at right place '''
pi = partition(arr, low, high)

# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi - 1 )
quickSort(arr, pi + 1 , high)

''' Function to pran array '''
def printArray(arr, size):

for i in range (size):
print (arr[i], end = " " )
print ()

# Driver code

arr = [ 10 , 7 , 8 , 9 , 1 , 5 ]
n = len (arr)
quickSort(arr, 0 , n - 1 )
print ( "Sorted array:" )
printArray(arr, n)

# This code is contributed by SHUBHAMSINGH10``````

## C#

``````// C# implementation QuickSort
// using Lomuto's partition Scheme
using System;

class GFG
{
static void Swap( int [] array, int position1, int position2)
{
// Swaps elements in an array

// Copy the first position's element
int temp = array[position1];

// Assign to the second element
array[position1] = array[position2];

// Assign to the first element
array[position2] = temp;
}

/* This function takes last element as
pivot, places the pivot element at its
correct position in sorted array, and
places all smaller (smaller than pivot)
to left of pivot and all greater elements
to right of pivot */
static int partition( int []arr, int low, int high)
{
int pivot = arr[high];

// Index of smaller element
int i = (low - 1);

for ( int j = low; j <= high- 1; j++)
{
// If current element is smaller
// than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of
// smaller element
Swap(arr, i, j);
}
}
Swap(arr, i + 1, high);
return (i + 1);
}

/* The main function that
implements QuickSort
arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */
static void quickSort( int []arr, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
static void printArray( int []arr, int size)
{
int i;
for (i = 0; i < size; i++)
Console.Write( " " + arr[i]);
Console.WriteLine();
}

// Driver Code
static public void Main()
{
int []arr = {10, 7, 8, 9, 1, 5};
int n = arr.Length;
quickSort(arr, 0, n-1);
Console.WriteLine( "Sorted array: " );
printArray(arr, n);
}
}

// This code is contributed by vt_m.``````

``````Sorted array:
1 5 7 8 9 10``````

Hoare的分区方案：

``````partition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1  // Initialize left index
j = hi + 1  // Initialize right index

// Find a value in left side greater
// than pivot
do
i = i + 1
while arr[i] < pivot

// Find a value in right side smaller
// than pivot
do
j--;
while (arr[j] > pivot);

if i >= j then
return j

swap arr[i] with arr[j]``````

## C ++

``````/* C++ implementation of QuickSort using Hoare's
partition scheme. */
#include <bits/stdc++.h>
using namespace std;

/* This function takes first element as pivot, and places
all the elements smaller than the pivot on the left side
and all the elements greater than the pivot on
the right side. It returns the index of the last element
on the smaller side*/
int partition( int arr[], int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;

while ( true ) {
// Find leftmost element greater than
// or equal to pivot
do {
i++;
} while (arr[i] < pivot);

// Find rightmost element smaller than
// or equal to pivot
do {
j--;
} while (arr[j] > pivot);

// If two pointers met.
if (i >= j)
return j;

swap(arr[i], arr[j]);
}
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted, low  --> Starting index, high  --> Ending index */
void quickSort( int arr[], int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
void printArray( int arr[], int n)
{
for ( int i = 0; i < n; i++)
printf ( "%d " , arr[i]);
printf ( "\n" );
}

// Driver Code
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof (arr) / sizeof (arr[0]);
quickSort(arr, 0, n - 1);
printf ( "Sorted array: \n" );
printArray(arr, n);
return 0;
}``````

## Java

``````// Java implementation of QuickSort
// using Hoare's partition scheme
import java.io.*;

class GFG {

/* This function takes first element as pivot, and
places all the elements smaller than the pivot on the
left side and all the elements greater than the pivot
on the right side. It returns the index of the last
element on the smaller side*/
static int partition( int [] arr, int low, int high)
{
int pivot = arr[low];
int i = low - 1 , j = high + 1 ;

while ( true ) {
// Find leftmost element greater
// than or equal to pivot
do {
i++;
} while (arr[i] < pivot);

// Find rightmost element smaller
// than or equal to pivot
do {
j--;
} while (arr[j] > pivot);

// If two pointers met.
if (i >= j)
return j;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// swap(arr[i], arr[j]);
}
}

/* The main function that
implements QuickSort
arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */
static void quickSort( int [] arr, int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[p] is now at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi);
quickSort(arr, pi + 1 , high);
}
}

/* Function to print an array */
static void printArray( int [] arr, int n)
{
for ( int i = 0 ; i < n; i++)
System.out.print( " " + arr[i]);
System.out.println();
}

// Driver Code
static public void main(String[] args)
{
int [] arr = { 10 , 7 , 8 , 9 , 1 , 5 };
int n = arr.length;
quickSort(arr, 0 , n - 1 );
System.out.println( "Sorted array: " );
printArray(arr, n);
}
}

// This code is contributed by vt_m.``````

## Python3

``````''' Python implementation of QuickSort using Hoare's
partition scheme. '''

''' This function takes first element as pivot, and places
all the elements smaller than the pivot on the left side
and all the elements greater than the pivot on
the right side. It returns the index of the last element
on the smaller side '''

def partition(arr, low, high):

pivot = arr[low]
i = low - 1
j = high + 1

while ( True ):

# Find leftmost element greater than
# or equal to pivot
i + = 1
while (arr[i] < pivot):
i + = 1

# Find rightmost element smaller than
# or equal to pivot
j - = 1
while (arr[j] > pivot):
j - = 1

# If two pointers met.
if (i > = j):
return j

arr[i], arr[j] = arr[j], arr[i]

''' The main function that implements QuickSort
arr --> Array to be sorted, low --> Starting index, high --> Ending index '''

def quickSort(arr, low, high):
''' pi is partitioning index, arr[p] is now
at right place '''
if (low < high):

pi = partition(arr, low, high)

# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi)
quickSort(arr, pi + 1 , high)

''' Function to pran array '''

def printArray(arr, n):
for i in range (n):
print (arr[i], end = " " )
print ()

# Driver code
arr = [ 10 , 7 , 8 , 9 , 1 , 5 ]
n = len (arr)
quickSort(arr, 0 , n - 1 )
print ( "Sorted array:" )
printArray(arr, n)

# This code is contributed by shubhamsingh10``````

## C#

``````// C# implementation of QuickSort
// using Hoare's partition scheme
using System;

class GFG {

/* This function takes first element as pivot, and
places all the elements smaller than the pivot on the
left side and all the elements greater than the pivot
on the right side. It returns the index of the last
element on the smaller side*/
static int partition( int [] arr, int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;

while ( true ) {
// Find leftmost element greater
// than or equal to pivot
do {
i++;
} while (arr[i] < pivot);

// Find rightmost element smaller
// than or equal to pivot
do {
j--;
} while (arr[j] > pivot);

// If two pointers met.
if (i >= j)
return j;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// swap(arr[i], arr[j]);
}
}

/* The main function that
implements QuickSort
arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */
static void quickSort( int [] arr, int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[p] is now at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */
static void printArray( int [] arr, int n)
{
for ( int i = 0; i < n; i++)
Console.Write( " " + arr[i]);
Console.WriteLine();
}

// Driver Code
static public void Main()
{
int [] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.Length;
quickSort(arr, 0, n - 1);
Console.WriteLine( "Sorted array: " );
printArray(arr, n);
}
}

// This code is contributed by vt_m.``````

``````Sorted array:
1 5 7 8 9 10``````

1. Hoare的方案比Lomuto的分区方案效率更高, 因为它的交换次数平均减少了三倍, 即使所有值都相等, 它也可以创建有效的分区。
2. 与Lomuto的分区方案一样, Hoare分区也会使输入数组已经排序后, 快速排序降级为O(n ^ 2), 也不会产生稳定的排序。
3. 请注意, 在此方案中, 枢轴的最终位置不一定在返回的索引处, 并且主要算法重复出现的下两个段分别是(lo..p)和(p + 1..hi) (lo..p-1)和(p + 1..hi), 就像Lomuto的方案一样。

• 回顶