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