快速排序算法分析

#include "stdafx.h" void Qsort(int a[], int low, int high) { if (low >= high) { printf_s("终止条件...\n"); return; } printf_s("调用Qsort开始:\n"); int first = low; int last = high; int key = a[first];/*用字表的第一个记录作为枢轴*/ int m = 1; while (first < last) { while (first < last && a[last] >= key) { --last; } a[first] = a[last];/*将比第一个小的移到低端*/ while (first < last && a[first] <= key) { ++first; } a[last] = a[first]; /*将比第一个大的移到高端*/ for (int i = 0; i < 9; i++) { printf_s("%d\t", a[i]); //cout << a[i] << ""; } printf_s("first:%d\t,last:%d\t", first, last); printf_s("-----第%d次\n",m++); } a[first] = key;/*枢轴记录到位*/ printf_s("本次调用Qsort结果\n："); for (int i = 0; i < 9; i++) { printf_s("%d\t", a[i]); } printf_s("\n调用Qsort结束。\n\n"); Qsort(a, low, first - 1); Qsort(a, first + 1, high); } int main() { int a[] = { 57, 68, 59, 52, 72, 28, 96, 33, 24 }; Qsort(a, 0, sizeof(a)/sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/ printf_s("排序结果：\n"); for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { printf_s("%d\t",a[i]); //cout << a[i] << ""; } printf_s("\n"); return 0; }

上面这段代码摘自百度百科-快速排序。 初始值： 57 68 59 52 72 28 96 33 24 调用结果分析： Key = 57 24 68 59 52 72 28 96 33 68 first,last(1,8) —1

24 33 59 52 72 28 96 59 68 first,last(2,7) —2

24 33 28 52 72 72 96 59 68 first,last(4,5) —3

24 33 28 52 72 72 96 59 68 first,last(4,4) —3 枢轴记录到位后，本次调用Qsort结果： ：24 33 28 52 57 72 96 59 68

经过本次循环，Key左边的值都小于Key，Key右边的值都大于Key 下面分别再对57左右两边的数据调用QSort，递归；

上面的QSort是最终while (first < last)一次循环结束后才对最后这个a[first]赋值为key ：a[first] = key;/枢轴记录到位/ //这句是把最终first所指的72换成初始时给的key值：57。

试着写了下快速排序，如下，与上面的区别主要在：一次QSort调用中每次进行交换操作时，交换操作是否交换的彻底。 写成下面这样，每次交换操作时，都彻底交换值：

void Qsort(int a[], int low, int high) { if (low >= high) { return; } int first = low; int last = high; int numKey = first; int key = a[numKey]; while(first < last) { while (a[last] >= key&&first < last)// 从后往前遍历，找到一个小于key的 { last--; } a[numKey] = a[last]; a[last] = key; numKey = last; //last与numKey所指的值交换后，numKey换成指last值。 while (a[first] <= key&&first < last) //从前往后找，找一个大于key的 { first++; } a[numKey] = a[first]; a[first] = key; numKey = first; //first与numKey所指的值交换后， numKey换成指first值。 } Qsort(a,low,numKey-1); Qsort(a,numKey+1,high); }

numKey用来记录当前key所在的位置。

–欢迎指正和补充！–