資訊專欄INFORMATION COLUMN
摘要：所有關(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í)就比較懵逼，不知道是個(gè)什么方式實(shí)現(xiàn)的，面試回來(lái)后也沒(méi)太在意，最近在看C語(yǔ)言的數(shù)據(jù)結(jié)構(gòu)，拓展下這方面的知識(shí)，其中就看到了關(guān)于快排算法的描述
描述如下：在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），數(shù)據(jù)序列被此記錄劃分成兩部分。所有關(guān)鍵字比該記錄關(guān)鍵字小的記錄放置在前一部分，所有比它大的記錄放置在后一部分，并把改記錄排在這兩部分的中間（稱為該記錄歸位），這個(gè)過(guò)程稱作一次快速排序。之后對(duì)所有的兩部分分別重復(fù)上述過(guò)程，直至每部分內(nèi)只有一個(gè)記錄或空為止。
光看概念有點(diǎn)暈，書上用的是C的源代碼，改寫下，變成JS代碼：
function quickSort(arr, start, end){
var i = start
var j = end
if (start < end ) {
var temp = arr[start]
while (i != j ) {
while(arr[j] > temp && j > i){
j--
}
var com = arr[j]
arr[j] = arr[i]
arr[i] = com
while(arr[i] < temp && i < j){
i++
}
var com1 = arr[j]
arr[j] = arr[i]
arr[i] = com1
}
arr[i] = temp
quickSort(arr, start, i - 1)
quickSort(arr, i + 1, end)
}
}
解釋下：
假設(shè)一個(gè)無(wú)序數(shù)組：[6,8,7,9,0,1,3,2,4,5]
取第一個(gè)元素為參考元素，先從尾端開始即end向左遍歷，元素下標(biāo)為j, 發(fā)現(xiàn)比參考元素小的值，則與從左向右遍歷的元素arr[i]進(jìn)行交換，然后就從i開始向右遍歷，找到一個(gè)比參考元素大的值，而后與arr[j]進(jìn)行交換，最終i = j 時(shí)完成一次快速排序,然后對(duì)左邊部分進(jìn)行快排，對(duì)右邊進(jìn)行快排。
根據(jù)書上就是這樣的了，自己也嘗試了下，答案是沒(méi)有問(wèn)題的
然后看網(wǎng)上某位大佬的做法，更加簡(jiǎn)單易懂，將快排簡(jiǎn)單化，就是比參考元素小的放置左邊部分，比參考元素大的放置右邊部分，而后分別對(duì)兩部分進(jìn)行快排。
代碼如下：
function quickSort(arr){
if (arr.length <= 1) {
return arr
}
var left = [], right=[]
var pivotIndex = Math.floor(arr.length / 2)
var pivot = arr.splice(pivotIndex, 1)[0]
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
}else {
right.push(arr[i])
}
}
return quickSort(left).concat([pivot], quickSort(right))
}
大佬的代碼還是比較厲害的，簡(jiǎn)單易懂，佩服
以上就是相關(guān)的快速排序的實(shí)現(xiàn)方法
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/89852.html
摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時(shí)間復(fù)雜度為?？焖倥判蚍ǖ脑砜焖倥判蚴且环N劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學(xué)堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時(shí)間復(fù)雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時(shí)間復(fù)雜度為O (n l...
摘要：雖然有著各種各樣的不同，但是相同的是，他們前端優(yōu)化不完全指南前端掘金篇幅可能有點(diǎn)長(zhǎng)，我想先聊一聊閱讀的方式，我希望你閱讀的時(shí)候，能夠把我當(dāng)作你的競(jìng)爭(zhēng)對(duì)手，你的夢(mèng)想是超越我。 如何提升頁(yè)面渲染效率 - 前端 - 掘金Web頁(yè)面的性能 我們每天都會(huì)瀏覽很多的Web頁(yè)面，使用很多基于Web的應(yīng)用。這些站點(diǎn)看起來(lái)既不一樣，用途也都各有不同，有在線視頻，Social Media，新聞，郵件客戶端...
摘要：忍者級(jí)別的函數(shù)操作對(duì)于什么是匿名函數(shù)，這里就不做過(guò)多介紹了。我們需要知道的是，對(duì)于而言，匿名函數(shù)是一個(gè)很重要且具有邏輯性的特性。通常，匿名函數(shù)的使用情況是創(chuàng)建一個(gè)供以后使用的函數(shù)。 JS 中的遞歸 遞歸, 遞歸基礎(chǔ), 斐波那契數(shù)列, 使用遞歸方式深拷貝, 自定義事件添加 這一次，徹底弄懂 JavaScript 執(zhí)行機(jī)制 本文的目的就是要保證你徹底弄懂javascript的執(zhí)行機(jī)制，如果...
摘要：插入排序是穩(wěn)定的算法。所以準(zhǔn)確的說(shuō)，當(dāng)數(shù)組長(zhǎng)度大于的時(shí)候，采用了快速排序和插入排序的混合排序方法。在對(duì)數(shù)組進(jìn)行了一次快速排序后，然后對(duì)兩個(gè)子集分別進(jìn)行了插入排序，最終修改數(shù)組為正確排序后的數(shù)組。 JavaScript 專題系列第二十篇，也是最后一篇，解讀 v8 排序源碼 前言 v8 是 Chrome 的 JavaScript 引擎，其中關(guān)于數(shù)組的排序完全采用了 JavaScript 實(shí)...
閱讀 3302·2023-04-26 01:31
閱讀 1922·2023-04-25 22:08
閱讀 3512·2021-09-01 11:42
閱讀 2857·2019-08-30 12:58
閱讀 2212·2019-08-29 18:31
閱讀 2462·2019-08-29 17:18
閱讀 3092·2019-08-29 13:01
閱讀 2580·2019-08-28 18:22
