目錄前言冒泡排序基礎(chǔ)算法第二種寫(xiě)法是在基礎(chǔ)算法的基礎(chǔ)上改良而來(lái)的：選擇排序基礎(chǔ)算法二元選擇排序-優(yōu)化插入排序交換法插入排序移動(dòng)法希爾排序堆排序快速排序歸并排序總結(jié)前言

所謂排序算法，即通過(guò)特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計(jì)算，大大提高了計(jì)算效率。對(duì)于排序，我們首先要求其具有一定的穩(wěn)定性，即當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)于某個(gè)序列之中，則經(jīng)過(guò)一定的排序算法之后，兩者在排序前后的相對(duì)位置不發(fā)生變化。換言之，即便是兩個(gè)完全相同的元素，它們?cè)谂判蜻^(guò)程中也是各有區(qū)別的，不允許混淆不清。

冒泡排序

冒泡排序是入門(mén)級(jí)的算法，但也有一些有趣的玩法。通常來(lái)說(shuō)，冒泡排序有三種寫(xiě)法：

一邊比較一邊向后兩兩交換，將最大值 / 最小值冒泡到最后一位；經(jīng)過(guò)優(yōu)化的寫(xiě)法：使用一個(gè)變量記錄當(dāng)前輪次的比較是否發(fā)生過(guò)交換，如果沒(méi)有發(fā)生交換表示已經(jīng)有序，不再繼續(xù)排序；

基礎(chǔ)算法

空間復(fù)雜度為 O(1)，時(shí)間復(fù)雜度為 O(n2)

const sort = (arr) => { for (let i = 0, len = arr.length; i < len-1; i++){for (let j = 0; j < len-1-i; j++) { if (arr[j] > arr[j+1]) {[arr[j], arr[j+1]] = [arr[j+1], arr[j]]; }} } return arr}

最外層的 for 循環(huán)每經(jīng)過(guò)一輪，剩余數(shù)字中的最大值就會(huì)被移動(dòng)到當(dāng)前輪次的最后一位，中途也會(huì)有一些相鄰的數(shù)字經(jīng)過(guò)交換變得有序。總共比較次數(shù)是 (n-1)+(n-2)+(n-3)+…+1(n−1)+(n−2)+(n−3)+…+1。

第二種寫(xiě)法是在基礎(chǔ)算法的基礎(chǔ)上改良而來(lái)的：

const sort = (arr) => { for (let i = 0, len = arr.length; i < len - 1; i++) {let isSwap = falsefor (let j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];isSwap = true }}if (!isSwap) { break;} } return arr;};

空間復(fù)雜度為O(1);時(shí)間復(fù)雜度為 O(n2)-最好為O(n);

最外層的 for 循環(huán)每經(jīng)過(guò)一輪，剩余數(shù)字中的最大值仍然是被移動(dòng)到當(dāng)前輪次的最后一位。這種寫(xiě)法相對(duì)于第一種寫(xiě)法的優(yōu)點(diǎn)是：如果一輪比較中沒(méi)有發(fā)生過(guò)交換，則立即停止排序，因?yàn)榇藭r(shí)剩余數(shù)字一定已經(jīng)有序了。

選擇排序

選擇排序的思想是：雙重循環(huán)遍歷數(shù)組，每經(jīng)過(guò)一輪比較，找到最小元素的下標(biāo)，將其交換至首位。

基礎(chǔ)算法

const sort = (arr) => { for (let i = 0, len = arr.length; i < len - 1; i++) {let minIndex = ifor (let j = i+1; j < len; j++) { if (arr[i] > arr[j]) {minIndex = j }}[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } return arr;};二元選擇排序-優(yōu)化

選擇排序算法也是可以?xún)?yōu)化的，既然每輪遍歷時(shí)找出了最小值，何不把最大值也順便找出來(lái)呢？這就是二元選擇排序的思想。

使用二元選擇排序，每輪選擇時(shí)記錄最小值和最大值，可以把數(shù)組需要遍歷的范圍縮小一倍。

const sort = (arr) => { for (let i = 0, len = arr.length; i < len / 2; i++) {let minIndex = i;let maxIndex = i;for (let j = i + 1; j < len-i; j++) { if (arr[minIndex] > arr[j]) {minIndex = j; } if (arr[maxIndex] < arr[j]) {maxIndex = j; }}if (minIndex === maxIndex) break;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];if (maxIndex === i) { maxIndex = minIndex;}const lastIndex = len - i - 1;[arr[maxIndex], arr[lastIndex]] = [arr[lastIndex], arr[maxIndex]]; } return arr; };插入排序

插入排序的思想非常簡(jiǎn)單，生活中有一個(gè)很常見(jiàn)的場(chǎng)景：在打撲克牌時(shí)，我們一邊抓牌一邊給撲克牌排序，每次摸一張牌，就將它插入手上已有的牌中合適的位置，逐漸完成整個(gè)排序。

插入排序有兩種寫(xiě)法：

交換法：在新數(shù)字插入過(guò)程中，不斷與前面的數(shù)字交換，直到找到自己合適的位置。 移動(dòng)法：在新數(shù)字插入過(guò)程中，與前面的數(shù)字不斷比較，前面的數(shù)字不斷向后挪出位置，當(dāng)新數(shù)字找到自己的位置后，插入一次即可。 交換法插入排序

const sort = (arr) => { for (let i = 1, len = arr.length; i < len; i++) {let j = i;while (j >= 1 && arr[j] < arr[j - 1]) { [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; j--} } return arr;};

當(dāng)數(shù)字少于兩個(gè)時(shí)，不存在排序問(wèn)題，當(dāng)然也不需要插入，所以我們直接從第二個(gè)數(shù)字開(kāi)始往前插入。

移動(dòng)法

我們發(fā)現(xiàn)，在交換法插入排序中，每次都要交換數(shù)字。但實(shí)際上，新插入的這個(gè)數(shù)字并不一定適合與它交換的數(shù)字所在的位置。也就是說(shuō)，它剛換到新的位置上不久，下一次比較后，如果又需要交換，它馬上又會(huì)被換到前一個(gè)數(shù)字的位置。

由此，我們可以想到一種優(yōu)化方案：讓新插入的數(shù)字先進(jìn)行比較，前面比它大的數(shù)字不斷向后移動(dòng)，直到找到適合這個(gè)新數(shù)字的位置后再插入。

這種方案我們需要把新插入的數(shù)字暫存起來(lái)，代碼如下：

const sort = (arr) => { for (let i = 1, len = arr.length; i < len; i++) {let j = i-1;let cur = arr[i];while (j >= 0 && cur < arr[j]) { arr[j+1] = arr[j] j--;}arr[j+1] = cur } return arr;};希爾排序

1959 年 77 月，美國(guó)辛辛那提大學(xué)的數(shù)學(xué)系博士 Donald Shell 在 《ACM 通訊》上發(fā)表了希爾排序算法，成為首批將時(shí)間復(fù)雜度降到O(n2)以下的算法之一。雖然原始的希爾排序最壞時(shí)間復(fù)雜度仍然是O(n2)，但經(jīng)過(guò)優(yōu)化的希爾排序可以達(dá)到O(n1.3)甚至 O(n7/6)。

希爾排序本質(zhì)上是對(duì)插入排序的一種優(yōu)化，它利用了插入排序的簡(jiǎn)單，又克服了插入排序每次只交換相鄰兩個(gè)元素的缺點(diǎn)。它的基本思想是：

將待排序數(shù)組按照一定的間隔分為多個(gè)子數(shù)組，每組分別進(jìn)行插入排序。這里按照間隔分組指的不是取連續(xù)的一段數(shù)組，而是每跳躍一定間隔取一個(gè)值組成一組 逐漸縮小間隔進(jìn)行下一輪排序 最后一輪時(shí)，取間隔為 11，也就相當(dāng)于直接使用插入排序。但這時(shí)經(jīng)過(guò)前面的「宏觀調(diào)控」，數(shù)組已經(jīng)基本有序了，所以此時(shí)的插入排序只需進(jìn)行少量交換便可完成 舉個(gè)例子，對(duì)數(shù)組[8, 3, 34, 6, 4, 1, 44, 45, 43, 2, 23]進(jìn)行希爾排序的過(guò)程如下：

第一遍（5 間隔排序）：按照間隔 5 分割子數(shù)組，共分成五組，分別是[8, 1, 23],[3, 44],[34, 45],[6, 43],[4, 2]。對(duì)它們進(jìn)行插入排序，排序后它們分別變成：[1, 8, 23],[3, 44],[34, 45],[6, 43],[2, 4]，此時(shí)整個(gè)數(shù)組變成 [1, 3, 34, 6, 2, 8, 44, 45, 43, 4, 23]

第二遍（2 間隔排序）：按照間隔 2 分割子數(shù)組，共分成兩組，分別是[1, 34, 2, 44, 43, 23],[3, 6, 8, 45, 4]。對(duì)他們進(jìn)行插入排序，排序后它們分別變成：[1, 2, 23, 34, 43, 44],[3, 4, 6, 8, 45]，此時(shí)整個(gè)數(shù)組變成[1, 3, 2, 4, 23, 6, 34, 8, 43, 45, 44]。這里有一個(gè)非常重要的性質(zhì)：當(dāng)我們完成 2 間隔排序后，這個(gè)數(shù)組仍然是保持 5 間隔有序的。也就是說(shuō)，更小間隔的排序沒(méi)有把上一步的結(jié)果變壞。

第三遍（11 間隔排序，等于直接插入排序）：按照間隔 1 分割子數(shù)組，分成一組，也就是整個(gè)數(shù)組。對(duì)其進(jìn)行插入排序，經(jīng)過(guò)前兩遍排序，數(shù)組已經(jīng)基本有序了，所以這一步只需經(jīng)過(guò)少量交換即可完成排序。排序后數(shù)組變成[1, 2, 3, 4, 6, 8, 23, 34, 43, 44, 45]，整個(gè)排序完成。

const sort = arr => { const len = arr.length; if (len < 2) {return arr; } let gap = Math.floor(len / 2); while (gap > 0) {for (let i = gap; i < len; i++) { let j = i; let cur = arr[i]; while (j >= 0 && cur < arr[j - gap]) {arr[j] = arr[j - gap];j -= gap; } arr[j] = cur;}gap = Math.floor(gap / 2); } return arr;}堆排序

堆排序過(guò)程如下：

用數(shù)列構(gòu)建出一個(gè)大頂堆，取出堆頂?shù)臄?shù)字(放到待排序數(shù)組的最后)； 調(diào)整剩余的數(shù)字，構(gòu)建出新的大頂堆，再次取出堆頂?shù)臄?shù)字； 循環(huán)往復(fù)，完成整個(gè)排序。

function sort(arr) { for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length) } for (let j = arr.length - 1; j > 0; j--) {[arr[0], arr[j]] = [arr[j], arr[0]]adjustHeap(arr, 0, j) }}function adjustHeap(arr, i, length) { let tmp = arr[i] for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {if (k + 1 < length && arr[k] < arr[k + 1]) { k++;}if (arr[k] > tmp) { arr[i] = arr[k]; i = k;} else { break;}arr[i] = tmp; }}快速排序

快速排序算法由 C. A. R. Hoare 在 1960 年提出。它的時(shí)間復(fù)雜度也是 O(nlogn)，但它在時(shí)間復(fù)雜度為 O(nlogn) 級(jí)的幾種排序算法中，大多數(shù)情況下效率更高，所以快速排序的應(yīng)用非常廣泛。再加上快速排序所采用的分治思想非常實(shí)用，使得快速排序深受面試官的青睞，所以掌握快速排序的思想尤為重要。

快速排序算法的基本思想是：

從數(shù)組中取出一個(gè)數(shù)，稱(chēng)之為基數(shù)（pivot） 遍歷數(shù)組，將比基數(shù)大的數(shù)字放到它的右邊，比基數(shù)小的數(shù)字放到它的左邊。遍歷完成后，數(shù)組被分成了左右兩個(gè)區(qū)域 將左右兩個(gè)區(qū)域視為兩個(gè)數(shù)組，重復(fù)前兩個(gè)步驟，直到排序完成 事實(shí)上，快速排序的每一次遍歷，都將基數(shù)擺到了最終位置上。第一輪遍歷排好 1 個(gè)基數(shù)，第二輪遍歷排好 2 個(gè)基數(shù)（每個(gè)區(qū)域一個(gè)基數(shù)，但如果某個(gè)區(qū)域?yàn)榭眨瑒t此輪只能排好一個(gè)基數(shù)），第三輪遍歷排好 4 個(gè)基數(shù)（同理，最差的情況下，只能排好一個(gè)基數(shù)），以此類(lèi)推。總遍歷次數(shù)為 logn～n 次，每輪遍歷的時(shí)間復(fù)雜度為 O(n)，所以很容易分析出快速排序的時(shí)間復(fù)雜度為 O(nlogn) ～O(n2)，平均時(shí)間復(fù)雜度為 O(nlogn)。

const partition = (arr, start, end) => { let pivot = arr[start]; // 取第一個(gè)數(shù)為基數(shù) let left = start + 1; // 從第二個(gè)數(shù)開(kāi)始分區(qū) let right = end; // 右邊界 // left、right 相遇時(shí)退出循環(huán) while (left < right) {// 找到第一個(gè)大于基數(shù)的位置while (left < right && arr[left] <= pivot) left++;// 交換這兩個(gè)數(shù)，使得左邊分區(qū)都小于或等于基數(shù)，右邊分區(qū)大于或等于基數(shù)if (left != right) { [arr[left], arr[right]] = [arr[right], arr[left]]; right--;} } // 如果 left 和 right 相等，單獨(dú)比較 arr[right] 和 pivot if (left == right && arr[right] > pivot) right--; // 將基數(shù)和中間數(shù)交換 if (right != start) [arr[left], pivot] = [pivot, arr[left]]; // 返回中間值的下標(biāo) return right;}const quickSort = (arr, start, end) => { if (start >= end) return; const middle = partition(arr, start, end) quickSort(arr, start, middle - 1); quickSort(arr, middle + 1, end);}const sort = arr => { quickSort(arr, 0, arr.length -1);}歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為2-路歸并。

算法描述

把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列； 對(duì)這兩個(gè)子序列分別采用歸并排序； 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

const merge = (left, right) => { let result = []; while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) { result.push(left.shift());} else { result.push(right.shift());} } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result;}const sort = (arr) => { let len = arr.length; if (len < 2) {return arr; } const middle = Math.floor(len / 2),left = arr.slice(0, middle),right = arr.slice(middle); return merge(sort(left), sort(right));};總結(jié)

到此這篇關(guān)于JavaScript實(shí)現(xiàn)的七種排序算法的文章就介紹到這了,更多相關(guān)JavaScript排序算法內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！