/* 快速排序的算法源程序*/

#include<stdio.h>

#define MAXNUM 100
#define TRUE 1
#define FALSE 0
typedef int KeyType;
typedef int DataType;

typedef struct {
    KeyType key;         /* 排序碼字段 */
    /*DataType info;        記錄的其它字段 */
} RecordNode;

typedef struct {
    int n;               /* n為文件中的記錄個數，n<MAXNUM */
    RecordNode record[MAXNUM];
} SortObject;

void quickSort(SortObject * pvector, int l, int r) {
    int i, j;
    RecordNode temp, *data = pvector->record;
    
    if (l >= r) return;   /* 只有一個記錄或無記錄，則無須排序 */

    i = l;  j = r;  temp = data[i];

    while (i != j) {        /* 尋找Rl的最終位置 */
        while( data[j].key >= temp.key && j > i )
            j--;         /* 從右向左掃描，查找第1個排序碼小于temp.key的記錄 */
        if (i < j) data[i++] = data[j];   

        while( data[i].key <= temp.key && j > i )
            i++;         /* 從左向右掃描，查找第1個排序碼大于temp.key的記錄 */
        if (i < j) data[j--] = data[i];
    }

    data[i] = temp;                 /* 找到Rl的最終位置 */
    quickSort(pvector, l, i-1);                 /* 遞歸處理左區間 */
    quickSort(pvector, i+1, r);            /* 遞歸處理右區間 */
}

SortObject vector = {8, 49,38,65,97,76,13,27,49};

int main(){
    int i;
    quickSort(&vector, 0, 7);
    for(i = 0; i < 8; i++)
        printf("%d ", vector.record[i]);
    getchar();
    return 0;
}