# 排序算法整理

排序在編程中經(jīng)常有使用，尤其是面對數(shù)據(jù)分析和數(shù)據(jù)整理的時(shí)候，我們更加需要一種合適情景的排序方式來滿足我們的需求，之前有對排序進(jìn)行一些學(xué)習(xí)和了解，但是一直沒有做系統(tǒng)性的整理和記錄，導(dǎo)致很多時(shí)候需要重新查詢資料理解，借著這個空閑時(shí)間對常見的排序算法進(jìn)行整理加以自己的理解，希望自己以后看到能快速回憶并能在工作中使用到這些思想。

## 冒泡排序（Bubble Sort）

這應(yīng)該是我們最常見的排序算法之一，接觸數(shù)據(jù)結(jié)構(gòu)與算法里面也是以這個引入的排序內(nèi)容，其核心思想是將需要排序的數(shù)據(jù)像氣泡由水底到水面浮上一般，每次選定一個數(shù)據(jù)與未完成排序的數(shù)據(jù)進(jìn)行對比，滿足排序需求則進(jìn)行位置互換（氣泡上浮的過程），這樣子保證了每次能讓滿足需求（最大或者最小的數(shù)據(jù)）的數(shù)據(jù)浮動至最后的位置，當(dāng)排序的數(shù)據(jù)全部經(jīng)過這樣子的操作后自然已經(jīng)排序完畢的。

**需要兩層循環(huán)分別控制浮動的氣泡數(shù)和比較的未排序數(shù)的選定**

## 選擇排序（Selection Sort）

選擇排序與前面提到的冒泡排序有相似的地方，也是單次取得最大或者最小的數(shù)據(jù)，但是選擇排序并沒有頻繁的進(jìn)行數(shù)據(jù)交換，而是通過記錄需要的數(shù)據(jù)（最大的或者最小的）的下標(biāo)，最后與已經(jīng)排序好的區(qū)域的數(shù)據(jù)進(jìn)行比對，完成正確的位置的選擇。

**也需要兩層循環(huán)，性能十分穩(wěn)定，適用于數(shù)據(jù)規(guī)模小的排序**

## 插入排序（Insertion Sort）

插入排序的整體思想在我的理解是“先排后序”，既不需要先按整體數(shù)據(jù)的大小順序得到數(shù)據(jù)，而是先只將需要排序的數(shù)據(jù)按大小進(jìn)行排列。首先默認(rèn)第一個數(shù)據(jù)是有序的，然后取下一個數(shù)據(jù)，從有序的數(shù)據(jù)隊(duì)伍的最后開始往前比對，如果滿足小于則插入該數(shù)據(jù)的前面，其他數(shù)據(jù)順次后移，直到未排序數(shù)據(jù)取完并排序完，此時(shí)完成排序。

**需要多次進(jìn)行賦值操作完成數(shù)據(jù)后移**

## 希爾排序（Shell Sort）

通過設(shè)置增量來將數(shù)據(jù)劃分為幾個組，然后組內(nèi)進(jìn)行數(shù)據(jù)對比，完成一次后改變增量并完成組內(nèi)排序的流程，最后既可完成整個排序。

**在插入排序的基礎(chǔ)上通過設(shè)定間隔形成**

## 歸并排序（Merge Sort）

歸并排序的主要思想是分而治之，通常是采取對排序模塊進(jìn)行細(xì)分，然后將細(xì)分部分先進(jìn)行排序，排序完成后再將兩個部分按順序比較并組合（遞歸方法循環(huán)處理），這種排序方式在數(shù)據(jù)較多的時(shí)候性能依舊能保持穩(wěn)定。

**性能穩(wěn)定，但是需要額外的內(nèi)存空間存儲數(shù)據(jù)**

## 快速排序（Quick Sort）

這種排序方式是通過選定一個基準(zhǔn)元素，然后讀取數(shù)據(jù)剩余全部元素，將大于基準(zhǔn)的數(shù)據(jù)和小于基準(zhǔn)的數(shù)據(jù)分別置于基準(zhǔn)的前面或者后面（將二者分離），完成后基準(zhǔn)將處于兩堆數(shù)據(jù)的中間，如此循環(huán)往復(fù)（遞歸操作），最后將數(shù)據(jù)完成排序。

**通過基準(zhǔn)元素對數(shù)據(jù)進(jìn)行分類處理**

## 堆排序（Heap Sort）

堆排序利用到了數(shù)據(jù)結(jié)構(gòu)中的完全二叉樹的思想形式，堆中的所有子樹滿足父節(jié)點(diǎn)大于左右子節(jié)點(diǎn)，首先得到一個未排序的數(shù)據(jù)，按照順序組成一棵完全二叉樹，然后按照從最后一顆子樹到最頂上的子樹的順序去構(gòu)建堆（建立堆的過程中更改堆內(nèi)子樹結(jié)構(gòu)后需要對其原來兩個節(jié)點(diǎn)的子樹進(jìn)行再一次調(diào)整），在完成建立堆后，我們便可以開始堆排序，原則是將定點(diǎn)節(jié)點(diǎn)和最后一個節(jié)點(diǎn)進(jìn)行交換代表排序完成（因?yàn)槎褧M足頂點(diǎn)節(jié)點(diǎn)是最大的），在完成交換后，我們需要對頂點(diǎn)節(jié)點(diǎn)重新進(jìn)行堆的構(gòu)建規(guī)則，以此循環(huán)操作，最后得到一個有序的數(shù)據(jù)。

**需要利用到完全二叉樹和堆的數(shù)據(jù)概念，通過堆挑選出最大的數(shù)據(jù)來作為排序依據(jù)**

## 計(jì)數(shù)排序（Counting Sort）

計(jì)數(shù)排序方式是一種典型的以空間換取時(shí)間的操作方式，首先得到數(shù)組內(nèi)的最大值和最小值，建立一個以二者為下標(biāo)邊界的數(shù)組，通過遍歷未排序的數(shù)據(jù)，在遍歷過程中同時(shí)統(tǒng)計(jì)不同的數(shù)據(jù)與下標(biāo)數(shù)值相同的有多少，最后讀取統(tǒng)計(jì)好的數(shù)組的值，有多少值便打印多少個下標(biāo)相同的數(shù)據(jù)，以此達(dá)到排序的目的。

**當(dāng)數(shù)據(jù)規(guī)模較大且數(shù)據(jù)范圍跨度不大的時(shí)候計(jì)數(shù)排序是一種穩(wěn)定且實(shí)用的方式**

## 桶排序（Bucket Sort）

桶排序是計(jì)數(shù)排序的升級版本，其排序性能主要取決于桶的劃分方式，劃分區(qū)間太小則造成空間需求多排序時(shí)間減少，劃分區(qū)間太多則造成排序耗時(shí)變多。

其流程是首先劃分好桶的分類區(qū)間，然后將數(shù)據(jù)依據(jù)標(biāo)準(zhǔn)投入到不同的桶中，然后對非空的桶內(nèi)數(shù)據(jù)進(jìn)行排序，最后將非空的桶按照之前的劃分標(biāo)準(zhǔn)再進(jìn)行拼接。

**算法優(yōu)劣在于對桶的分區(qū)設(shè)置，是計(jì)數(shù)排序的一種分而治之的形式**

## 基數(shù)排序（Radix Sort）

基數(shù)排序結(jié)合了計(jì)數(shù)排序，首先取得未排序數(shù)據(jù)中最大的數(shù)據(jù)，得到該數(shù)據(jù)的位數(shù)，然后按照位數(shù)形成劃分空間（從個位、十位、百位......），然后將數(shù)據(jù)進(jìn)行劃分，劃分的空間內(nèi)利用計(jì)數(shù)排序適用于小范圍數(shù)據(jù)區(qū)間的特點(diǎn)進(jìn)行排序，最后將排序好的不同區(qū)間的數(shù)據(jù)組合，然后選擇下一個劃分空間的依據(jù)，重復(fù)上面的步驟，最后達(dá)到排序的目的。

**基數(shù)排序是計(jì)數(shù)排序更加精細(xì)的一種策略，避開了計(jì)數(shù)排序?qū)τ诳臻g申請的不確定性**