快速排序被列为20世纪十大算法之一。 基本思想是：选取一个枢轴，通过一趟排序将待排记录分割成独立的俩部分，其中一部分记录比枢轴小，另外一部分记录比枢轴大；然后再继续对分割好的的字序列进行上述排序。
实现代码
void swap(int *a, int low, int high) { int temp = a[low]; a[low] = a[high]; a[high] = temp; } // 交换a中字表的记录，是枢轴记录到位，并返回其位置 // 此时枢轴之前（后）的记录均不大（小）于它 int Partition(int *a, int low, int high) { int pivotKey = a[low]; // 用字表的第一个记录作枢轴记录 while (low < high) // 从表的俩端交替向中间扫描 { while (low < high && pivotKey <= a[high]) { high--; } swap(a, low, high); // 将比枢轴记录小的记录交换到低端 while (low < high && pivotKey >= a[low]) { low++; } swap(a, low, high); // 将比枢轴记录大的记录交换到高端 } return low; // 返回枢轴的位置 } // 对顺序表a的子序列作快速排序 void QSort(int *a, int low, int high) { int pivot; if (low < high) { pivot = Partition(a, low, high); // 将a一分为二、返回枢轴位置 QSort(a, low, pivot - 1); // 对低字表递归排序 QSort(a, pivot + 1, high); // 对高子表递归排序 } } // 对序列表a进行快速排序 void QuickSort(int *a, int len) { QSort(a, 0, len - 1); }快速排序优化
优化选取枢轴 直接选取表的第一个记录作为枢轴，如果第一个记录正好是整个表的中间数是最理想的，但实际情况是第一个记录往往偏大或偏小，甚至极端情况是最大或最小，此时第一个记录作为枢轴显然是不合适的，故一般采用“三数取中”法——即选取头尾和中间三个数，也可速记选取，取中间值作为枢轴。或“九数取中”法，即选取三组数，算出分别算出中间值，再在这三个中间值中选取中间值作为枢轴。 int mid = low + (high - low) / 2; if (a[low] > a[high]) { swap(a, low, high); } if (a[mid] > a[high]) { swap(a, mid, high); } if (a[low] < a[mid]) { swap(a, low, mid); } int pivotKey = a[low]; // 用字表的第一个记录作枢轴记录 优化小数组时的排序方案 当数组较小时，直接采用直接插入排序，性能更好 对QSort函数进行改进即可。 high - low 大于某个常数，有资料说7合适，也有说50合适，实际情况可自行调整。 #define MAX_LEN_INSERT_SORT 7 void QSort(int *a, int low, int high) { int pivot; if ((high - low) > MAX_LEN_INSERT_SORT) { pivot = Partition(a, low, high); // 将a一分为二、返回枢轴位置 QSort(a, low, pivot - 1); // 对低字表递归排序 QSort(a, pivot + 1, high); // 对高子表递归排序 } else { InsertSort(int *a, int len); } } 优化递归操作 void QSort(int *a, int low, int high) { int pivot; if ((high - low) > MAX_LEN_INSERT_SORT) { while (low < high) { pivot = Partition(a, low, high); // 将a一分为二、返回枢轴位置 QSort(a, low, pivot - 1); // 对低字表递归排序 low = pivot + 1; // 尾递归优化法 } } else { InsertSort(int *a, int len); } }