思想：快速排序是对冒泡排序的一种改进。它的基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，基准数据排在这两个子序列的中间；
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，一直达到整个数据变成有序序列。
排序过程：对r[s...t]中记录进行一趟快速排序，附设两个指针 i 和 j ，设枢轴记录rp = r[s]，x = rp.key
初始时令i = s，j = t
首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换；
再从i所指位置起向后搜索，找到第一个关键字大于 x 的记录，和rp交换；
重复上述两步，直到i == j为止。
再分别对两个子序列进行快速排序，知道每个子序列只含有一个记录为止。
时间复杂度O(nlogn)。
代码：
#include <iostream>
#include <cstdio>
#include <ctime>
#include <iomanip>
using namespace std;
const int cutoff = 3;
int arr[10000];
void mySwap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
void insertSrot(int *a, int len)
{
for (int i = 1; i < len; i++) {
int tmp = a[i];
int j;
for (j = i; j > 0 && a[j - 1] > tmp; j--) {
a[j] = a[j - 1]; // 元素后移
}
a[j] = tmp; // 元素插入
}
}
// 实现三数中值分割法
int median3(int *a, int low, int high)
{
int center = (low + high) / 2;
if (a[low] > a[center]) {
mySwap(a[low], a[center]);
}
if (a[low] > a[high]) {
mySwap(a[low], a[high]);
}
if (a[center] > a[high]) {
mySwap(a[center], a[high]);
}
mySwap(a[center], a[high - 1]);
return high - 1;
}
void QSort(int *a, int low, int high)
{
if (low + cutoff <= high) {
int pivot = median3(a, low, high);
// Begin partitioning
int i = low, j = high - 1;
while (1) {
while (a[++i] < a[pivot]);
while (a[--j] > a[pivot]);
if (i < j) {
mySwap(a[i], a[j]);
}
else {
break;
}
}
mySwap(a[i], a[high - 1]);
QSort(a, low, i - 1);
QSort(a, i + 1, high);
}
else {
insertSrot(a + low, high - low + 1);
}
}
void quickSort(int *a, int len)
{
QSort(a, 0, len - 1);
}
void printArray(int *a, int len)
{
for (int i = 0; i < len; i++) {
if (i != 0 && i % 10 == 0) {
cout << endl;
}
cout << setw(3) << a[i] << ' ';
}
cout << endl;
}
int main()
{
srand(time(0));
cout << "Please input length of array: ";
int len;
cin >> len;
for (int i = 0; i < len; i++) {
arr[i] = rand() % 100;
}
cout << "Before sorting:\n";
printArray(arr, len);
quickSort(arr, len);
cout << "After sorting:\n";
printArray(arr, len);
return 0;
}
/*
Please input length of array: 20
Before sorting:
71 77 25 92 52 37 85 5 29 81
93 32 77 35 43 37 93 72 14 42
After sorting:
5 14 25 29 32 35 37 37 42 43
52 71 72 77 77 81 85 92 93 93
*/
这里在选择枢轴的时候病并没有直接取第一个元素，因为这种没有经过充分考虑的选择，当输入是预排序的或是反序的，那么这样的枢轴就产生一个劣质的分别。。最终甚至会导致花费的时间是二次的，可是实际上却根本没干什么事，这是相当尴尬的。而且，预排序的输入（或具有一大段预排序数据的输入）是相当常见的。所以使用第一个元素作为枢纽元是绝对糟糕的注意，应该立即放弃这种想法。
这里所使用的是一种比较好的作法，叫做三数中值分割法，算则数组中的中值，当然，直观是很难算出，而且计算中值会明显减慢排序的速度。一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢轴。
使用三数中值分割法消除了预排序输入的坏情形，并且减少了快速排序大约5%的运行时间。