JS排序之快速排序詳解
更新時間：2017年04月08日 11:54:56 作者：Blue-Beginner
這篇文章主要為大家詳細介紹了JS快速排序的相關(guān)資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文為大家分享了JS快速排序的具體代碼，供大家參考，具體內(nèi)容如下
說明
時間復(fù)雜度指的是一個算法執(zhí)行所耗費的時間
空間復(fù)雜度指運行完一個程序所需內(nèi)存的大小
穩(wěn)定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不穩(wěn)定指，如果a=b，a在b的前面，排序后可能會交換位置
--JS快速排序--
原理
從數(shù)組中選定一個基數(shù)，然后把數(shù)組中的每一項與此基數(shù)做比較，小的放入一個新數(shù)組，大的放入另外一個新數(shù)組。然后再采用這樣的方法操作新數(shù)組。直到所有子集只剩下一個元素，排序完成。
時間復(fù)雜度，空間復(fù)雜度，穩(wěn)定性
- 平均時間復(fù)雜度O(nlogn)
- 最好情況O(nlogn)
- 最差情況O(n*n)
- 空間復(fù)雜度O(logn)
- 穩(wěn)定性：不穩(wěn)定
快速排序的寫法
var examplearr=[8,94,15,88,55,76,21,39];
function fastsort(arr){
if(arr.length<2){
return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
for(i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i])
}
}
return fastsort(left).concat([pivot],fastsort(right));
}
console.log(fastsort(examplearr));
解析
pivotIndex是將數(shù)組的長度除2向下取整得到的一個數(shù)值，數(shù)組的長度是不斷減半的，所以最后它的值為0
pivot是利用splice方法從數(shù)組里獲取一個基數(shù)
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了微信小程序tab左右滑動切換功能的實現(xiàn)代碼,本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02
csdn 博客中實現(xiàn)運行代碼功能實現(xiàn)
有時候因為csdn的博客經(jīng)常處理一些字符，導(dǎo)致代碼很多情況下，都不能正常運行，給大家的閱讀帶來了麻煩，下面是腳本之家編輯簡單的整理下。2009-08-08
js 樹組復(fù)制方法2009-02-02
本篇文章主要介紹了js浮點數(shù)精確計算(加、減、乘、除) 需要的朋友可以過來參考下，希望對大家有所幫助2013-12-12
微信小程序?qū)崙?zhàn)項目之富文本編輯器實現(xiàn)
富文本在Web開發(fā)上的地位大家可想而知,很多地方都需要用到富文本編輯器,比如開發(fā)類似新聞管理小程序、商品簡介等,下面這篇文章主要給大家介紹了關(guān)于微信小程序?qū)崙?zhàn)項目之富文本編輯器實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-10-10
基于Electron實現(xiàn)桌面應(yīng)用開發(fā)代碼實例
這篇文章主要介紹了基于Electron實現(xiàn)桌面應(yīng)用開發(fā)代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
這篇文章主要為大家詳細介紹了利用bootstrapValidator驗證UEditor,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-09-09
本文主要給大家介紹了javascript中的scrollTop方法，以及scrollTop在各大瀏覽器的兼容性情況的詳細測試，十分的細致全面，這里推薦給大家，有需要的小伙伴可以參考下。2015-04-04
原生JavaScript實現(xiàn)todolist功能
本篇文章給大家介紹了通過原生JavaScript實現(xiàn)todolist功能相關(guān)知識點，對此有需要的朋友可以學(xué)習(xí)下。2018-03-03
這篇文章主要介紹了JS防抖和節(jié)流實例解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09