快速排序算法的思想和幾種實現(xiàn)方式

昵稱46399781 2018-06-05

展開全文

快速排序算法是基于分治策略的另一個排序算法。

該方法的基本思想是：

1．先從數(shù)列中取出一個數(shù)作為基準數(shù)，記為x。

2．分區(qū)過程，將不小于x的數(shù)全放到它的右邊，不大于x的數(shù)全放到它的左邊。（這樣key的位置左邊的沒有大于key的，右邊的沒有小于key的，只需對左右區(qū)間排序即可）

3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)

快排目前有兩類實現(xiàn)算法，第一種是標準算法，第二種是兩頭交換法?？偟乃枷肱c上面三步一樣，在細節(jié)處理上有一些差異。

標準算法思想及實現(xiàn)

標準算算法采用的思想是挖坑填坑的思想：

以一個數(shù)組作為示例，取區(qū)間第一個數(shù)為基準數(shù)。

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

初始時，i = 0; j = 9; X = a[i] = 72

由于已經(jīng)將a[0]中的數(shù)保存到X中，可以理解成在數(shù)組a[0]上挖了個坑，可以將其它數(shù)據(jù)填充到這來。

從j開始向前找一個比X小或等于X的數(shù)。當j=8，符合條件，將a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++; 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個坑。這次從i開始向后找一個大于X的數(shù)，當i=3，符合條件，將a[3]挖出再填到上一個坑中a[8]=a[3]; j--;

數(shù)組變?yōu)椋?/p>

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

i = 3; j = 7; X=72

再重復(fù)上面的步驟，先從后向前找，再從前向后找。

從j開始向前找，當j=5，符合條件，將a[5]挖出填到上一個坑中，a[3] = a[5]; i++;

從i開始向后找，當i=5時，由于i==j退出。

此時，i = j = 5，而a[5]剛好又是上次挖的坑，因此將X填入a[5]。

數(shù)組變?yōu)椋?/p>

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對a[0…4]和a[6…9]這二個子區(qū)間重復(fù)上述步驟就可以了。

對挖坑填數(shù)進行總結(jié)

1．i =L; j = R; 將基準數(shù)挖出形成第一個坑a[i]。

2．j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中。

3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。

4．再重復(fù)執(zhí)行2，3二步，直到i==j，將基準數(shù)填入a[i]中。

代碼實現(xiàn)如下：

[cpp]view plain copy

print?

#include <iostream>
using namespace std;
void quick_sort(int s[],int l, int r){
int i = l,j = r, x = s[l];
while(i < j){
while(i < j && s[j] > x) j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) i++;
if(i < j)
s[j--] = s[i];
}
//此時i==j,下面s[i]或者s[j]都可以，j-1,j+1也ok
s[j] = x;
if (l<i) quick_sort(s,l, i - 1);
if (r>i) quick_sort(s,i + 1, r);
};
int main()
{
int test[] = {34,5,4,5,3,2,6,90,5};
quick_sort(test,0,8);
for(auto c : test){
cout<<c<<" ";
}
cout<<endl;
return 0;
}

兩頭交換法思想及實現(xiàn)

兩頭交換法與標準算法思想的差異是，先從左邊開始找到大于基準值的那個數(shù)，再從右邊找到小于基準值的那個數(shù)，將兩個數(shù)交換(這樣比基準值小的都在左邊，比基準值大的都在右邊)。直到數(shù)列分成大于基準值和小于基準值的兩個區(qū)間，以這兩個區(qū)間進行同樣的排序操作。

代碼實現(xiàn)如下：

[cpp]view plain copy

print?

#include <iostream>
using namespace std;
void quickSort(int a[],int beg,int end){
//partition非遞歸實現(xiàn)，官方版
if(beg >= end) return;
int i = beg, j = end, x = a[(i + j)>>1],tmp =0;//這里基準值選了中間的值
while(i <= j){//取等號，確保分成兩個不相交區(qū)間
while( a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j ){
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
quickSort(a,beg,j);
quickSort(a,i,end);
};
int main()
{
int test[] = {34,6,4,5,1,2,6,90,7};
quickSort(test,0,8);
for(auto c : test){
cout<<c<<" ";
}
cout<<endl;
return 0;}

上面的算法是兩頭交換法官方的版本，邊界情況較少，比較健壯。

兩頭交換法還有另一個實現(xiàn)方式，這種實現(xiàn)方式，基準值只能選區(qū)間第一個值或最后一個值?；鶞手挡粎⑴c交換，將除基準值之外的所有值按照與基準值的大小關(guān)系分成兩部分，然后將區(qū)間分界點的值填到基準值的坑里，將基準值放在區(qū)間分界點。對于基準值左右的區(qū)間進行再次排序。

代碼實現(xiàn)：

[cpp]view plain copy

print?

[cpp]view plain copy

print?

#include <iostream>
using namespace std;
//兩點交換法，固定軸點的實現(xiàn)，基準點不參與排序
//基準點選第一個值，中間交換點選j,
//基準點選第一個值，中間交換點選i
//不然，會出現(xiàn)死循環(huán)
//將除第一個值之外的其他值交換使得小于基準值的在前，大于的在后，然后最中間點較小的j位置的值的與第一個值交換，交換后前面的小于基準值，后面的大于基準值
int partition(int b[],int first,int last){
int x = b[first],temp = 0;
int i = first,j = last + 1;//因為后面判斷是--j
while(true){
while(b[++i] < x && i <= last);
while(b[--j] > x);
if(i >= j){
break;
}
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
b[first] = b[j];
b[j] = x;
return j;
};
void quickSort(int a[],int beg,int end){
if(beg < end){
int q = partition(a,beg,end);
quickSort(a,beg,q-1);
quickSort(a,q+1,end);
}
};
int main()
{
int test[] = {34,5,4,5,3,2,6,90,5};
quickSort(test,0,8);
for(auto c : test){
cout<<c<<" ";
}
cout<<endl;
return 0;
}

[cpp]view plain copy

print?

注意：兩頭交換法，最后填坑點的選擇與基準值的選擇有關(guān)系，當基準值在區(qū)間前半部分則填坑點選值較小的j,反之則選i.

效率分析

快排的時間復(fù)雜度理論上是Nlog(N). i,j點的值與基準值比較時取“嚴格大于/小于”還是”大于等于/小于等于”會影響復(fù)法最壞復(fù)雜度。一般的想法是用大于等于/小于等于，忽略與樞紐元相同的元素，這樣可以減少不必要的交換，因為這些元素無論放在哪一邊都是一樣的。但是如果遇到所有元素都一樣的情況，這種方法每次都會產(chǎn)生最壞的劃分，也就是一邊1個元素，令一邊n－1個元素，使得時間復(fù)雜度變成。而如果用嚴格大于/小于，雖然兩邊指針每此只挪動1位，但是它們會在正中間相遇，產(chǎn)生一個最好的劃分，時間復(fù)雜度為。。但是當取嚴格大于/小于的時候，交換的次數(shù)也會相應(yīng)的增加。實際的交換次數(shù)應(yīng)該是相同的。