在这里，我们将看到快速排序技术，但我们将使用三路快速排序。基本的快速排序技术只是找到一个元素作为枢轴，然后围绕枢轴对数组进行分区，之后，在枢轴的左右子数组上递归。
三路快速排序类似，但有三个部分。数组arr[1到n]被分为三个部分。
arr[1到i]arr[i + 1, j]arr[j + 1, n]
算法
partition(arr, left, right, i, j) −
begin if right – left <= 1, then if arr[right] < arr[left], then swap arr[right] and arr[left] i := left j := right return end if mid := left, pivot = arr[right] while mid <= right, do if arr[mid] < pivot, then swap arr[left], arr[mid] increase left and mid by 1 else if arr[mid] = pivot, then increase mid by 1 else swap arr[mid], arr[right] decrease right by 1 done i := left – 1 j := midend
快速排序（arr，左，右） –
begin if left >= right, then return end if define i and j partition(arr, left, right, i, j) quicksort(arr, left, i) quicksort(arr, j, right)end
Example
的中文翻译为：
示例
#include#includeusing namespace std;void partition(int arr[], int left, int right, int &i, int &j) { if (right - left <= 1) { if (arr[right] < arr[left]) swap(arr[right], arr[left]); i = left; j = right; return;}int mid = left;int pivot = arr[right];while (mid <= right) { if (arr[mid] pivot) swap(arr[mid], arr[right--]); } i = left-1; j = mid;}void quicksort(int arr[], int left, int right) { if (left >= right) //1 or 0 elements return; int i, j; partition(arr, left, right, i, j); quicksort(arr, left, i); quicksort(arr, j, right);}void display(int arr[], int n) { for (int i = 0; i < n; ++i) cout << " " << arr[i]; cout << endl;}int main() { int a[] = {4, 9, 4, 3, 1, 9, 4, 3, 9, 4, 3, 1, 4}; int n = sizeof(a) / sizeof(int); display(a, n); quicksort(a, 0, n - 1); display(a, n);}
输出
4 9 4 3 1 9 4 3 9 4 3 1 41 1 3 3 3 4 4 4 4 4 9 9 9
以上就是3路快速排序（荷兰国旗问题）的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445323.html
微信扫一扫 
支付宝扫一扫 
