排序是學(xué)習(xí)編程這個(gè)過程中一定會(huì)學(xué)習(xí)的算法，也是程序員的一項(xiàng)基本技能。今天就給大家講一下編程里面常用的快速排序西乖。
- 優(yōu)點(diǎn)
快速排序是一種非澈疲快的排序算法，基于“二分”思想获雕，時(shí)間復(fù)雜度是O(Nlog2N)薄腻。由于算法需要使用遞歸，空間復(fù)雜度最好情況為O(log2N), 最差為log(N)
且不會(huì)浪費(fèi)儲(chǔ)存空間 - 實(shí)現(xiàn)
1.找樞軸
假設(shè)我們現(xiàn)在要對(duì)3, 5, 2, 1, 8, 9, 10 ,7, 4,6 這10個(gè)數(shù)進(jìn)行排序届案。首先我們需要在數(shù)列里面找一個(gè)基準(zhǔn)數(shù)庵楷，又稱樞軸。我們一般取第一個(gè)為樞軸楣颠。
3, 5, 2, 1, 8, 9, 10 ,7, 4,6
2.交換
我們要讓數(shù)列左邊的數(shù)都小于樞軸尽纽，右邊的數(shù)都大于樞軸。我們一般取第一個(gè)數(shù)為樞軸童漩，類似與下面這個(gè)樣子弄贿。
2 1 3 5 8 9 10 7 4 6
如何實(shí)現(xiàn)呢？
有點(diǎn)類似與冒泡排序的交換矫膨，大家可以思考一下再往下看
我們可以設(shè)置兩個(gè)哨兵i, j差凹， 讓i,j 分別從數(shù)組的兩邊來(lái)進(jìn)行搜索。j哨兵先從數(shù)組右邊找一個(gè)比樞軸小的數(shù)(j--)侧馅，i數(shù)組再?gòu)臄?shù)組左側(cè)找一個(gè)比樞軸大的數(shù)(i++)危尿，如果此時(shí)i < j，則將i, j哨兵所在的兩個(gè)數(shù)交換馁痴。
如下圖谊娇，樞軸為6，j哨兵找到第一個(gè)小于6的數(shù)5罗晕，然后停止邮绿。接著渠旁，i哨兵開始行動(dòng)了，往右找到第一個(gè)大于6的數(shù)7船逮，此時(shí)顾腊，i < j, 交換兩個(gè)哨兵的值，即7 與 5位置交換挖胃。
接著杂靶，兩個(gè)哨兵重復(fù)上面的步驟，j找到小于6的數(shù)4酱鸭，i找到大于6的數(shù)9吗垮，而且 i < 9,則將4與9交換。
重復(fù)上面步驟凹髓，j找到了小于6的數(shù)3烁登，i往右探測(cè)，發(fā)現(xiàn)自己與j相遇了蔚舀，然后就可以停止探測(cè)饵沧，將樞軸與i與j相遇的位置交換。
這時(shí)我們發(fā)現(xiàn)我們已經(jīng)到底目的了赌躺，樞軸左邊的數(shù)都小于樞軸焦履，右邊的數(shù)大于樞軸探颈。
不過撮胧，樞軸左邊與右邊的數(shù)列還不是有序的僻肖，我們只需要對(duì)樞軸左邊與右邊的數(shù)列重復(fù)上面的步驟就行了，
3 1 2 5 4 //重復(fù)上面步驟缅叠，找3為基準(zhǔn)數(shù)
9 7 10 8 //重復(fù)上面步驟悄泥，找9為基準(zhǔn)數(shù)
不斷重復(fù)直到不能拆分為子序列為止
-
處理過程如下
過程 算法描述
void Qsort(int arr[], int left, int right)
{
if(left >= right)
return;
int i, j, temp, t;
i = left;
j = right;
temp = arr[i]; /*將基準(zhǔn)數(shù)放在temp里面*/
while(i < j)
{
while(arr[j] >= temp && i < j) /*不能沒有等于*/
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) /*交換i,j 需要判斷是否i < j;*/
{
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i]; /*基準(zhǔn)數(shù)交換*/
arr[i] = temp;
Qsort(arr, left, i-1); /*處理樞軸左邊，遞歸*/
Qsort(arr, i+1, right); /*處理樞軸右邊肤粱，遞歸*/
}
- 缺點(diǎn)码泞，快速排序雖然香，但依然有缺點(diǎn)狼犯。
- 排序過程需要定位數(shù)列的左邊與右邊余寥，適合順序儲(chǔ)存結(jié)構(gòu)，不適合鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)
- 排序過程無(wú)法保證相同元素的順序悯森，所有是不穩(wěn)定的
以上圖片來(lái)自與網(wǎng)絡(luò)宋舷。
