[[426795]]

本文轉(zhuǎn)載自微信公眾號「JS每日一題」，作者灰灰  。轉(zhuǎn)載本文請聯(lián)系JS每日一題公眾號。

一、是什么

排序是程序開發(fā)中非常常見的操作，對一組任意的數(shù)據(jù)元素經(jīng)過排序操作后，就可以把他們變成一組一定規(guī)則排序的有序序列

排序算法屬于算法中的一種，而且是覆蓋范圍極小的一種，徹底掌握排序算法對程序開發(fā)是有很大的幫助的

對于排序算法的好壞衡量，主要是從時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性

時間復(fù)雜度、空間復(fù)雜度前面已經(jīng)講過，這里主要看看穩(wěn)定性的定義

穩(wěn)定性指的是假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變

即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，則稱這種排序算法是穩(wěn)定的;否則稱為不穩(wěn)定的

二、有哪些

常見的算法排序算法有：

• 冒泡排序
• 選擇排序
• 插入排序
• 歸并排序
• 快速排序

冒泡排序

一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來

思路如下：

• 比較相鄰的元素，如果第一個比第二個大，就交換它們兩個
• 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)
• 針對所有的元素重復(fù)以上的步驟，除了最后一個
• 重復(fù)上述步驟，直到?jīng)]有任何一堆數(shù)字需要比較

選擇排序

選擇排序是一種簡單直觀的排序算法，它也是一種交換排序算法

無論什么數(shù)據(jù)進(jìn)去都是 O(n2)的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好

唯一的好處是不占用額外的內(nèi)存存儲空間

思路如下：

在未排序序列中找到最小(大)元素，存放到排序序列的起始位置

從剩余未排序元素中繼續(xù)尋找最小(大)元素，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢

插入排序

插入排序是一種簡單直觀的排序算法

它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入

解決思路如下：

• 把待排序的數(shù)組分成已排序和未排序兩部分，初始的時候把第一個元素認(rèn)為是已排好序的
• 從第二個元素開始，在已排好序的子數(shù)組中尋找到該元素合適的位置并插入該位置(如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。)
• 重復(fù)上述過程直到最后一個元素被插入有序子數(shù)組中

歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法

該算法是采用分治法的一個非常典型的應(yīng)用

將已有序的子序列合并，得到完全有序的序列，即先使每個子序列有序，再使子序列段間有序

解決思路如下：

• 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
• 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
• 比較兩個指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置
• 重復(fù)步驟3直到某一指針到達(dá)序列尾
• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

快速排序

快速排序是對冒泡排序算法的一種改進(jìn)，基本思想是通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)比另一部分的所有數(shù)據(jù)要小

再按這種方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，使整個數(shù)據(jù)變成有序序列

解決思路如下：

• 從數(shù)列中挑出一個元素，稱為"基準(zhǔn)"(pivot)
• 重新排序數(shù)列，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面(相同的數(shù)可以到任何一邊)。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)(partition)操作
• 遞歸地(recursively)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

三、區(qū)別

除了上述的排序算法之外，還存在其他的排序算法，例如希爾排序、堆排序等等......

區(qū)別如下圖所示：

參考文獻(xiàn)

• https://www.runoob.com/w3cnote/bubble-sort.html
• http://www.x-lab.info/post/sort-algorithm/
• https://zhuanlan.zhihu.com/p/42586566