快捷導(dǎo)航

javascript 快速排序函數(shù)代碼

更新時(shí)間：2012年05月30日 16:47:25 作者：

主要原理是快速排序的原理：找基準(zhǔn)點(diǎn)、建立二個(gè)數(shù)組分別存儲(chǔ)、遞歸

核心代碼：

 
function quickSort(arr){ 
//如果數(shù)組只有一個(gè)數(shù)，就直接返回； 
if(arr.length<1){ 
return arr; 
} 
//找到中間的那個(gè)數(shù)的索引值；如果是浮點(diǎn)數(shù)，就向下取整 
var centerIndex = Math.floor(arr.length/2); 
//根據(jù)這個(gè)中間的數(shù)的索引值，找到這個(gè)數(shù)的值； 
var centerNum = arr.splice(centerIndex,1); 
//存放左邊的數(shù) 
var arrLeft = []; 
//存放右邊的數(shù) 
var arrRight = []; 
for(i=0;i<arr.length;i++){ 
if(arr[i]<centerNum){ 
arrLeft.push(arr[i]) 
}else if(arr[i]>centerNum){ 
arrRight.push(arr[i]) 
} 
} 
return quickSort(arrLeft).concat(centerNum,quickSort(arrRight)); 
}; 
var arrSort = [33,18,2,40,16,63,27]; 
var arr1 = quickSort(arrSort); 
console.log(arr1); 

主要原理是：快速排序的原理：找基準(zhǔn)點(diǎn)、建立二個(gè)數(shù)組分別存儲(chǔ)、遞歸

基準(zhǔn)點(diǎn)：就是找到這個(gè)數(shù)組中間的一個(gè)數(shù)；

建立二個(gè)數(shù)組分別存儲(chǔ)：就是以這個(gè)基準(zhǔn)點(diǎn)，將它的左右數(shù)值，分別存放到兩個(gè)定義的新數(shù)組當(dāng)中；

遞歸：在函數(shù)內(nèi)部調(diào)用自身；

這里我總結(jié)的一點(diǎn)是在使用遞歸時(shí)：
1.必需要有一個(gè)判斷，并且返回一個(gè)值；不然就是一個(gè)死循環(huán)了；
2.在內(nèi)部調(diào)用自己的時(shí)候，傳的參數(shù)是內(nèi)部定義的某個(gè)變量，這個(gè)變量和初次傳時(shí)來(lái)的參數(shù)，有關(guān)聯(lián)；
3.要執(zhí)行同樣的工作，可以考慮用遞歸；

這是第一次執(zhí)行函數(shù)的變量情況：中間數(shù)是40；根據(jù)循環(huán)里的判斷條件小于40的存放在arrLeft，大于40的存放在arrRight里面。如下圖

第二次調(diào)用函數(shù)
,當(dāng)執(zhí)行到 return quickSort(arrLeft).concat(centerNum,quickSort(arrRight));
quickSort(arrLeft)會(huì)去調(diào)用函數(shù)，傳的參數(shù)是[33,18,2,16,27]
中間數(shù)是2，比2小的放左邊arrLeft，比2大的放右邊arrRight