Javascript實現冒泡排序與快速排序以及對快速排序的性能優化

dadong 發布于2019-08-23 15:08 / 3608人閱讀

摘要：實現快速排序介紹通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

冒泡排序 介紹

重復遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后“冒泡”到數組的末端。假如數組長度為n，在n-1次遍歷后可完成排序。

實現

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function bubbleSort(arr) {
  let time = arr.length - 1
  while (time) {
    let i = 0
    while (i arr[i+1]) [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      i ++
    }    
    time --
  }
}

bubbleSort(arr)

快速排序 介紹

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

實現

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort(arr) {
  if (arr.length <= 1) return arr
  let pivotVal = arr[0],
  smallers = [], 
  biggers = [], 
  idx = 1
  while (idx < arr.length) {
    if (pivotVal > arr[idx]) {
      smallers.push(arr[idx])
    } else {
      biggers.push(arr[idx])
    }
    idx ++
  }
  return quickSort(smallers).concat(pivotVal, quickSort(biggers))
}

quickSort(arr)

這種方法較好理解，就是找一個基準元素，一般是數組的第1位，然后遍歷數組，比基準元素大的元素扔進去一個臨時數組里，較小的扔進另一個臨時數組里，最后把這兩個數組和基準元素按順序拼接起來。當然臨時數組還要遞歸調用方法來對內部繼續進行拆分，直到最后產生的臨時數組長度為0或1為止。

接下來對此方法進行優化，畢竟這樣一套遞歸下來，新建了不少臨時數組，對性能會有一定的影響。

優化

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort2(arr, start, end) {
  while(start >= end) return
  let pivot = start,
  pivotVal = arr[pivot],
  idx = pivot + 1
  while (idx <= end) {
    if (arr[idx] < pivotVal) {
      pivot ++
      if (arr[pivot] != arr[idx]) {
        [arr[pivot], arr[idx]] = [arr[idx], arr[pivot]]
      }
    }
    idx ++
  }
  [arr[pivot], arr[start]] = [arr[start], arr[pivot]]
  quickSort2(arr, pivot + 1, end)
  quickSort2(arr, 0, pivot - 1)
}

quickSort2(arr, 0, arr.length-1)

原理就是以數組的第一個元素為基準元素，從第二個元素開始對基準元素進行比較，如果比基準元素小則讓基準點前進一位，同時把現基準點上的值與對比元素的值對換。一次遍歷下來后，現基準點所在的位置就是最后一個比基準元素小的元素所在的位置，右邊是大于或者等于基準元素的元素，左邊是小于基準元素的元素（除了第一位，第一位是基準元素），所以最后一步操作就是讓現基準點上的元素和第一位上的元素（基準元素）互換，確保基準點和基準元素對應上。之后遞歸調用就可以完成。

快速排序，簡單高效，但是當序列長度在5到25之間時，直接插入排序的速度比快速排序快至少10%， 改進后的快速排序，當數據規模小于25時，采用直接插入排序。

插入排序 介紹

當插入第i(i ≥ 1)個元素時，假設前面從arr[0]到arr[i-1]已經有序，那么只需將arr[i]和前面那些有序的數值進行比較，找到自己應該插入的位置即可，原來位置上的元素一次向后順移。

實現

let arr = [0, 99, 2, 6, 1, 10, 2, 3, 1, 9, 0]

function insertSort(arr) {
  let idx = 1
  while(idx < arr.length) {
    while(idx > 0) {
      if (arr[idx] >= arr[idx-1]) break
      [arr[idx], arr[idx-1]] = [arr[idx-1], arr[idx]]    
      idx --
    }
    idx ++
  }
}

insertSort(arr)

云服務器 GPU云服務器最好的快速排序算法最快速的排序算法快速排序快速排序函數

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101581.html

JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0
JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
JavaScript各種排序算法的實現及其速度性能分析

摘要：今天我們來討論的問題有兩個如何用實現選擇排序冒泡排序插入排序快速排序歸并排序堆排序對生成的萬個隨機數進行排序，各個排序算法的性能分析。快速排序快速排序算法基本上是面試必考排序算法，也是傳聞最好用的算法。今天我們來討論的問題有兩個：如何用JavaScript實現選擇排序、冒泡排序、插入排序、快速排序、歸并排序、堆排序；對生成的10萬個隨機數進行排序，各個排序算法的性能分析。創...

yuanxin 2019-08-20 19:03 評論0 收藏0
JS數據結構與算法_排序和搜索算法

摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。上一篇：JS數據結構與算法_樹寫在前面這是《學習JavaScript數據結構與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

姘擱『 2019-08-23 16:26 評論0 收藏0