快速排序js實(shí)現(xiàn)

zhoutk 發(fā)布于2019-08-22 16:22 / 2678人閱讀

摘要：然后再分別對基數(shù)左邊和右邊的數(shù)組進(jìn)行相同的操作，直到數(shù)組中只有一個元素時，返回該數(shù)組。

快速排序算法

今天大概講下使用js實(shí)現(xiàn)快速排序算法：

快速排序算法的思想類似于二分法，每次都是在數(shù)組中選擇一個基數(shù)（可以是任意一個位置的數(shù)，不過一般選擇中間的數(shù)字或者最左邊的數(shù)字），每一輪結(jié)束后，比該基數(shù)小的數(shù)都位于該基數(shù)的左邊，比該基數(shù)大的數(shù)都位于該基數(shù)的右邊。然后再分別對基數(shù)左邊和右邊的數(shù)組進(jìn)行相同的操作，直到數(shù)組中只有一個元素時，返回該數(shù)組。不說了，具體上代碼(我取數(shù)組最左邊的元素作為基數(shù))：

var arr=[5,7,2,9,3,8,4,7,1];
// 每次選擇最左邊的數(shù)作為基數(shù)
function quickSort(arr){
  if (arr.length<2) { return arr; }
  // 定義左指針
  var left=0;
  // 定義右指針
  var right=arr.length-1;
  //開啟每一輪的排序
  while(left=arr[0] && left
問題：為什么如果基數(shù)選擇數(shù)組最左邊元素，每次移動必須右指針先移動找到比基數(shù)小的數(shù)？同理選擇右邊，要先移動左指針？
回答：解決問題時可以有時候把問題放到極限情況下，這樣更加便于我們直觀的觀察和分析
我們假設(shè)如果基數(shù)選擇數(shù)組最左邊元素，而我們選擇先移動左指針。如果先移動左指針，則此時左指針與右指針相遇，此時交換arr[0]與arr[right]，交換后如第二張圖所示，本來交換后位于紅色7左邊的元素應(yīng)該都小于等于7，但是此時8位于7的左邊，明顯不符合要求。

GPU云服務(wù)器云服務(wù)器 js快速排序快速排序法js js實(shí)現(xiàn)table排序快速排序

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/94285.html

相關(guān)文章

js實(shí)現(xiàn)冒泡排序,快速排序,選擇排序

摘要：用冒泡排序快速排序選擇排序冒泡排序冒泡排序是比較經(jīng)典的排序方法，是一種用時間換空間的排序方法。找到并交換的時候，指針位置不變。選擇排序沒趟都會產(chǎn)生最小值，它不是相鄰元素的比較而是在該元素設(shè)置一個索引。選擇排序循環(huán)找到從開始到最后的最小的數(shù) 用js冒泡排序,快速排序,選擇排序 1.冒泡排序冒泡排序是比較經(jīng)典的排序方法，是一種用時間換空間的排序方法。我總結(jié)了一下它的特點(diǎn)：（1）它的時間復(fù)...

bbbbbb 2019-08-22 16:56 評論0 收藏0
關(guān)于JS的快速排序實(shí)現(xiàn)方法

摘要：所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分，所有比它大的記錄放置在后一部分，并把改記錄排在這兩部分的中間稱為該記錄歸位，這個過程稱作一次快速排序。代碼如下大佬的代碼還是比較厲害的，簡單易懂，佩服以上就是相關(guān)的快速排序的實(shí)現(xiàn)方法由于自己不是計(jì)算機(jī)專業(yè)，數(shù)據(jù)結(jié)構(gòu)沒有太多研究，曾經(jīng)面試時有被問過關(guān)于快速排序以及冒泡排序的寫法，冒泡排序比較簡單，當(dāng)時能回答出來，但是快速排序當(dāng)時就比較懵逼...

LeexMuller 2019-08-21 17:40 評論0 收藏0
js算法-快速排序(Quicksort)

摘要：快速排序英語，又稱劃分交換排序，簡稱快排，一種排序算法，最早由東尼霍爾提出。快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序n個項(xiàng)目要O(nLogn)次比較。在最壞狀況下則需要O(n^2)次比較，但這種狀況并不常見。事實(shí)上，快速排序O(nLogn)通常明顯比其他算...

Taste 2019-08-23 14:35 評論0 收藏0
排序算法速度測試（插入排序、二分法插入、選擇排序、快速排序、堆排序）js實(shí)現(xiàn)

摘要：公共函數(shù)庫用于取出隨機(jī)排列的數(shù)字原數(shù)組給原數(shù)組賦值排序算法插入排序時間復(fù)雜度二分法插入排序選擇排序快速排序一堆排序測試用例插入排序時間測試二分法插入排序時間測試選擇排序時間測試快速排序時間測試一堆公共函數(shù)庫（用于取出隨機(jī)排列的數(shù)字） module.exports={ randomIntegerArray:function(count){ var origina...

mochixuan 2019-08-20 16:04 評論0 收藏0
js 排序算法之快速排序

摘要：快速排序是一種劃分交換排序?？焖倥判蚧诿芭葸f歸分治。他在大數(shù)據(jù)情況下是最快的排序算法之一，平均事件復(fù)雜度很低而且前面的系數(shù)很小，在大量隨機(jī)輸入的情況下最壞情況出現(xiàn)的概率是極小的。快速排序是一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法。分治法的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。...

Eidesen 2019-08-23 11:38 評論0 收藏0