C語言實現(xiàn)QuickSort

// ----- 快速排序 -----

int Partition(SqList &L, int low, int high)

{ // 交換順序表L中子序列L.r[low..high]的記錄，使樞軸記錄到位，并返回其所在位置，此時，在它之前（后）的記錄均不大（?。┯谒?/p>

? ? KeyType pivotkey;

? ? L.r[0] = L.r[low]; ? ? ? // 用子表的第一個記錄作為樞軸記錄

? ? pivotkey = L.r[low].key; // 樞軸記錄關(guān)鍵字

? ? while (low < high)

? ? { // 從表的兩端交替地向中間掃描

? ? ? ? while (low < high && L.r[high].key >= pivotkey)

? ? ? ? {

? ? ? ? ? ? --high;

? ? ? ? }

? ? ? ? L.r[low] = L.r[high]; // 將比樞軸記錄小的記錄移到低端

? ? ? ? while (low < high && L.r[low].key <= pivotkey)

? ? ? ? {

? ? ? ? ? ? ++low;

? ? ? ? }

? ? ? ? L.r[high] = L.r[low]; // 將比樞軸記錄大的記錄移到高端

? ? }

? ? L.r[low] = L.r[0]; // 樞軸記錄到位

? ? return low; ? ? ? ?// 返回樞軸位置

}

void QSort(SqList &L, int low, int high)

{ // 對順序表L中的子序列L.r[low..high]進(jìn)行快速排序

? ? int pivotloc;

? ? if (low < high)

? ? { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 待排序列長度大于1

? ? ? ? pivotloc = Partition(L, low, high); // 將L.r[low..high]一分為二

? ? ? ? QSort(L, low, pivotloc - 1); ? ? ? ?// 對低子表遞歸排序，pivotloc是樞軸位置

? ? ? ? QSort(L, pivotloc + 1, high); ? ? ? // 對高子表遞歸排序

? ? }

}

void QuickSort(SqList &L)

{ // 對順序表L進(jìn)行快速排序

? ? QSort(L, 1, L.length);

}