資訊專欄INFORMATION COLUMN
摘要：實現(xiàn)快速排序介紹通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
冒泡排序 介紹
重復(fù)遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后“冒泡”到數(shù)組的末端。假如數(shù)組長度為n，在n-1次遍歷后可完成排序。
實現(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)
快速排序
介紹
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。實現(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)
這種方法較好理解，就是找一個基準(zhǔn)元素，一般是數(shù)組的第1位，然后遍歷數(shù)組，比基準(zhǔn)元素大的元素扔進去一個臨時數(shù)組里，較小的扔進另一個臨時數(shù)組里，最后把這兩個數(shù)組和基準(zhǔn)元素按順序拼接起來。當(dāng)然臨時數(shù)組還要遞歸調(diào)用方法來對內(nèi)部繼續(xù)進行拆分，直到最后產(chǎn)生的臨時數(shù)組長度為0或1為止。
接下來對此方法進行優(yōu)化，畢竟這樣一套遞歸下來，新建了不少臨時數(shù)組，對性能會有一定的影響。
優(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ù)組的第一個元素為基準(zhǔn)元素，從第二個元素開始對基準(zhǔn)元素進行比較，如果比基準(zhǔn)元素小則讓基準(zhǔn)點前進一位，同時把現(xiàn)基準(zhǔn)點上的值與對比元素的值對換。一次遍歷下來后，現(xiàn)基準(zhǔn)點所在的位置就是最后一個比基準(zhǔn)元素小的元素所在的位置，右邊是大于或者等于基準(zhǔn)元素的元素，左邊是小于基準(zhǔn)元素的元素（除了第一位，第一位是基準(zhǔn)元素），所以最后一步操作就是讓現(xiàn)基準(zhǔn)點上的元素和第一位上的元素（基準(zhǔn)元素）互換，確?；鶞?zhǔn)點和基準(zhǔn)元素對應(yīng)上。之后遞歸調(diào)用就可以完成。
快速排序，簡單高效，但是當(dāng)序列長度在5到25之間時，直接插入排序的速度比快速排序快至少10%， 改進后的快速排序，當(dāng)數(shù)據(jù)規(guī)模小于25時，采用直接插入排序。插入排序 介紹
當(dāng)插入第i(i ≥ 1)個元素時，假設(shè)前面從arr[0]到arr[i-1]已經(jīng)有序，那么只需將arr[i]和前面那些有序的數(shù)值進行比較，找到自己應(yīng)該插入的位置即可，原來位置上的元素一次向后順移。實現(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/101581.html
摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數(shù)據(jù)。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就...
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復(fù)雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，...
摘要：今天我們來討論的問題有兩個如何用實現(xiàn)選擇排序冒泡排序插入排序快速排序歸并排序堆排序?qū)ι傻娜f個隨機數(shù)進行排序，各個排序算法的性能分析?？焖倥判蚩焖倥判蛩惴ɑ旧鲜敲嬖嚤乜寂判蛩惴?，也是傳聞最好用的算法。 今天我們來討論的問題有兩個： 如何用JavaScript實現(xiàn)選擇排序、冒泡排序、插入排序、快速排序、歸并排序、堆排序； 對生成的10萬個隨機數(shù)進行排序，各個排序算法的性能分析。 創(chuàng)...
摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法樹寫在前面這是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最后一篇博客，也是在面試中常常會被問到的一部分內(nèi)容排序和搜索。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_樹 寫在前面 這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...
閱讀 1832·2021-09-26 09:55
閱讀 5858·2021-09-22 15:40
閱讀 2092·2019-08-30 15:53
閱讀 1561·2019-08-30 11:15
閱讀 1801·2019-08-29 15:41
閱讀 1942·2019-08-28 18:13
閱讀 3233·2019-08-26 12:00
閱讀 1735·2019-08-26 10:30
