先看一下c++的實作方法:
1、快速排序的描述
快速排序算法采用的分治算法,是以對一個子數組A[p…r]進行快速排序的三個步驟為:
(1)分解:數組A[p...r]被劃分為兩個(可能為空)子數組A[p...q-1]和A[q+1...r],給定一個樞軸,使得A[p...q-1]中的每個元素小于等于A[q],A[q+1...r]中的每個元素大于等于A[q],q下标是在劃分過程中計算得出的。
(2)解決:通過遞歸調用快速排序,對子數組A[p...q-1]和A[q+1...r]進行排序。
(3)合并:因為兩個子數組是就地排序,不需要合并操作,整個數組A[p…r]排序完成。
快速排序關鍵過程是對數組進行劃分,劃分過程需要選擇一個主元素(pivot element)作為參照,圍繞着這個主元素進劃分子數組。舉個列說明如何劃分數組,現有子數組A={24,15,27,5,43,87,34},以最後一個元素為主元素進行劃分,劃分過程如圖所示:
PARTITION(A,p,r)
//将最後一個元素作為主元素
i = p-1
for j=p to r-1 //從第一個元素開始到倒數第二個元素結束,比較确定主元的位置
do if A[j] <= x
i = i+1
exchange A[i] <-> A[j]
//最終确定主元的位置
return i+1 //傳回主元的位置
根據劃分過程的為代碼,書中又給出了快速排序的為代碼:
1 QUICKSORT(A,p,r)
2 if p<r
3 q = PARTITION(A,p,r) //确定劃分位置
4 QUICKSORT(A,p,q-1) //子數組A[p...q-1]
5 QUICKSORT(Q,q+1,r) //子數組A[q+1...r]
好了 了解了就可以根據僞代碼來寫測試:
#include<iostream>
using namespace std;
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//劃分數組
int partition(int a[], int begin, int last)
{
int x = a[last];
int i = begin - 1;
for (int j = begin; j < last; j++)
{
if (x <= a[j])
{
i=i+1;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[last]);
return (i + 1);
}
//利用遞歸排序
void quick_sort(int a[], int begin, int last)
{
if (begin < last)
{
int q = partition(a, begin, last);
quick_sort(a, begin, q-1);
quick_sort(a, q + 1, last);
}
}
int main()
{
int i;
int a[] = { 88, 1, 22, 99, 55, 77, 33, 66, 44, 70 };
"After the quick sort,the data is:" << endl;
quick_sort(a, 0, 9);
for (const auto i : a)
" ";
cout << endl;
return 0;
}
2.go語言的方法
先說明這個快速排序法的概念,它以最右邊的值s作比較的标準,将整個數列分為三個部份,一個是小于s的部份,一個是大于s的部份,一個是未處理的部份,如下所示 :
在排序的過程中,i 與 j 都會不斷的往右進行比較與交換,最後數列會變為以下的狀态:
然後将s的值置于中間,接下來就以相同的步驟會左右兩邊的數列進行排序的動作,如下所示:
整個演算的過程,直接摘錄書中的虛拟碼來作說明:
QUICKSORT(A, p, r) if p < r
then q <- PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
end QUICKSORT
PARTITION(A, p, r)
x <- A[r]
i <- p-1
for j <- p to r-1
do if A[j] <= x
then i <- i+1
exchange A[i]<->A[j]
exchange A[i+1]<->A[r]
return i+1
end PARTITION
一個實際例子的演算如下所示:
package main
import (
"fmt"
)
const MAX = 10
var sortArray = []int{41, 24, 76, 11, 45, 64, 21, 69, 19, 36}
func main() {
fmt.Println("before sort:")
show()
quickSort(sortArray, 0, MAX-1)
fmt.Println("after sort:")
show()
}
func quickSort(sortArray []int, left, right int) {
if left < right {
pos := partition(sortArray, left, right)
partition(sortArray, left, pos-1)
partition(sortArray, pos+1, right)
}
}
func partition(sortArray []int, left, right int) int {
key := sortArray[right]
i := left - 1
for j := left; j < right; j++ {
if sortArray[j] <= key {
i++
swap(i, j)
}
}
swap(i+1, right)
return i + 1
}
// Swap the position of a and b
func swap(a, b int) {
sortArray[a], sortArray[b] = sortArray[b], sortArray[a]
}
// foreach
func show() {
for _, value := range sortArray {
fmt.Printf("%d\t", value)
}
}