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

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

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

快速排序算法

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

快速排序算法的思想類似于二分法，每次都是在數(shù)組中選擇一個(gè)基數(shù)（可以是任意一個(gè)位置的數(shù)，不過(guò)一般選擇中間的數(shù)字或者最左邊的數(shù)字），每一輪結(jié)束后，比該基數(shù)小的數(shù)都位于該基數(shù)的左邊，比該基數(shù)大的數(shù)都位于該基數(shù)的右邊。然后再分別對(duì)基數(shù)左邊和右邊的數(shù)組進(jìn)行相同的操作，直到數(shù)組中只有一個(gè)元素時(shí)，返回該數(shù)組。不說(shuō)了，具體上代碼(我取數(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;
  //開(kāi)啟每一輪的排序
  while(left=arr[0] && left
問(wèn)題：為什么如果基數(shù)選擇數(shù)組最左邊元素，每次移動(dòng)必須右指針先移動(dòng)找到比基數(shù)小的數(shù)？同理選擇右邊，要先移動(dòng)左指針？
回答：解決問(wèn)題時(shí)可以有時(shí)候把問(wèn)題放到極限情況下，這樣更加便于我們直觀的觀察和分析
我們假設(shè)如果基數(shù)選擇數(shù)組最左邊元素，而我們選擇先移動(dòng)左指針。如果先移動(dòng)左指針，則此時(shí)左指針與右指針相遇，此時(shí)交換arr[0]與arr[right]，交換后如第二張圖所示，本來(lái)交換后位于紅色7左邊的元素應(yīng)該都小于等于7，但是此時(shí)8位于7的左邊，明顯不符合要求。

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/94285.html

相關(guān)文章

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

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

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

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

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

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

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

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

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

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

Eidesen 2019-08-23 11:38 評(píng)論0 收藏0