基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
公司主營(yíng)業(yè)務(wù)：網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)建站是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)建站推出西湖免費(fèi)做網(wǎng)站回饋大家。
快速排序算法通過多次比較和交換來實(shí)現(xiàn)排序，其排序流程如下：
(1)首先設(shè)定一個(gè)分界值，通過該分界值將數(shù)組分成左右兩部分。
(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
(3)然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理
(4)重復(fù)上述過程，可以看出，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。
下面通過一個(gè)例子介紹快速排序算法的思想，假設(shè)要對(duì)數(shù)組a[10]={6，1，2，7，9，3，4，5，10，8}進(jìn)行排序，首先要在數(shù)組中選擇一個(gè)數(shù)作為基準(zhǔn)值，這個(gè)數(shù)可以隨意選擇，在這里，我們選擇數(shù)組的第一個(gè)元素a[0]=6作為基準(zhǔn)值，接下來，我們需要把數(shù)組中小于6的數(shù)放在左邊，大于6的數(shù)放在右邊，怎么實(shí)現(xiàn)呢？
我們?cè)O(shè)置兩個(gè)“哨兵”，記為“哨兵i”和“哨兵j”，他們分別指向數(shù)組的第一個(gè)元素和最后一個(gè)元素，即i=0，j=9。首先哨兵j開始出動(dòng)，哨兵j一步一步地向左挪動(dòng)（即j–），直到找到一個(gè)小于6的數(shù)停下來。接下來哨兵i再一步一步向右挪動(dòng)（即i++），直到找到一個(gè)數(shù)大于6的數(shù)停下來。
最后哨兵j停在了數(shù)字5面前，哨兵i停在了數(shù)字7面前。此時(shí)就需要交換i和j指向的元素的值。
交換之后的數(shù)組變?yōu)閍[10]={6，1，2，5，9，3，4，7，10，8}：
第一次交換至此結(jié)束。接下來，由于哨兵i和哨兵j還沒有相遇，于是哨兵j繼續(xù)向前，發(fā)現(xiàn)比6小的4之后停下；哨兵i繼續(xù)向前，發(fā)現(xiàn)比6大的9之后停下，兩者再進(jìn)行交換。交換之后的數(shù)組變?yōu)閍[10]={6，1，2，5，4，3，9，7，10，8}。
第二次交換至此結(jié)束。接下來，哨兵j繼續(xù)向前，發(fā)小比6小的3停下來；哨兵i繼續(xù)向前，發(fā)現(xiàn)i==j了?。。∮谑?，這一輪的探測(cè)就要結(jié)束了，此時(shí)交換a[i]與基準(zhǔn)的值，數(shù)組a就以6為分界線，分成了小于6和大于6的左右兩部分：a[10]={3，1，2，5，4，6，9，7，10，8}。
至此，第一輪快速排序完全結(jié)束，接下來，對(duì)于6左邊的半部分3，1，2，5，4，執(zhí)行以上過程；對(duì)于6右邊的半部分9，7，10，8，執(zhí)行以上過程，直到不可拆分出新的子序列為止。最終將會(huì)得到這樣的序列：1 2 3 4 5 6 7 8 9 10，到此，排序完全結(jié)束。
快速排序的一次劃分算法從兩頭交替搜索，直到low和hight重合，因此其時(shí)間復(fù)雜度是O(n)；而整個(gè)快速排序算法的時(shí)間復(fù)雜度與劃分的趟數(shù)有關(guān)。
理想的情況是，每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列幾乎等分，經(jīng)過log 2 n趟劃分，便可得到長(zhǎng)度為1的子表。這樣，整個(gè)算法的時(shí)間復(fù)雜度為O(nlog 2 n)。
最壞的情況是，每次所選的中間數(shù)是當(dāng)前序列中的最大或最小元素，這使得每次劃分所得的子表中一個(gè)為空表，另一子表的長(zhǎng)度為原表的長(zhǎng)度-1。這樣，長(zhǎng)度為n的數(shù)據(jù)表的快速排序需要經(jīng)過n趟劃分，使得整個(gè)排序算法的時(shí)間復(fù)雜度為O(n 2 )。
為改善最壞情況下的時(shí)間性能，可采用其他方法選取中間數(shù)。通常采用“三者值取中”方法，即比較H-r[low].key、H-r[high].key與H-r[(low+high)/2].key，取三者中關(guān)鍵字為中值的元素為中間數(shù)。
可以證明，快速排序的平均時(shí)間復(fù)雜度也是O(nlog 2 n)。因此，該排序方法被認(rèn)為是目前最好的一種內(nèi)部排序方法
先從數(shù)據(jù)序列中選一個(gè)元素,并將序列中所有比該元素小的元素都放到它的右邊或左邊,再對(duì)左右兩邊分別用同樣的方法處之直到每一個(gè)待處理的序列的長(zhǎng)度為1, 處理結(jié)束。
在當(dāng)前無序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹?/p>
快速排序的基本思想是基于分治策略的。對(duì)于輸入的子序列L[p..r]，如果規(guī)模足夠小則直接進(jìn)行排序（比如用前述的冒泡、選擇、插入排序均可），否則分三步處理：
分解(Divide)：將待排序列L[p..r]劃分為兩個(gè)非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。具體可通過這樣的途徑實(shí)現(xiàn)：在序列L[p..r]中選擇數(shù)據(jù)元素L[q]，經(jīng)比較和移動(dòng)后，L[q]將處于L[p..r]中間的適當(dāng)位置，使得數(shù)據(jù)元素L[q]的值小于L[q+1..r]中任一元素的值。
遞歸求解(Conquer)：通過遞歸調(diào)用快速排序算法，分別對(duì)L[p..q]和L[q+1..r]進(jìn)行排序。
合并(Merge)：由于對(duì)分解出的兩個(gè)子序列的排序是就地進(jìn)行的，所以在L[p..q]和L[q+1..r]都排好序后不需要執(zhí)行任何計(jì)算L[p..r]就已排好序，即自然合并。
這個(gè)解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經(jīng)典應(yīng)用實(shí)例之一。
終于編寫出來了，我寫了兩種，你看看：下面是代碼：
/*非遞歸算法1
遞歸算法的開銷很大，所以在下編了一個(gè)非遞歸的，算法描述如下：
A non-recursive version of quick sort using stack:
There are 2 stacks, namely one which stores the start of
a subarray and the other which stores the end of the
subarray.
STEP 1: while the subarray contains more than one element
,i.e. from Do {
SUBSTEP 1. pivot=Partion(subarray);
SUBSTEP 2. keep track of the right half of the current
subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo
SUBSTEP 3. go on to deal with the left half of
the current subarray i.e. to=pivot-1
}
STEP 2: if(neither of the stacks is empty)
Get a new subarray to deal with from the stacks.
i.e. start=pop(stackFrom); to=pop(stackTo);
STEP 3: both stacks are empty, and array has
been sorted. The program ends.
*/*/
void UnrecQuicksort(int q[],int low,int high)
{stack s1;br/stacks2;br/ s1.push(low);br/ s2.push(high);br/ int tl,th,p;br/ while(!s1.empty() !s2.empty())br/ {tl=s1.top();th=s2.top();br/ s1.pop();s2.pop();br/ if(tl=th) continue;br/ p=partition(q,tl,th);br/ s1.push(tl);s1.push(p+1);br/ s2.push(p-1);s2.push(th);br/ }
}
/*非遞歸算法2
要把遞歸算法改寫成非遞歸算法，可引進(jìn)一個(gè)棧，這個(gè)棧的大小取決于遞歸調(diào)用的深度，最
多不會(huì)超過n，如果每次都選較大的部分進(jìn)棧，處理較短的部分，遞歸深度最多不超過log2n
，也就是說快速排序需要的附加存儲(chǔ)開銷為O（log2n）。
*/
void UnrecQuicksort2(int q[],int low,int high)
{int *a;br/ int top=0,i,j,p;br/ a=new int[high-low+1];br/ if(a==NULL) return;br/ a[top++]=low;br/ a[top++]=high;br/ while(top0)br/ {i=a[--top];br/ j=a[--top];br/ while(j {p=partition(q,j,i);br/ if(p-j {//先分割前部,后部進(jìn)棧br/a[top++]=p+1;br/ a[top++]=i;br/ i=p-1;br/ }
else
{//先分割后部,前部進(jìn)棧
a[top++]=j;
a[top++]=p-1;
j=p+1;
}
}
}
}
/*打印輸出*/
void display(int p[],int len)
{for(int i=0;i cout}
/*測(cè)試*/
int _tmain(int argc, _TCHAR* argv[])
{int a[]={49,65,97,12,23,41,56,14};
quicksort(a,0,7);
//UnrecQuicksort(a,0,7);
//UnrecQuicksort2(a,0,7);
display(a,8);
return 0;
}
快速排序，外文名Quicksort，計(jì)算機(jī)科學(xué)，適用領(lǐng)域Pascal，c++等語(yǔ)言，是對(duì)冒泡排序算法的一種改進(jìn)。
原理：
設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個(gè)過程稱為一趟快速排序。
性能分析：
快速排序的一次劃分算法從兩頭交替搜索，直到low和hight重合，因此其時(shí)間復(fù)雜度是O(n)；而整個(gè)快速排序算法的時(shí)間復(fù)雜度與劃分的趟數(shù)有關(guān)。
理想的情況是，每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列幾乎等分，經(jīng)過log2n趟劃分，便可得到長(zhǎng)度為1的子表。這樣，整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。
以上內(nèi)容參考：百度百科——快排算法
快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。[1]
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。[1]
中文名
快速排序算法
外文名
quick sort
別名
快速排序
提出者
C. A. R. Hoare
提出時(shí)間
1960年
快速
導(dǎo)航
排序步驟
程序調(diào)用舉例
示例代碼
性能分析
排序流程
快速排序算法通過多次比較和交換來實(shí)現(xiàn)排序，其排序流程如下：[2]
(1)首先設(shè)定一個(gè)分界值，通過該分界值將數(shù)組分成左右兩部分。[2]
(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。[2]
(3)然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。[2]
(4)重復(fù)上述過程，可以看出，這是一個(gè)遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。[2]
排序步驟
原理
設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選
快排圖
用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個(gè)過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。[1]
一趟快速排序的算法是：[1]
1）設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=N-1；[1]
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；[1]
3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]的值交換；[1]
4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]的值交換；[1]
5）重復(fù)第3、4步，直到i==j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。[1]
排序演示
假設(shè)一開始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此時(shí)，ref=5，i=1，j=11，從后往前找，第一個(gè)比5小的數(shù)是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。
此時(shí)i=1，j=8，從前往后找，第一個(gè)比5大的數(shù)是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。
此時(shí)，i=3，j=8，從第8位往前找，第一個(gè)比5小的數(shù)是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。
Go語(yǔ)言標(biāo)準(zhǔn)庫(kù)中提供了sort包對(duì)整型，浮點(diǎn)型，字符串型切片進(jìn)行排序，檢查一個(gè)切片是否排好序，使用二分法搜索函數(shù)在一個(gè)有序切片中搜索一個(gè)元素等功能。
關(guān)于sort包內(nèi)的函數(shù)說明與使用，請(qǐng)查看
在這里簡(jiǎn)單講幾個(gè)sort包中常用的函數(shù)
在Go語(yǔ)言中，對(duì)字符串的排序都是按照字節(jié)排序，也就是說在對(duì)字符串排序時(shí)是區(qū)分大小寫的。
二分搜索算法
Go語(yǔ)言中提供了一個(gè)使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比較㏒?n個(gè)元素，其中n為切片中元素的總數(shù)。
sort.Search(size,fn)函數(shù)接受兩個(gè)參數(shù)：所處理的切片的長(zhǎng)度和一個(gè)將目標(biāo)元素與有序切片的元素相比較的函數(shù)，該函數(shù)是一個(gè)閉包，如果該有序切片是升序排列，那么在判斷時(shí)使用 有序切片的元素 = 目標(biāo)元素。該函數(shù)返回一個(gè)int值，表示與目標(biāo)元素相同的切片元素的索引。
在切片中查找出某個(gè)與目標(biāo)字符串相同的元素索引
重慶分公司
重慶分公司
