JavaScript实现
网上大部分都是基于这种写法：
//JavaScript
function quicksort(arr) {
if(arr.length <= 1) {
return arr;
}
//这里直接选取中间元素为枢轴
var pivotIndex = Math.floor(arr.length/2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if(arr[i] < pivot) {
left.push(arr[i]);
}else {
right.push(arr[i]);
}
}
return quicksort(left).concat([pivot], quicksort(right));
}
但是这种个写法很明显是需要0(n)的额外空间的，那如果我们基于原地分区该怎样实现呢？
partition的不同版本
记得在学习数据结构的时候，我们是下面这样实现的，通过两个指针low,high从两端往中间逼近。
//C++
int partition(int arr[], int low, int high){
//直接选取第一个元素为枢轴
int pivot = arr[low];
while(low < high) {
//注意下面的while内部也要进行越界判断！
while(low < high && arr[high] > pivot) {
high--;
}
while(low < high && arr[low] <= pivot) {
low++;
}
arr[low] = pivot;
return low;
}
}
void quicksort(int arr[], int low, int high) {
int loc = 0;
if(low < high) {
loc = partition(arr, low, high);
quicksort(arr, low, loc - 1);
quicksort(arr, loc + 1, high);
}
}
因为partition函数是快排的核心，所以partition的优化方法有很多，可以分为两大类，单向扫描版本和双向扫描版本，上面就是双向扫描的例子，方法还是很好理解的。《算法导论》那本书上还提出了另一种基于单向扫描的partition方法，如下：
int partition(int arr[], int low, int high){
x = arr[high]; //这里直接选取最后一个元素为比较元素，后面还可以根据random来改进
int i = low - 1; //这个i为慢速移动下标，必须为比最小的下标p小1，否则两个元素的序列（比如2，1）就无法交换
int j = low;
for(; j < high; j++) {
if(arr[j] <= x){
swap(&arr[++i], &arr[j]);
}
}
swap(&arr[i+1], &a[j]);
return i + 1;
}
quicksort(int arr[], int low, int high) {
if(low < high) {
int index = partition(arr, low, high);
quicksort(arr, low, index - 1);
quicksort(arr, index + 1, high);
}
}
算法示意图如下：
单向扫描优化版本
可以优化的地方：
- <=x 改为<x，减少交换次数
- i的初始值直接设为low
- i = j时的交换是多余的可以优化掉
//cpp优化版本
int partition (int a[], low, high) {
int x = a[high];
int i = low;
int j = low;
for(; j < high; j++) {
if(a[j] < x) {
if(i != j){
swap(&a[i], &a[j]);
}
i++;
}
}
swap(&a[i], &a[j]);
return i;
}
随机化版本
之前的方法都是基于一个前提：所有的排列都是等概率的，但是实际工程中并不会总是成立。有时候我们可以通过在算法中引入随机性，从而使得算法对所有的输入都能获得较好的期望，比如针对一个几乎有序的输入序列进行排序的问题。很多人都选择随机化版本作为大数据输入情况下的快排。
思路如下:
randomPartition(arr, low, high){
i = random(low, high);
swap(a[i], a[high]);
return partition(arr, low, high);
}
randomQuicksort(arr, low, high) {
if(low < high){
int index = randomPartition(arr, low, high);
randomQuicksort(arr, low, index - 1);
randomQuicksort(arr, index + 1, high)
}
}
其实就是多了最开始的枢轴随机化一个数这步，然后再与最后的元素交换，后面都一样一样滴。
单向扫描版本的JavaScript实现
//js
function quicksort (arr) {
function swap (arr, m, n) {
var tmp = arr[m];
arr[m] = arr[n];
arr[n] = tmp;
}
function partition (arr, low, high) {
var x = arr[high];
var i = low - 1;
for(var j = low; j < high; j++) {
if(arr[j] <= x){
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
function sort (arr, low, high) {
if(low < high) {
var pivotIndex = partition(arr, low, high);
sort(arr, low, pivotIndex - 1);
sort(arr, pivotIndex + 1, high);
}
return arr;
}
return sort(arr, 0, arr.length - 1);
}
同理，其中的partition也可以优化
function partition (arr, low, high) {
var x = arr[high];
var i = low;
for(var j = low; j < high; j++){
if(arr[j] < x){
if(x != j){
swap(arr, i, j);
i++;
}
}
}
swap(arr, i, high);
return i;
}
