https://www.zhouwenzhen.top/archives/108/

作者 | hustcc

來源 | https://github.com/hustcc/JS-Sorting-Algorithm

排序算法是《數(shù)據(jù)結構與算法》中最基本的算法之一髓涯。

排序算法可以分為內(nèi)部排序和外部排序瓤荔，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序崔挖、選擇排序、冒泡排序庵寞、歸并排序狸相、快速排序、堆排序捐川、基數(shù)排序等脓鹃。用一張圖概括：

算法復雜度

關于時間復雜度：

1. 平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序古沥。
2. 線性對數(shù)階 (O(nlog2n)) 排序 快速排序瘸右、堆排序和歸并排序；
3. O(n1+§)) 排序岩齿，§ 是介于 0 和 1 之間的常數(shù)太颤。希爾排序
4. 線性階 (O(n)) 排序 基數(shù)排序，此外還有桶纯衍、箱排序栋齿。

關于穩(wěn)定性：

• 排序后 2 個相等鍵值的順序和排序之前它們的順序相同
• 穩(wěn)定的排序算法：冒泡排序、插入排序襟诸、歸并排序和基數(shù)排序瓦堵。
• 不是穩(wěn)定的排序算法：選擇排序、快速排序歌亲、希爾排序菇用、堆排序。

名詞解釋：

n：數(shù)據(jù)規(guī)模

k：“桶”的個數(shù)

In-place：占用常數(shù)內(nèi)存陷揪，不占用額外內(nèi)存

Out-place：占用額外內(nèi)存

1惋鸥、冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復地走訪過要排序的數(shù)列悍缠，一次比較兩個元素卦绣，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換飞蚓，也就是說該數(shù)列已經(jīng)排序完成滤港。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

作為最簡單的排序算法之一趴拧，冒泡排序給我的感覺就像 Abandon 在單詞書里出現(xiàn)的感覺一樣溅漾，每次都在第一頁第一位山叮，所以最熟悉。冒泡排序還有一種優(yōu)化算法添履，就是立一個 flag屁倔，當在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序暮胧。但這種改進對于提升性能來說并沒有什么太大作用锐借。

（1）算法步驟

1. 比較相鄰的元素。如果第一個比第二個大叔壤，就交換他們兩個瞎饲。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對炼绘。這步做完后，最后的元素會是最大的數(shù)妄田。
3. 針對所有的元素重復以上的步驟俺亮，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復上面的步驟疟呐，直到?jīng)]有任何一對數(shù)字需要比較脚曾。

（2）動圖演示

冒泡排序

（3）Python 代碼

def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2、選擇排序

選擇排序是一種簡單直觀的排序算法启具，無論什么數(shù)據(jù)進去都是 O(n2) 的時間復雜度本讥。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好鲁冯。唯一的好處可能就是不占用額外的內(nèi)存空間了吧拷沸。

（1）算法步驟

1. 首先在未排序序列中找到最小（大）元素薯演，存放到排序序列的起始位置
2. 再從剩余未排序元素中繼續(xù)尋找最凶采帧（大）元素，然后放到已排序序列的末尾跨扮。
3. 重復第二步序无，直到所有元素均排序完畢。

（2）動圖演示

選擇排序

（3）Python 代碼

def selectionSort(nums):
    for i in range(len(nums) - 1):  # 遍歷 len(nums)-1 次
        minIndex = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[minIndex]:  # 更新最小值索引
                minIndex = j  
        nums[i], nums[minIndex] = nums[minIndex], nums[i] # 把最小數(shù)交換到前面
    return nums

3衡创、插入排序

插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴帝嗡，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂璃氢。插入排序是一種最簡單直觀的排序算法哟玷，它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)拔莱，在已排序序列中從后向前掃描碗降，找到相應位置并插入隘竭。

插入排序和冒泡排序一樣，也有一種優(yōu)化算法讼渊，叫做拆半插入动看。

（1）算法步驟

1. 將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列爪幻。
2. 從頭到尾依次掃描未排序序列菱皆，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等挨稿，則將待插入元素插入到相等元素的后面仇轻。）

（2）動圖演示

插入排序

（3）Python 代碼

def insertionSort(nums):
    for i in range(len(nums) - 1):  # 遍歷 len(nums)-1 次
        curNum, preIndex = nums[i+1], i  # curNum 保存當前待插入的數(shù)
        while preIndex >= 0 and curNum < nums[preIndex]: # 將比 curNum 大的元素向后移動
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex + 1] = curNum  # 待插入的數(shù)的正確位置   
    return nums

4、希爾排序

希爾排序奶甘，也稱遞減增量排序算法篷店，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法臭家。

希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時疲陕，效率高，即可以達到線性排序的效率钉赁；
• 但插入排序一般來說是低效的蹄殃，因為插入排序每次只能將數(shù)據(jù)移動一位；

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序你踩，待整個序列中的記錄“基本有序”時诅岩，再對全體記錄進行依次直接插入排序。

（1）算法步驟

1. 選擇一個增量序列 t1带膜，t2吩谦，……，tk钱慢，其中 ti > tj, tk = 1逮京；
2. 按增量序列個數(shù) k，對序列進行 k 趟排序；
3. 每趟排序，根據(jù)對應的增量 ti蚕键，將待排序列分割成若干長度為 m 的子序列轨域，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

（2）動圖演示

希爾排序

（3）Python 代碼

def shellSort(nums):
    lens = len(nums)
    gap = 1  
    while gap < lens // 3:
        gap = gap * 3 + 1  # 動態(tài)定義間隔序列
    while gap > 0:
        for i in range(gap, lens):
            curNum, preIndex = nums[i], i - gap  # curNum 保存當前待插入的數(shù)
            while preIndex >= 0 and curNum < nums[preIndex]:
                nums[preIndex + gap] = nums[preIndex] # 將比 curNum 大的元素向后移動
                preIndex -= gap
            nums[preIndex + gap] = curNum  # 待插入的數(shù)的正確位置
        gap //= 3  # 下一個動態(tài)間隔
    return nums

5妻导、歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。

作為一種典型的分而治之思想的算法應用倔韭，歸并排序的實現(xiàn)由兩種方法：

• 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫术浪，所以就有了第 2 種方法）
• 自下而上的迭代

和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響寿酌，但表現(xiàn)比選擇排序好的多胰苏，因為始終都是 O(nlogn) 的時間復雜度。代價是需要額外的內(nèi)存空間醇疼。

（1）算法步驟

1. 申請空間硕并，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列秧荆；
2. 設定兩個指針倔毙，最初位置分別為兩個已經(jīng)排序序列的起始位置；
3. 比較兩個指針所指向的元素乙濒，選擇相對小的元素放入到合并空間陕赃，并移動指針到下一位置；
4. 重復步驟 3 直到某一指針達到序列尾颁股；
5. 將另一序列剩下的所有元素直接復制到合并序列尾凯正。

（2）動圖演示

歸并排序

（3）Python 代碼

def mergeSort(nums):
    # 歸并過程
    def merge(left, right):
        result = []  # 保存歸并后的結果
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾
        return result
    # 遞歸過程
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

6豌蟋、快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法梧疲。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較宇智，但這種狀況并不常見。事實上机蔗，快速排序通常明顯比其他 Ο(nlogn) 算法更快萝嘁，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現(xiàn)出來酸钦。

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應用拔恰。本質(zhì)上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡單粗暴咸这，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高州丹！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時間復雜度達到了 O(n2)，但是人家就是優(yōu)秀醉箕，在大多數(shù)情況下都比平均時間復雜度為 O(n logn) 的排序算法表現(xiàn)要更好放棒，可是這是為什么呢，我也不知道。好在我的強迫癥又犯了摩泪，查了 N 多資料終于在《算法藝術與信息學競賽》上找到了滿意的答案：

快速排序的最壞運行情況是 O(n2)，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)熊楼，且 O(nlogn) 記號中隱含的常數(shù)因子很小悲雳，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以晴楔，對絕大多數(shù)順序性較弱的隨機數(shù)列而言凑队，快速排序總是優(yōu)于歸并排序。

（1）算法步驟

1. 從數(shù)列中挑出一個元素，稱為 “基準”（pivot）;
2. 重新排序數(shù)列做修，所有元素比基準值小的擺放在基準前面康震，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）瘫镇。在這個分區(qū)退出之后鹦付，該基準就處于數(shù)列的中間位置郎嫁。這個稱為分區(qū)（partition）操作辑鲤；
3. 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序弛随；

遞歸的最底部情形决左，是數(shù)列的大小是零或一链烈，也就是永遠都已經(jīng)被排序好了漩勤。雖然一直遞歸下去，但是這個算法總會退出越败，因為在每次的迭代（iteration）中触幼，它至少會把一個元素擺到它最后的位置去。

（2）動圖演示

快速排序

（3）Python 代碼

def quickSort(nums):  # 這種寫法的平均空間復雜度為 O(nlogn)
    if len(nums) <= 1:
        return nums
    pivot = nums[0]  # 基準值
    left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot] 
    right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
    return quickSort(left) + [pivot] + quickSort(right)

'''
@param nums: 待排序數(shù)組
@param left: 數(shù)組上界
@param right: 數(shù)組下界
'''
def quickSort2(nums, left, right):  # 這種寫法的平均空間復雜度為 O(logn) 
    # 分區(qū)操作
    def partition(nums, left, right):
        pivot = nums[left]  # 基準值
        while left < right:
            while left < right and nums[right] >= pivot:
                right -= 1
            nums[left] = nums[right]  # 比基準小的交換到前面
            while left < right and nums[left] <= pivot:
                left += 1
            nums[right] = nums[left]  # 比基準大交換到后面
        nums[left] = pivot # 基準值的正確位置究飞，也可以為 nums[right] = pivot
        return left  # 返回基準值的索引置谦，也可以為 return right
    # 遞歸操作
    if left < right:
        pivotIndex = partition(nums, left, right)
        quickSort2(nums, left, pivotIndex - 1)  # 左序列
        quickSort2(nums, pivotIndex + 1, right) # 右序列
    return nums

7、堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結構所設計的一種排序算法亿傅。堆積是一個近似完全二叉樹的結構媒峡，并同時滿足堆積的性質(zhì)：即子結點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序葵擎。分為兩種方法：

1. 大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值谅阿，在堆排序算法中用于升序排列；
2. 小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值酬滤，在堆排序算法中用于降序排列签餐；

堆排序的平均時間復雜度為 Ο(nlogn)。

（1）算法步驟

1. 創(chuàng)建一個堆 H[0……n-1]盯串；
2. 把堆首（最大值）和堆尾互換氯檐；
3. 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)体捏，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應位置男摧；
4. 重復步驟 2，直到堆的尺寸為 1译打。

（2）動圖演示

堆排序

（3）Python 代碼

# 大根堆（從小打大排列）
def heapSort(nums):
    # 調(diào)整堆
    def adjustHeap(nums, i, size):
        # 非葉子結點的左右兩個孩子
        lchild = 2 * i + 1
        rchild = 2 * i + 2
        # 在當前結點、左孩子拇颅、右孩子中找到最大元素的索引
        largest = i 
        if lchild < size and nums[lchild] > nums[largest]: 
            largest = lchild 
        if rchild < size and nums[rchild] > nums[largest]: 
            largest = rchild 
        # 如果最大元素的索引不是當前結點奏司，把大的結點交換到上面，繼續(xù)調(diào)整堆
        if largest != i: 
            nums[largest], nums[i] = nums[i], nums[largest] 
            # 第 2 個參數(shù)傳入 largest 的索引是交換前大數(shù)字對應的索引
            # 交換后該索引對應的是小數(shù)字樟插，應該把該小數(shù)字向下調(diào)整
            adjustHeap(nums, largest, size)
    # 建立堆
    def builtHeap(nums, size):
        for i in range(len(nums)//2)[::-1]: # 從倒數(shù)第一個非葉子結點開始建立大根堆
            adjustHeap(nums, i, size) # 對所有非葉子結點進行堆的調(diào)整
        # print(nums)  # 第一次建立好的大根堆
    # 堆排序 
    size = len(nums)
    builtHeap(nums, size) 
    for i in range(len(nums))[::-1]: 
        # 每次根結點都是最大的數(shù)韵洋，最大數(shù)放到后面
        nums[0], nums[i] = nums[i], nums[0] 
        # 交換完后還需要繼續(xù)調(diào)整堆竿刁，只需調(diào)整根節(jié)點，此時數(shù)組的 size 不包括已經(jīng)排序好的數(shù)
        adjustHeap(nums, 0, i) 
    return nums  # 由于每次大的都會放到后面搪缨，因此最后的 nums 是從小到大排列

8食拜、計數(shù)排序

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復雜度的排序副编，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)负甸。

（1）動圖演示

計數(shù)排序

（2）Python 代碼

def countingSort(nums):
    bucket = [0] * (max(nums) + 1) # 桶的個數(shù)
    for num in nums:  # 將元素值作為鍵值存儲在桶中，記錄其出現(xiàn)的次數(shù)
        bucket[num] += 1
    i = 0  # nums 的索引
    for j in range(len(bucket)):
        while bucket[j] > 0:
            nums[i] = j
            bucket[j] -= 1
            i += 1
    return nums

9痹届、桶排序

桶排序是計數(shù)排序的升級版呻待。它利用了函數(shù)的映射關系，高效與否的關鍵就在于這個映射函數(shù)的確定队腐。為了使桶排序更加高效蚕捉，我們需要做到這兩點：

1. 在額外空間充足的情況下，盡量增大桶的數(shù)量
2. 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中

同時柴淘，對于桶中元素的排序迫淹，選擇何種比較排序算法對于性能的影響至關重要。

什么時候最快

當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中为严。

什么時候最慢

當輸入的數(shù)據(jù)被分配到了同一個桶中敛熬。

Python 代碼

def bucketSort(nums, defaultBucketSize = 5):
    maxVal, minVal = max(nums), min(nums)
    bucketSize = defaultBucketSize  # 如果沒有指定桶的大小，則默認為5
    bucketCount = (maxVal - minVal) // bucketSize + 1  # 數(shù)據(jù)分為 bucketCount 組
    buckets = []  # 二維桶
    for i in range(bucketCount):
        buckets.append([])
    # 利用函數(shù)映射將各個數(shù)據(jù)放入對應的桶中
    for num in nums:
        buckets[(num - minVal) // bucketSize].append(num)
    nums.clear()  # 清空 nums
    # 對每一個二維桶中的元素進行排序
    for bucket in buckets:
        insertionSort(bucket)  # 假設使用插入排序
        nums.extend(bucket)    # 將排序好的桶依次放入到 nums 中
    return nums

桶排序

10梗脾、基數(shù)排序

基數(shù)排序是一種非比較型整數(shù)排序算法荸型，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較炸茧。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)瑞妇，所以基數(shù)排序也不是只能使用于整數(shù)。

基數(shù)排序有兩種方法：

1. MSD （主位優(yōu)先法）：從高位開始進行排序
2. LSD （次位優(yōu)先法）：從低位開始進行排序

動圖演示

基數(shù)排序

Python 代碼

# LSD Radix Sort
def radixSort(nums):
    mod = 10
    div = 1
    mostBit = len(str(max(nums)))  # 最大數(shù)的位數(shù)決定了外循環(huán)多少次
    buckets = [[] for row in range(mod)] # 構造 mod 個空桶
    while mostBit:
        for num in nums:  # 將數(shù)據(jù)放入對應的桶中
            buckets[num // div % mod].append(num)
        i = 0  # nums 的索引
        for bucket in buckets:  # 將數(shù)據(jù)收集起來
            while bucket:
                nums[i] = bucket.pop(0) # 依次取出
                i += 1
        div *= 10
        mostBit -= 1
    return nums