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

原始碼

1. #include<stdio.h> 
2.  
3. /** quick_sort [快速排序法] 
4. * @param {array} array 
5. * @param {int} low 
6. * @param {int} high 
7. */ 
8. int quick_sort(int *array,int low,int high) { 
9.    int pivot_point,pivot_item,i,j,temp; 
10.    // 指標交界結束排序 
11.    if(high<=low){return 1;} 
12.  
13.    // 紀錄樞紐值 
14.    pivot_item = array[low]; 
15.    j=low; 
16.  
17.    // 尋找比樞紐小的數 
18.    for(i=low+1; i<=high; i++) { 
19.        // 跳過等於或大於的數 
20.        if(array[i]>=pivot_item){continue;} 
21.  
22.        j++; 
23.        // 交換 array[i] , array[j] 
24.        temp = array[i]; 
25.        array[i] = array[j]; 
26.        array[j] = temp; 
27.    } 
28.  
29.    // 將樞紐位址移到中間 
30.    pivot_point=j; 
31.    // 交換 array[low] , array[pivot_point] 
32.    temp = array[low]; 
33.    array[low] = array[pivot_point]; 
34.    array[pivot_point] = temp; 
35.  
36.    // 遞迴處理左側區段 
37.    quick_sort(array,low,pivot_point-1); 
38.    // 遞迴處理右側區段 
39.    quick_sort(array,pivot_point+1,high); 
40.  
41.    return 1; 
42. } 
43.  
44.  
45. /*主程式*/ 
46. int main(){ 
47.    int a[]={12,42,54,3,5,32,61,24,31}; 
48.  
49.    quick_sort(a,0,8); 
50.  
51.    int i; 
52.    for(i=0; i<=8; i++) { 
53.        printf("%d\n",a[i]); 
54.    } 
55.  
56.    _getch(); 
57.    return 0; 
58. } 

#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;
}