C语言快速排序算法详解与实现

#include <stdio.h> #define MAXL 10

typedef int KeyType; typedef int InfoType;

typedef struct { KeyType key; //KeyType为关键字的数据类型 InfoType otherdata; // InfoType为其他数据类型 } RecordType ;

void PrintList(RecordType r[], int n) //打印顺序表元素 { for (int i = 0; i < n; i++) { printf("%d ", r[i].key); } printf("\n"); }

int QKPass(RecordType r[], int low, int high) //一趟快速排序算法的实现

{ RecordType tmp; tmp = r[low]; /* 选择首记录为基准记录 / while (low < high) /待排序区域长度大于1继续执行/ { /先从high向前扫描找小于tmp支点关键字的记录 / while(low < high && r[high].key >= tmp.key) high--; if (low < high)/找到小于tmp.key记录则放置到低半区/ {
r[low] = r[high]; /high指向的位置空了/ low++; }
while (low < high && r[low].key < tmp.key) / 其次从low向后扫描找大于tmp.key的记录 / low++; if (low < high) / 找到大于tmp.key的记录放置到高半区/ { r[high] = r[low]; high--; }
} r[low] = tmp; / 将支点保存到low=high的位置 / return low; / 返回支点的位置 */ }

void QKSort(RecordType r[], int low, int high) //快速排序 { int pos; if (low < high) { pos = QKPass(r, low, high); QKSort(r, low, pos - 1); QKSort(r, pos + 1, high); } }

int main() { RecordType arr[MAXL] = {{4, 0}, {3, 0}, {6, 0}, {1, 0}, {9, 0}, {7, 0}, {5, 0}, {8, 0}, {2, 0}, {0, 0}}; int delta[3] = {5, 3, 1}; printf("快速排序前为: "); PrintList(arr, MAXL); QKSort(arr, 0, MAXL - 1); printf("快速排序后为: "); PrintList(arr, MAXL); return 0; }

输出结果为：

快速排序前为: 4 3 6 1 9 7 5 8 2 0 快速排序后为: 0 1 2 3 4 5 6 7 8 9

快速排序的具体过程为：

第一趟：

基准元素为4，low=0，high=9

从high向前扫描找小于4的元素，找到2，将其放到低半区，此时high=8

从low向后扫描找大于4的元素，找到9，将其放到高半区，此时low=1

从high向前扫描找小于4的元素，找到3，将其放到低半区，此时high=7

从low向后扫描找大于4的元素，找到6，将其放到高半区，此时low=2

从high向前扫描找小于4的元素，没有找到，结束第一趟排序，将基准元素4放到位置low=3，此时数组变为{2, 3, 0, 1, 4, 7, 5, 8, 6, 9}

第二趟：

基准元素为2，low=0，high=2

从high向前扫描找小于2的元素，没有找到

从low向后扫描找大于2的元素，找到3，将其放到高半区，此时low=1

从high向前扫描找小于2的元素，没有找到，结束第二趟排序，将基准元素2放到位置low=0，此时数组变为{0, 2, 3, 1, 4, 7, 5, 8, 6, 9}

第三趟：

基准元素为3，low=1，high=2

从high向前扫描找小于3的元素，没有找到

从low向后扫描找大于3的元素，没有找到，结束第三趟排序，将基准元素3放到位置low=2，此时数组变为{0, 2, 3, 1, 4, 7, 5, 8, 6, 9}

第四趟：

基准元素为1，low=3，high=2，结束排序

第五趟：

基准元素为4，low=4，high=9

从high向前扫描找小于4的元素，没有找到，结束排序

第六趟：

基准元素为7，low=5，high=9

从high向前扫描找小于7的元素，找到6，将其放到低半区，此时high=8

从low向后扫描找大于7的元素，没有找到，结束第六趟排序，将基准元素7放到位置low=6，此时数组变为{0, 2, 3, 1, 4, 6, 5, 7, 8, 9}

第七趟：

基准元素为5，low=7，high=9

从high向前扫描找小于5的元素，没有找到

从low向后扫描找大于5的元素，没有找到，结束第七趟排序，将基准元素5放到位置low=7，此时数组变为{0, 2, 3, 1, 4, 6, 5, 7, 8, 9}

第八趟：

基准元素为8，low=8，high=9，结束排序

第九趟：

基准元素为6，low=5，high=7

从high向前扫描找小于6的元素，没有找到

从low向后扫描找大于6的元素，没有找到，结束第九趟排序，将基准元素6放到位置low=5，此时数组变为{0, 2, 3, 1, 4, 5, 6, 7, 8, 9}

第十趟：

基准元素为9，low=8，high=9，结束排序

最终数组排好序为{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。