快速排序，顾名思义，在所有排序方法中它是最快的，先说一个它的时间复杂度是O(nlog2N), 虽然也有其他排序方法的时间复杂度也是这个（例如堆排序），但是快排的常数项是最小的。
先来看一下代码 =
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;
void quickSort(int[], int, int);
int main(int argc, char *argv[])
{
int R[] = {49, 38, 65, 97, 76, 13, 27, 49};
cout << "sort before = " << endl;
dbg(R);
int len = sizeof(R) / sizeof(R[0]);
quickSort(R, 0, len - 1);
cout << "sort after = " << endl;
dbg(R);
return 0;
}
void quickSort(int R[], int low, int high)
{
int temp;
int i = low, j = high;
if (low < high)
{
temp = R[low]; // 枢轴
while (i < j)
{
while (j > i && R[j] >= temp) j--; // 从右往左扫描
if (i < j)
{
R[i] = R[j];
i++;
}
while (i < j && R[i] < temp) i++; // 从左往右扫描
if (i < j)
{
R[j] = R[i];
j--;
}
}
R[i] = temp;
quickSort(R, low, i - 1);
quickSort(R, i + 1, high);
}
}
运行结果如下(文章中显示变量使用的是[dbg][1])
说一个具体的思路 =
- 首先，找到一个数字作为比较的
枢轴，这里使用的是数组最左端的数字，使用temp暂存，现在最左端相当于挖了一个坑（因为当前数字已经赋值给temp了). - 从右往左扫描数组，找到比枢轴
小的数字，将这个数字赋值给枢轴所在位置(填左边的坑, 同时在右边挖了一个坑) - 从左往右扫描数组，找到比枢轴
大的数字，将这个数字赋值给右边挖的坑。
这个排序方法使用的分治的思想，英文叫做divide and conquer， 分割之后再去克服每一项。递归也是属于这一种。就是将一个大问题分解成相似的小问题，然后解决了其中的一个小问题后，使用类似的方法就解决了所有的问题。