資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究3 路快速排序（荷蘭國旗）
在此，我們將看到快速排序技術，但我們將使用三路快速排序。基本快速排序技術只是將一個元素作為中心點，然後基於中心點對陣列進行分割槽，之後，對中心點左右兩側的子陣列進行遞迴。
三路快速排序類似，但有三個部分。將陣列 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 := mid end
quicksort(arr, left, right) −
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
示例
#include<iostream>
#include<vector>
using 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[left++], arr[mid++]);
else if (arr[mid]==pivot)
mid++;
else 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 4 1 1 3 3 3 4 4 4 4 4 9 9 9
更新時間：20-08-2019
2K+ 檢視
廣告