hanyeah

与归并排序一样，快速排序也使用了分治思想。快速排序最坏情况时间复杂度是O(n^2)，平均时间复杂度是O(nlgn)，而且O(nlgn)中隐含的常数因子很小，快速排序还是原址排序。

实现代码如下：

// var a = [2, 8, 7, 1, 3, 5, 6, 4];
var a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
a.sort(function(){return Math.random()>0.5});
console.log(a.join("\t"));
quikSort(a, 0, a.length);
console.log(a.join("\t"));

function quikSort(a, p, r){
	if(p < r - 1){
		var q = partition(a, p, r);
		quikSort(a, p, q);
		quikSort(a, q + 1, r);
	}
}

function partition(a, p ,r){
	var x = a[r - 1];
	var i = p - 1;
	for(var j = p; j < r - 1; j++){
		if(a[j] <= x){
			i = i + 1;
			exchange(a, i, j);
		}
	}
	exchange(a, i + 1, r - 1);
	return i + 1;
}

function exchange(a,i,largest){
	var temp = a[i];
	a[i] = a[largest];
	a[largest] = temp;
}

随机化快速排序：

// var a = [2, 8, 7, 1, 3, 5, 6, 4];
var a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
a.sort(function(){return Math.random()>0.5});
console.log(a.join("\t"));
quikSort(a, 0, a.length);
console.log(a.join("\t"));

function quikSort(a, p, r){
	if(p < r - 1){
		var q = randomPartition(a, p, r);// 快速排序的随机化版本
		quikSort(a, p, q);
		quikSort(a, q + 1, r);
	}
}

function randomPartition(a, p ,r){
	var i = random(p, r);
	exchange(a, r, i);
	return partition(a, p, r);
}

function random(A, B){
	return A + Math.floor((B - A) * Math.random());
}

function partition(a, p ,r){
	var x = a[r - 1];
	var i = p - 1;
	for(var j = p; j < r - 1; j++){
		if(a[j] <= x){
			i = i + 1;
			exchange(a, i, j);
		}
	}
	exchange(a, i + 1, r - 1);
	return i + 1;
}

function exchange(a,i,largest){
	var temp = a[i];
	a[i] = a[largest];
	a[largest] = temp;
}