JS排序之快速排序詳解
更新時間：2017年04月08日 11:54:56 作者：Blue-Beginner
這篇文章主要為大家詳細介紹了JS快速排序的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文為大家分享了JS快速排序的具體代碼，供大家參考，具體內容如下
說明
時間復雜度指的是一個算法執(zhí)行所耗費的時間
空間復雜度指運行完一個程序所需內存的大小
穩(wěn)定指，如果a=b,a在b的前面，排序后a仍然在b的前面
不穩(wěn)定指，如果a=b，a在b的前面，排序后可能會交換位置
--JS快速排序--
原理
從數組中選定一個基數，然后把數組中的每一項與此基數做比較，小的放入一個新數組，大的放入另外一個新數組。然后再采用這樣的方法操作新數組。直到所有子集只剩下一個元素，排序完成。
時間復雜度，空間復雜度，穩(wěn)定性
- 平均時間復雜度O(nlogn)
- 最好情況O(nlogn)
- 最差情況O(n*n)
- 空間復雜度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是將數組的長度除2向下取整得到的一個數值，數組的長度是不斷減半的，所以最后它的值為0
pivot是利用splice方法從數組里獲取一個基數
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了探討跨域請求資源的幾種方式（總結），小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
微信小程序wxss如何引用外部CSS文件以及iconfont
這篇文章主要給大家介紹了關于微信小程序wxss如何引用外部CSS文件以及iconfont的相關資料，文中通過圖文介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
極品源碼：自動完成 仿163篇...2007-07-07
詳解原生JavaScript實現jQuery中AJAX處理的方法
這篇文章主要介紹了原生JavaScript實現jQuery中AJAX處理的方法,作者根據jQuery中一些對AJAX請求的處理方式來用原生API實現,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了淺談讓你的代碼更簡短，更整潔，更易讀的ES6小技巧，小編覺得挺不錯的，現在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-10-10
2008-02-02
網頁可見區(qū)域寬或高、網頁正文全文寬或高以及網頁正文部分左或右，詳細請看下文，希望對大家有所幫助2013-06-06
這篇文章主要介紹了js如何獲取元素下面所有的li，有哪些方法,需要的朋友可以參考下2014-04-04
本文給大家分享的是使用javascript實現的簡單的鍵盤打字效果，十分的簡單實用，推薦給有需要的小伙伴參考下。2015-04-04
這篇文章主要為大家詳細介紹了JavaScript實現二級菜單的制作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10