- 相關(guān)推薦
JavaScript快速排序?qū)崿F(xiàn)實(shí)例教程
目前最常見的排序算法大概有七八種，理解和掌握各種排序算法似乎是一個(gè)合格的程序員所必須要掌握的。今天想要和大家分享快速排序算法的Javascript的實(shí)現(xiàn)。
快速排序(Quicksort),又稱為 劃分交換排序(partition-exchange sort)，最早是由東尼·霍爾提出的。
基本思想
快速排序使用 分治法(Divide and conquer)策略(即分而治之，各個(gè)擊破)把一個(gè)序列(list)分為兩個(gè)子序列(sub-lists)。其基本步驟如下:
從數(shù)列中挑出一個(gè)元素，稱為 基準(zhǔn)(pivot)。
重新排序數(shù)列，所有小于基準(zhǔn)的元素，都移到基準(zhǔn)的左邊;所有大于基準(zhǔn)的元素都移到基準(zhǔn)的右邊。這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)處于數(shù)列的中間位置，稱為 分區(qū)(partition)操作。
對基準(zhǔn)左邊和右邊的兩個(gè)子集，進(jìn)行遞歸操作，即不斷重復(fù)第一步和第二步。直到所有子集只剩下一個(gè)元素為止。
示例說明
下面我們舉個(gè)示例進(jìn)行排序說明，數(shù)列為[8,7,0,7,5,2,5,3,1]。
第一步: 基準(zhǔn)值選取。基準(zhǔn)值可以任意選取，便于理解，這里我們選擇中間值5作為基準(zhǔn)。
[8,7,0,7, 5, 2,5,3,1]
第二步: 進(jìn)行分區(qū)操作。按照順序?qū)⒚總�(gè)元素與基準(zhǔn)進(jìn)行比較，想成兩個(gè)子集，大于5與小于5.
[0,2,5,3,1, 5, 8,7,7]
第三步，遞歸操作。對兩個(gè)子集不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
[0,2, 5, 3,1] 5 [8, 7, 7][0,2,3,1, 5 ] 5 [7, 7, 8][0, 2, 3,1]5,5,7, 7, 8[0,1, 2, 3] 5, 5, 7, 7, 8[0,1,2,3,5,5,7,7,8]
Javascript的實(shí)現(xiàn)
講述了快速排序的基本思想，下面就讓我們使用代碼對其進(jìn)行實(shí)現(xiàn)吧~
第一步: 定義函數(shù)quicksort,參數(shù)為一個(gè)數(shù)組。
var quicksort = function(arr){
};
第二步: 檢查數(shù)組個(gè)數(shù)，小于等于1，則返回。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
}
};
第三步: 進(jìn)行基準(zhǔn)選擇，定義兩個(gè)空數(shù)組進(jìn)行左右兩個(gè)子集元素的存放。
var quicksort = function(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]);
}
}
};
第四步: 遞歸操作。對兩個(gè)子集不斷重復(fù)第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
var quicksort = function(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));
};
第五步: quicksort函數(shù)的調(diào)用
這里可以直接定義一個(gè)數(shù)組，對函數(shù)進(jìn)行調(diào)用即可。
var quicksort = function(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));
};var array = [8,7,0,7,5,2,5,3,1];
quicksort(array); //[0,1,2,3,5,5,7,7,8]
小結(jié)
快速排序的基本思想還是比較簡單的，巧用了分治法策略 ~。
【JavaScript快速排序?qū)崿F(xiàn)實(shí)例教程】相關(guān)文章：
深入理解JS實(shí)現(xiàn)快速排序和去重javascript技巧10-28
Javascript實(shí)例教程08-10
常用排序算法之JavaScript實(shí)現(xiàn)代碼段06-04
Javascript實(shí)例教程如何使用HoTMetal06-12
堆的javascript實(shí)現(xiàn)方法10-02
Javascript 繼承實(shí)現(xiàn)例子參考08-23
用Javascript進(jìn)行簡單的Table點(diǎn)擊排序08-29
使用JavaScript實(shí)現(xiàn)Java的List功能10-26