2009-04-25

[C語言] 快速排序法(quick sort)


#include<stdio.h>

/** quick_sort [快速排序法]
* @param {array} array
* @param {int} low
* @param {int} high
*/
int quick_sort(int *array,int low,int high) {
int pivot_point,pivot_item,i,j,temp;
// 指標交界結束排序
if(high<=low){return 1;}

// 紀錄樞紐值
pivot_item = array[low];
j=low;

// 尋找比樞紐小的數
for(i=low+1; i<=high; i++) {
// 跳過等於或大於的數
if(array[i]>=pivot_item){continue;}

j++;
// 交換 array[i] , array[j]
temp = array[i];
array[i] = array[j];
array[j] = temp;
}

// 將樞紐位址移到中間
pivot_point=j;
// 交換 array[low] , array[pivot_point]
temp = array[low];
array[low] = array[pivot_point];
array[pivot_point] = temp;

// 遞迴處理左側區段
quick_sort(array,low,pivot_point-1);
// 遞迴處理右側區段
quick_sort(array,pivot_point+1,high);

return 1;
}


/*主程式*/
int main(){
int a[]={12,42,54,3,5,32,61,24,31};

quick_sort(a,0,8);

int i;
for(i=0; i<=8; i++) {
printf("%d\n",a[i]);
}

_getch();
return 0;
}

3 回應:

匿名 提到...

7 2 3 9 5 8 10 6 4 1 會不會排不出來

[7] 2 3 9* 5 8 10 6 4 1*

[7] 2 3 1 5 8* 10 6 4* 9

[7] 2 3 1 5 4 10* 6* 8 9

6 2 3 1 5 4 [7] 10 8 9

以下分成

[6] 2 3 1 5 4 及 [10] 8 9

請問接下來怎麼排?

匿名 提到...

若改用link list要怎麼寫?

胡忠晞 Jax 提到...

老師出問題就是需要你們去思考
最簡單的就是將 link list 轉成 array
至於要直接處理 link list 就真的要想一想

用 point 去記錄三個關鍵點[起始點,結束點,游標]
使用相同的演算法還是可以 run