本文概述

• C ++
• Java
• Python3
• C#
• C ++
• Java
• Python3
• C#

我们已经讨论了使用Lomuto分区方案的QuickSort。与Hoare方案相比, 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.

【快速排序中的Hoare vs Lomuto分区方案详细介绍】输出如下

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

注意 ：
如果我们更改Hoare的分区以选择最后一个元素作为枢轴, 那么Hoare的分区可能会导致QuickSort无限次递归。例如, {10、5、6、20}并且数据透视为arr [high], 则返回的索引将始终为高, 并会调用相同的QuickSort。要处理随机数据透视, 我们总是可以将随机元素与第一个元素交换, 并且只需遵循上述算法即可。
比较：

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

推荐阅读

• 

  什么是对公负债业务
• 

  做生鲜电商需要办什么营业执照
• 

  威能壁挂炉代码百度如何解决
• 

  拍鸟用什么相机好
• 

  荒野行动物品怎么拆分 如何分开扔掉道具
• 

  黄雅琼个人资料介绍 黄雅琼个人资料介绍
• 

  怎样做稻谷酒
• 

  天山雪菊哪里买 天山雪菊多少钱才能买到
• 

  鹅蛋和什么东西不能吃
• 

  电池容量|骁龙870基本“零差评”，这四款价格两千左右，入手用三年
• 

  mongodb数据库迁移到另一台服务器 mongodb 迁移数据
• 

  紫叶草怎么种植 紫叶草怎么养
• 

  补办车牌号一般几天可以下来
• 

  3m汽车膜分几个档次 汽车贴膜什么牌子好
• 

  前端|实习生 Git 不熟练，还没脸去问是种什么体验
• 

  开发转数据分析,数据分析好还是大数据开发好
• 

  熊童子多肉服盆的注意事项有哪些 多肉熊童子用什么盆好看
• 

  地板出汗怎么办 地板如何去汗，地板如何去汗渍
• 

  冠状沟白色污垢是什么
• 

  mysql中的锁指的是什么 mysql导致锁的原因

• 算法设计（hoax数字介绍和代码实现）
• Python hmac –消息身份验证的键哈希介绍
• OpenCV中的直方图均衡介绍和代码示例
• Linux中的HISTCONTROL命令及示例
• 算法设计（公路广告牌问题解决和代码实现）
• 2021年8个顶级Node.js框架推荐，Web开发必备干货！
• 如何在JavaScript中实现HashMap（详细实现指南）
• 删除不必要的启动条目并加快启动速度的4个工具
• 如果有智慧公交可视化平台，《开端》还能无限重启吗（）