成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Javascript實(shí)現(xiàn)冒泡排序與快速排序以及對(duì)快速排序的性能優(yōu)化

dadong / 3615人閱讀

摘要：實(shí)現(xiàn)快速排序介紹通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

冒泡排序 介紹

重復(fù)遍歷要排序的元素列，依次比較兩個(gè)相鄰的元素，前一個(gè)元素若比后一個(gè)元素大則互換位置。以升序排序?yàn)槔?，最大的元素?huì)在第一次遍歷后“冒泡”到數(shù)組的末端。假如數(shù)組長(zhǎng)度為n，在n-1次遍歷后可完成排序。

實(shí)現(xiàn) 
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)
快速排序 介紹 
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
實(shí)現(xiàn) 
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)

這種方法較好理解，就是找一個(gè)基準(zhǔn)元素，一般是數(shù)組的第1位，然后遍歷數(shù)組，比基準(zhǔn)元素大的元素扔進(jìn)去一個(gè)臨時(shí)數(shù)組里，較小的扔進(jìn)另一個(gè)臨時(shí)數(shù)組里，最后把這兩個(gè)數(shù)組和基準(zhǔn)元素按順序拼接起來(lái)。當(dāng)然臨時(shí)數(shù)組還要遞歸調(diào)用方法來(lái)對(duì)內(nèi)部繼續(xù)進(jìn)行拆分，直到最后產(chǎn)生的臨時(shí)數(shù)組長(zhǎng)度為0或1為止。

接下來(lái)對(duì)此方法進(jìn)行優(yōu)化，畢竟這樣一套遞歸下來(lái)，新建了不少臨時(shí)數(shù)組，對(duì)性能會(huì)有一定的影響。

優(yōu)化 
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)

原理就是以數(shù)組的第一個(gè)元素為基準(zhǔn)元素，從第二個(gè)元素開(kāi)始對(duì)基準(zhǔn)元素進(jìn)行比較，如果比基準(zhǔn)元素小則讓基準(zhǔn)點(diǎn)前進(jìn)一位，同時(shí)把現(xiàn)基準(zhǔn)點(diǎn)上的值與對(duì)比元素的值對(duì)換。一次遍歷下來(lái)后，現(xiàn)基準(zhǔn)點(diǎn)所在的位置就是最后一個(gè)比基準(zhǔn)元素小的元素所在的位置，右邊是大于或者等于基準(zhǔn)元素的元素，左邊是小于基準(zhǔn)元素的元素（除了第一位，第一位是基準(zhǔn)元素），所以最后一步操作就是讓現(xiàn)基準(zhǔn)點(diǎn)上的元素和第一位上的元素（基準(zhǔn)元素）互換，確?；鶞?zhǔn)點(diǎn)和基準(zhǔn)元素對(duì)應(yīng)上。之后遞歸調(diào)用就可以完成。

快速排序，簡(jiǎn)單高效，但是當(dāng)序列長(zhǎng)度在5到25之間時(shí)，直接插入排序的速度比快速排序快至少10%， 改進(jìn)后的快速排序，當(dāng)數(shù)據(jù)規(guī)模小于25時(shí)，采用直接插入排序。
插入排序 介紹 
當(dāng)插入第i(i ≥ 1)個(gè)元素時(shí)，假設(shè)前面從arr[0]到arr[i-1]已經(jīng)有序，那么只需將arr[i]和前面那些有序的數(shù)值進(jìn)行比較，找到自己應(yīng)該插入的位置即可，原來(lái)位置上的元素一次向后順移。
實(shí)現(xiàn) 
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)

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

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

相關(guān)文章

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總

    摘要：筆者寫(xiě)的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語(yǔ)言是，旨在入門(mén)數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡(jiǎn)單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就...

    zsy888 評(píng)論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...

    canger 評(píng)論0 收藏0

  • JavaScript各種排序算法的實(shí)現(xiàn)及其速度性能分析

    摘要：今天我們來(lái)討論的問(wèn)題有兩個(gè)如何用實(shí)現(xiàn)選擇排序冒泡排序插入排序快速排序歸并排序堆排序?qū)ι傻娜f(wàn)個(gè)隨機(jī)數(shù)進(jìn)行排序，各個(gè)排序算法的性能分析?？焖倥判蚩焖倥判蛩惴ɑ旧鲜敲嬖嚤乜寂判蛩惴?，也是傳聞最好用的算法。 今天我們來(lái)討論的問(wèn)題有兩個(gè)： 如何用JavaScript實(shí)現(xiàn)選擇排序、冒泡排序、插入排序、快速排序、歸并排序、堆排序； 對(duì)生成的10萬(wàn)個(gè)隨機(jī)數(shù)進(jìn)行排序，各個(gè)排序算法的性能分析。 創(chuàng)...

    yuanxin 評(píng)論0 收藏0

  • JS數(shù)據(jù)結(jié)構(gòu)與算法_排序和搜索算法

    摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法樹(shù)寫(xiě)在前面這是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最后一篇博客，也是在面試中常常會(huì)被問(wèn)到的一部分內(nèi)容排序和搜索。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_樹(shù) 寫(xiě)在前面 這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會(huì)被問(wèn)到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無(wú)心去深入研究排序相...

    姘擱『 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<