時(shí)間復(fù)雜度，平均O（nlogn），最壞O（n)；

不穩(wěn)定的算法

1、算法思想

??? 快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。

（1） 分治法的基本思想

??? 分治法的基本思想是：將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。

（2）快速排序的基本思想

??? 設(shè)當(dāng)前待排序的無(wú)序區(qū)為R[low..high]，利用分治法可將快速排序的基本思想描述為：

①分解：

在R[low..high]中任選一個(gè)記錄作為基準(zhǔn)(Pivot)，以此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左、右兩個(gè)較小的子區(qū)間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區(qū)間中所有記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄(不妨記為pivot)的關(guān)鍵字pivot.key，右邊的子區(qū)間中所有記錄的關(guān)鍵字均大于等于pivot.key，而基準(zhǔn)記錄pivot則位于正確的位置(pivotpos)上，它無(wú)須參加后續(xù)的排序。

注意：

??? 劃分的關(guān)鍵是要求出基準(zhǔn)記錄所在的位置pivotpos。劃分的結(jié)果可以簡(jiǎn)單地表示為(注意pivot=R[pivotpos])：

??? R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys

????????????????? 其中l(wèi)ow≤pivotpos≤high。

②求解：

通過(guò)遞歸調(diào)用快速排序?qū)ψ蟆⒂易訁^(qū)間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。

③組合：

因?yàn)楫?dāng)"求解"步驟中的兩個(gè)遞歸調(diào)用結(jié)束時(shí)，其左、右兩個(gè)子區(qū)間已有序。對(duì)快速排序而言，"組合"步驟無(wú)須做什么，可看作是空操作。

1、如無(wú)序數(shù)組[3 2 4 1 5 9]

a),先把第一項(xiàng)[3]取出來(lái),

用[3]依次與其余項(xiàng)進(jìn)行比較,

如果比[3]小就放[3]前邊,2 1 都比[3]小,所以全部放到[3]前邊

如果比[3]大就放[3]后邊,4 5 9比[3]大,放到[3]后邊

一趟排完后變成下邊這樣:

排序前 3 2 4 1 5 9

排序后 2 1 3 4 5 9

b),對(duì)前半拉[2 1]繼續(xù)進(jìn)行快速排序

重復(fù)步驟a)【取第一項(xiàng) 2與其余項(xiàng)比較】后變成下邊這樣:

排序前 2 1

排序后 1 2

前半拉排序完成。

c),對(duì)后半拉[4 5 9]繼續(xù)進(jìn)行快速排序

重復(fù)步驟a)【取第一項(xiàng) 4與其余項(xiàng)比較】后變成下邊這樣:

排序前 4 5 9

排序后 4 5 9

d),對(duì)后半拉[5 9]繼續(xù)進(jìn)行快速排序

重復(fù)步驟a)【取第一項(xiàng) 5與其余項(xiàng)比較】后變成下邊這樣:

排序前 5 9

排序后 5 9

d在這個(gè)例子中可以忽略，但是當(dāng)后面的數(shù)字較小時(shí)就得必不可少的循環(huán)繼續(xù)下去。

前半拉排序完成。

總的排序也完成:

排序前:[3 2 4 1 5 9]

排序后:[1 2 3 4 5 9]

2、快速排序算法QuickSort

? void QuickSort(SeqList R，int low，int high)

?? { //對(duì)R[low..high]快速排序

???? int pivotpos； //劃分后的基準(zhǔn)記錄的位置

???? if(low<high){//僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序

??????? pivotpos=Partition(R，low，high)； //對(duì)R[low..high]做劃分

??????? QuickSort(R，low，pivotpos-1)； //對(duì)左區(qū)間遞歸排序

??????? QuickSort(R，pivotpos+1，high)； //對(duì)右區(qū)間遞歸排序

????? }

??? } //QuickSort

? 注意：

??? 為排序整個(gè)文件，只須調(diào)用QuickSort(R，1，n)即可完成對(duì)R[l..n]的排序。

具體算法實(shí)現(xiàn)：

1: int partition(int R[], int low, int high) 2: {//對(duì)R[low..high]做劃分 3: int pivot = R[low]; 4: int tmp =0; 5:? 6: // int i = low, j= high ; 7: // print(R+low,high-low+1); 8:? 9: while(low < high) 10: { 11: while( low <high &&R[high] >= pivot) 12: --high ; 13: swap(R[low] ,R[high]); 14:? 15: while (low < high && R[low] <= pivot ) 16: ++low; 17: swap(R[low] ,R[high]); 18:? 19: 20: } 21:? 22:? 23: //print(R+i,j-i+1); 24: 25: return high; 26: } 27: void quick_sort_z(int R[] ,int low ,int high) 28: { 29: int pivot_pos; //劃分后的基準(zhǔn)記錄的位置 30: if(low<high){ //僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序 31: pivot_pos = partition(R ,low, high); //對(duì)R[low..high]做劃分 32: // cout<<pivot_pos <<endl; 33: quick_sort_z(R, low, pivot_pos-1); //對(duì)左區(qū)間遞歸排序 34: quick_sort_z(R, pivot_pos+1, high);//對(duì)右區(qū)間遞歸排序 35: } 36: } 37:? 38: void quick_sort(int R[], int low, int high) 39: { 40: quick_sort_z(R,low,high); 41: }

?

另一種partion算法實(shí)現(xiàn)：以最后一個(gè)元素作為基準(zhǔn)

1: int partition_a(int data[],int lo,int hi) 2: { 3: int key=data[hi]; //以最后一個(gè)元素，data[hi]為主元 4: int i=lo-1; 5: for(int j=lo;j<hi;j++) ///注，j從p指向的是r-1，不是r。 6: { 7: if(data[j]<=key) 8: { 9: i=i+1; 10: swap(data[i],data[j]); 11: } 12: } 13: swap(data[i+1],data[hi]); 14: return i+1; 15: }

完整的源代碼（VS2010編譯）：

1: // code-summary.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。 2:? 3: /************************************************************************** 4: * Copyright (c) 2013, All rights reserved. 5: * 文件名稱 : code-summary.cpp 6: * 文件標(biāo)識(shí) : 7: * 摘 要 : 快速排序算法 8: * 9: * 當(dāng)前版本 : Ver 1.0 10: * 作者 : 徐冬冬 11: * 完成日期 : 2013/05/10 12: * 13: * 取代版本 : 14: * 原作者 : 15: * 完成日期 : 16: * 開(kāi)放版權(quán) : GNU General Public License GPLv3 17: *************************************************************************/ 18: #include "stdafx.h" 19:? 20: #include <iostream> 21: #include <random> 22: #include <stdlib.h> 23: using namespace std; 24:? 25: //快速排序 26:? 27: void init(int a[], int len) 28: { 29: int i =0; 30: for( i=0; i<len ;i++) 31: { 32: a[i]= rand(); 33: } 34: return ; 35: } 36: void print(int *a, int len) 37: { 38: int i =0; 39: for( i=0; i<len; i++) 40: { 41: cout << a[i] <<'\t'; 42: } 43: cout << endl; 44: return ; 45: } 46: void swap(int &a, int &b) 47: { 48: int tmp =a; 49: a = b; 50: b=tmp; 51: return ; 52: } 53: int partition(int R[], int low, int high) 54: {//對(duì)R[low..high]做劃分 55: int pivot = R[low]; 56: int tmp =0; 57:? 58: // int i = low, j= high ; 59: // print(R+low,high-low+1); 60:? 61: while(low < high) 62: { 63: while( low <high &&R[high] >= pivot) 64: --high ; 65: swap(R[low] ,R[high]); 66:? 67: while (low < high && R[low] <= pivot ) 68: ++low; 69: swap(R[low] ,R[high]); 70:? 71: 72: } 73:? 74:? 75: //print(R+i,j-i+1); 76: 77: return high; 78: } 79:? 80: int partition_a(int data[],int lo,int hi) 81: { 82: int key=data[hi]; //以最后一個(gè)元素，data[hi]為主元 83: int i=lo-1; 84: for(int j=lo;j<hi;j++) ///注，j從p指向的是r-1，不是r。 85: { 86: if(data[j]<=key) 87: { 88: i=i+1; 89: swap(data[i],data[j]); 90: } 91: } 92: swap(data[i+1],data[hi]); 93: return i+1; 94: } 95:? 96: void quickSort(int R[] ,int low ,int high) 97: { 98: int pivot_pos; //劃分后的基準(zhǔn)記錄的位置 99: if(low<high){ //僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序 100: pivot_pos = partition(R ,low, high); //對(duì)R[low..high]做劃分 101: // cout<<pivot_pos <<endl; 102: quickSort(R, low, pivot_pos-1); //對(duì)左區(qū)間遞歸排序 103: quickSort(R, pivot_pos+1, high);//對(duì)右區(qū)間遞歸排序 104: } 105: } 106:? 107: void quickSort_a(int R[] ,int low ,int high) 108: { 109: int pivot_pos; //劃分后的基準(zhǔn)記錄的位置 110: if(low<high){ //僅當(dāng)區(qū)間長(zhǎng)度大于1時(shí)才須排序 111: pivot_pos = partition_a(R ,low, high); //對(duì)R[low..high]做劃分 112: // cout<<pivot_pos <<endl; 113: quickSort_a(R, low, pivot_pos-1); //對(duì)左區(qū)間遞歸排序 114: quickSort_a(R, pivot_pos+1, high);//對(duì)右區(qū)間遞歸排序 115: } 116: } 117: void quick_sort(int R[], int low, int high) 118: { 119: quickSort(R,low,high); 120: } 121:? 122: void quick_sort_a(int R[], int low, int high) 123: { 124: quickSort_a(R,low,high); 125: } 126:? 127:? 128: int _tmain(int argc, _TCHAR* argv[]) 129: { 130: int *arr = new int[10]; 131: init(arr, 10); 132: print(arr, 10); 133: quick_sort(arr,0,9); 134: print(arr, 10 ); 135:? 136: init(arr, 10); 137: print(arr, 10); 138: quick_sort_a(arr,0,9); 139: print(arr, 10 ); 140:? 141: system("pause"); 142: return 0; 143: } 144:?

?

?

參考資料：

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.1.htm

http://www.cnblogs.com/kkun/archive/2011/11/23/2260270.html

http://blog.csdn.net/v_july_v/article/details/6262915

轉(zhuǎn)載于:https://www.cnblogs.com/xuddong/archive/2013/05/10/3072160.html

總結(jié)

以上是生活随笔為你收集整理的交换排序-经典的快速排序算法总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。