JS實現(xiàn)隨機化快速排序的實例代碼
更新時間：2013年08月01日 16:47:24 作者：
這篇文章介紹了JS實現(xiàn)隨機化快速排序的實例代碼，有需要的朋友可以參考一下
算法的平均時間復(fù)雜度為O(nlogn)。但是當(dāng)輸入是已經(jīng)排序的數(shù)組或幾乎排好序的輸入，時間復(fù)雜度卻為O(n^2)。為解決這一問題并保證平均時間復(fù)雜度為O(nlogn)的方法是引入預(yù)處理步驟，它惟一的目的是改變元素的順序使之隨機排序。這種預(yù)處理步驟可在O(n)時間內(nèi)運行。能夠起到同樣作用的另一種簡單方法是在算法中引入一個隨機元素，這可以通過隨機地選擇拆分元素的主元來實現(xiàn)。隨機選擇主元的結(jié)果放寬了關(guān)于輸入元素的所有排列的可能性相同的步驟。引入這一步來修正原先的快速排序，可得到下面所示的隨機化快速排序。新算法只是在區(qū)間[low…h(huán)igh]中一致隨機地選擇一個索引v，并將A[v]和A[low]交換，然后按照原來的快速排序算法繼續(xù)。這里，parseInt(Math.random()*(high-low+1) + low)返回一個在low和high之間的數(shù)。
/****************************************
算法：split
輸入：數(shù)組A[low...high]
輸出：
1.若有必要，輸出按上述描述的重新排列的數(shù)組A;
2.劃分元素A[low]的新位置w;
****************************************/
function split(array, low, high) {
var i = low;
var x = array[low];
for(var j = low + 1; j <= high; j++) {
if(array[j] <= x) {
i ++;
if(i != j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
temp = array[low];
array[low] = array[i];
array[i] = temp;
return i;
}
/****************************************
算法：rquicksort
輸入：A[0...n-1]
輸出：按非降序排列數(shù)組A[0...n-1]
rquicksort(A, 0, n-1);
****************************************/
function rquicksort(array, low, high) {
if(low < high) {
/******隨機化拆分元素的主元*******/
var v = parseInt(Math.random()*(high-low+1) + low);
var tmp = array[low];
array[low] = array[v];
array[v] = tmp;
/******隨機化拆分元素的主元*******/
var w = split(array, low, high);
rquicksort(array, low, w -1);
rquicksort(array, w +1, high);
return array;
}
}
var array = [33, 22, 11, 88, 23, 32];
array = rquicksort(array, 0, array.length-1);
console.log(array);
復(fù)制代碼 代碼如下:
/****************************************
算法：split
輸入：數(shù)組A[low...high]
輸出：
1.若有必要，輸出按上述描述的重新排列的數(shù)組A;
2.劃分元素A[low]的新位置w;
****************************************/
function split(array, low, high) {
var i = low;
var x = array[low];
for(var j = low + 1; j <= high; j++) {
if(array[j] <= x) {
i ++;
if(i != j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
temp = array[low];
array[low] = array[i];
array[i] = temp;
return i;
}
/****************************************
算法：rquicksort
輸入：A[0...n-1]
輸出：按非降序排列數(shù)組A[0...n-1]
rquicksort(A, 0, n-1);
****************************************/
function rquicksort(array, low, high) {
if(low < high) {
/******隨機化拆分元素的主元*******/
var v = parseInt(Math.random()*(high-low+1) + low);
var tmp = array[low];
array[low] = array[v];
array[v] = tmp;
/******隨機化拆分元素的主元*******/
var w = split(array, low, high);
rquicksort(array, low, w -1);
rquicksort(array, w +1, high);
return array;
}
}
var array = [33, 22, 11, 88, 23, 32];
array = rquicksort(array, 0, array.length-1);
console.log(array);
您可能感興趣的文章:
相關(guān)文章
file模式訪問網(wǎng)頁時iframe高度自適應(yīng)解決方案
最近做到iframe的高度自適應(yīng)這個問題;發(fā)現(xiàn)自己做的網(wǎng)頁是通過file方式訪問的，將網(wǎng)頁代碼放到apache下通過http協(xié)議訪問，在iframe加載的時候調(diào)用如下js方法:果然網(wǎng)頁高度能夠自適應(yīng)（對于其他方案應(yīng)該也有效果，我沒有注意去嘗試）感興趣的朋友可以了解下2013-01-01
javascript替換已有元素replaceChild()使用介紹
這篇文章主要介紹了javascript替換已有元素replaceChild()使用,需要的朋友可以參考下2014-04-04
JavaScript進(jìn)階練習(xí)及簡單實例分析
下面小編就為大家?guī)硪黄狫avaScript進(jìn)階練習(xí)及簡單實例分析。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
這篇文章主要為大家詳細(xì)介紹了如何利用JavaScript實現(xiàn)批量重命名文件,文中的示例代碼講解詳細(xì),有需要的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-12-12
本文主要介紹了使用javascript實現(xiàn)雪花飄落的特效，雖然網(wǎng)上有很多，不過都是比較陳舊了，兼容性不是太好，于是動手寫一個，把思路和實現(xiàn)代碼都分享給大家。2015-01-01
微信分享的標(biāo)題、縮略圖、連接及描述設(shè)置方法
微信分享的標(biāo)題、縮略圖、連接及描述該如何設(shè)置，這個問題確實難道不少朋友，下面有個示例，大家可以看看2014-10-10
javascript利用canvas實現(xiàn)鼠標(biāo)拖拽功能
這篇文章主要為大家詳細(xì)介紹了javascript利用canvas實現(xiàn)鼠標(biāo)拖拽功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07![JavaScript 字符串與數(shù)組轉(zhuǎn)換函數(shù)[不用split與join]](http://img.jbzj.com/images/xgimg/bcimg7.png)
JavaScript 字符串與數(shù)組轉(zhuǎn)換函數(shù)[不用split與join]
下面的代碼，不考慮他的運行效率的話，思路不錯，大家可以看看，但在實際的應(yīng)用中，我們?nèi)匀皇褂胹plit或join來實現(xiàn)數(shù)組的操作。2009-12-12
這篇文章主要介紹了TypeScript 運行時類型檢查補充工具，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
這篇文章主要為大家詳細(xì)介紹了js實現(xiàn)手表表盤時鐘與圓周運動，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-09-09