JavaScript實(shí)現(xiàn)
網(wǎng)上大部分都是基于這種寫(xiě)法：
//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));
}
但是這種個(gè)寫(xiě)法很明顯是需要0(n)的額外空間的圆存，那如果我們基于原地分區(qū)該怎樣實(shí)現(xiàn)呢汉柒？
partition的不同版本
記得在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們是下面這樣實(shí)現(xiàn)的，通過(guò)兩個(gè)指針low,high從兩端往中間逼近沈跨。
//C++
int partition(int arr[], int low, int high){
//直接選取第一個(gè)元素為樞軸
int pivot = arr[low];
while(low < high) {
//注意下面的while內(nèi)部也要進(jìn)行越界判斷！
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);
}
}
因?yàn)閜artition函數(shù)是快排的核心仿耽，所以partition的優(yōu)化方法有很多岩榆，可以分為兩大類(lèi)，單向掃描版本和雙向掃描版本恭金，上面就是雙向掃描的例子操禀，方法還是很好理解的∥颠叮《算法導(dǎo)論》那本書(shū)上還提出了另一種基于單向掃描的partition方法床蜘，如下：
int partition(int arr[], int low, int high){
x = arr[high]; //這里直接選取最后一個(gè)元素為比較元素，后面還可以根據(jù)random來(lái)改進(jìn)
int i = low - 1; //這個(gè)i為慢速移動(dòng)下標(biāo)蔑水，必須為比最小的下標(biāo)p小1邢锯，否則兩個(gè)元素的序列（比如2，1）就無(wú)法交換
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);
}
}
算法示意圖如下：
單向掃描優(yōu)化版本
可以?xún)?yōu)化的地方：
- <=x 改為<x搀别，減少交換次數(shù)
- i的初始值直接設(shè)為low
- i = j時(shí)的交換是多余的可以?xún)?yōu)化掉
//cpp優(yōu)化版本
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;
}
隨機(jī)化版本
之前的方法都是基于一個(gè)前提：所有的排列都是等概率的丹擎，但是實(shí)際工程中并不會(huì)總是成立歇父。有時(shí)候我們可以通過(guò)在算法中引入隨機(jī)性蒂培，從而使得算法對(duì)所有的輸入都能獲得較好的期望，比如針對(duì)一個(gè)幾乎有序的輸入序列進(jìn)行排序的問(wèn)題榜苫。很多人都選擇隨機(jī)化版本作為大數(shù)據(jù)輸入情況下的快排护戳。
思路如下:
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)
}
}
其實(shí)就是多了最開(kāi)始的樞軸隨機(jī)化一個(gè)數(shù)這步，然后再與最后的元素交換垂睬，后面都一樣一樣滴媳荒。
單向掃描版本的JavaScript實(shí)現(xiàn)
//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也可以?xún)?yōu)化
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;
}
