快速排序

排序在各種場(chǎng)合經(jīng)常被用到?？焖倥判蚴鞘殖Ｓ玫母咝实乃惴?。

其思想是：先選一個(gè)“標(biāo)尺”，用它把整個(gè)隊(duì)列過(guò)一遍篩子，以保證：其左邊的元素都不大于它，其右邊的元素都不小于它。這樣，排序問(wèn)題就被分割為兩個(gè)子區(qū)間。再分別對(duì)子區(qū)間排序就可以了。

下面的代碼是一種實(shí)現(xiàn)，請(qǐng)分析并填寫(xiě)劃線部分缺少的代碼。

#include <stdio.h>

void swap(int a[], int i, int j)

{

int t = a[i];

a[i] = a[j];

a[j] = t;

}

int partition(int a[], int p, int r)

{

? ? int i = p;

? ? int j = r + 1;

? ? int x = a[p];

? ? while(1){

? ? ? ? while(i<r && a[++i]<x);

? ? ? ? while(a[--j]>x);

? ? ? ? if(i>=j) break;

? ? ? ? swap(a,i,j);

? ? }

______________________;

? ? return j;

}

void quicksort(int a[], int p, int r)

{

? ? if(p<r){

? ? ? ? int q = partition(a,p,r);

? ? ? ? quicksort(a,p,q-1);

? ? ? ? quicksort(a,q+1,r);

? ? }

}

? ??

int main()

{

int i;

int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};

int N = 12;

quicksort(a, 0, N-1);

for(i=0; i<N; i++) printf("%d ", a[i]);

printf("\n");

return 0;

}

注意：只填寫(xiě)缺少的內(nèi)容，不要書(shū)寫(xiě)任何題面已有代碼或說(shuō)明性文字。

還原后的代碼：

所以劃線處應(yīng)該填：

swap(a, p, j);

有人就會(huì)問(wèn)，為什么i不可以，就是填swap(a, p,?i);

這個(gè)很簡(jiǎn)單，因?yàn)槲覀円捎糜|發(fā)點(diǎn)來(lái)作為交換點(diǎn)，--j是最近的代碼，++i是循環(huán)開(kāi)始就執(zhí)行的代碼，自然結(jié)果是因?yàn)閖的操作而導(dǎo)致結(jié)果i >= j發(fā)生，也就是說(shuō)j是主元，所以我們選擇swap(a, p, j);而不是swap(a, p,?i);

如果還沒(méi)弄懂，我就再舉個(gè)例子吧

很顯然，這里最后是用主元left作為交換點(diǎn)

之后我會(huì)持續(xù)更新，如果喜歡我的文章，請(qǐng)記得一鍵三連哦，點(diǎn)贊關(guān)注收藏，你的每一個(gè)贊每一份關(guān)注每一次收藏都將是我前進(jìn)路上的無(wú)限動(dòng)力 ?。?！↖(▔▽▔)↗感謝支持！