快捷導(dǎo)航

JS實(shí)現(xiàn)隨機(jī)化快速排序的實(shí)例代碼

更新時(shí)間：2013年08月01日 16:47:24 作者：

這篇文章介紹了JS實(shí)現(xiàn)隨機(jī)化快速排序的實(shí)例代碼，有需要的朋友可以參考一下

算法的平均時(shí)間復(fù)雜度為O(nlogn)。但是當(dāng)輸入是已經(jīng)排序的數(shù)組或幾乎排好序的輸入，時(shí)間復(fù)雜度卻為O(n^2)。為解決這一問(wèn)題并保證平均時(shí)間復(fù)雜度為O(nlogn)的方法是引入預(yù)處理步驟，它惟一的目的是改變?cè)氐捻樞蚴怪S機(jī)排序。這種預(yù)處理步驟可在O(n)時(shí)間內(nèi)運(yùn)行。能夠起到同樣作用的另一種簡(jiǎn)單方法是在算法中引入一個(gè)隨機(jī)元素，這可以通過(guò)隨機(jī)地選擇拆分元素的主元來(lái)實(shí)現(xiàn)。隨機(jī)選擇主元的結(jié)果放寬了關(guān)于輸入元素的所有排列的可能性相同的步驟。引入這一步來(lái)修正原先的快速排序，可得到下面所示的隨機(jī)化快速排序。新算法只是在區(qū)間[low…h(huán)igh]中一致隨機(jī)地選擇一個(gè)索引v，并將A[v]和A[low]交換，然后按照原來(lái)的快速排序算法繼續(xù)。這里，parseInt(Math.random()*(high-low+1) + low)返回一個(gè)在low和high之間的數(shù)。

復(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) {
　　/******隨機(jī)化拆分元素的主元*******/
　　var v = parseInt(Math.random()*(high-low+1) + low);
　　var tmp = array[low];
　　array[low] = array[v];
　　array[v] = tmp;
　　/******隨機(jī)化拆分元素的主元*******/
　　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模式訪(fǎng)問(wèn)網(wǎng)頁(yè)時(shí)iframe高度自適應(yīng)解決方案
最近做到iframe的高度自適應(yīng)這個(gè)問(wèn)題;發(fā)現(xiàn)自己做的網(wǎng)頁(yè)是通過(guò)file方式訪(fǎng)問(wèn)的，將網(wǎng)頁(yè)代碼放到apache下通過(guò)http協(xié)議訪(fǎng)問(wèn)，在iframe加載的時(shí)候調(diào)用如下js方法:果然網(wǎng)頁(yè)高度能夠自適應(yīng)（對(duì)于其他方案應(yīng)該也有效果，我沒(méi)有注意去嘗試）感興趣的朋友可以了解下
2013-01-01
javascript替換已有元素replaceChild()使用介紹
這篇文章主要介紹了javascript替換已有元素replaceChild()使用,需要的朋友可以參考下
2014-04-04
JavaScript進(jìn)階練習(xí)及簡(jiǎn)單實(shí)例分析
下面小編就為大家?guī)?lái)一篇JavaScript進(jìn)階練習(xí)及簡(jiǎn)單實(shí)例分析。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2016-06-06
JavaScript實(shí)現(xiàn)批量重命名文件
這篇文章主要為大家詳細(xì)介紹了如何利用JavaScript實(shí)現(xiàn)批量重命名文件,文中的示例代碼講解詳細(xì),有需要的小伙伴可以跟隨小編一起學(xué)習(xí)一下
2024-12-12
使用javascript實(shí)現(xiàn)雪花飄落的效果
本文主要介紹了使用javascript實(shí)現(xiàn)雪花飄落的特效，雖然網(wǎng)上有很多，不過(guò)都是比較陳舊了，兼容性不是太好，于是動(dòng)手寫(xiě)一個(gè)，把思路和實(shí)現(xiàn)代碼都分享給大家。
2015-01-01
微信分享的標(biāo)題、縮略圖、連接及描述設(shè)置方法
微信分享的標(biāo)題、縮略圖、連接及描述該如何設(shè)置，這個(gè)問(wèn)題確實(shí)難道不少朋友，下面有個(gè)示例，大家可以看看
2014-10-10
javascript利用canvas實(shí)現(xiàn)鼠標(biāo)拖拽功能
這篇文章主要為大家詳細(xì)介紹了javascript利用canvas實(shí)現(xiàn)鼠標(biāo)拖拽功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-07-07
JavaScript 字符串與數(shù)組轉(zhuǎn)換函數(shù)[不用split與join]
下面的代碼，不考慮他的運(yùn)行效率的話(huà)，思路不錯(cuò)，大家可以看看，但在實(shí)際的應(yīng)用中，我們?nèi)匀皇褂胹plit或join來(lái)實(shí)現(xiàn)數(shù)組的操作。
2009-12-12
TypeScript 運(yùn)行時(shí)類(lèi)型檢查補(bǔ)充工具
這篇文章主要介紹了TypeScript 運(yùn)行時(shí)類(lèi)型檢查補(bǔ)充工具，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2020-09-09
js實(shí)現(xiàn)手表表盤(pán)時(shí)鐘與圓周運(yùn)動(dòng)
這篇文章主要為大家詳細(xì)介紹了js實(shí)現(xiàn)手表表盤(pán)時(shí)鐘與圓周運(yùn)動(dòng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-09-09