前言

1 、排序的概念

排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列昵骤。
排序分為內(nèi)部排序和外部排序。
若整個(gè)排序過程不需要訪問外存便能完成肯适，則稱此類排序問題為內(nèi)部排序变秦。
反之，若參加排序的記錄數(shù)量很大框舔，整個(gè)序列的排序過程不可能在內(nèi)存中完成蹦玫，則稱此類排序問題為外部排序赎婚。

2 、排序分類

八大排序算法均屬于內(nèi)部排序樱溉。如果按照策略來分類挣输，大致可分為：交換排序、插入排序福贞、選擇排序撩嚼、歸并排序和基數(shù)排序。如下圖所示：

3 挖帘、算法分析

下表給出各種排序的基本性能绢馍，具體分析請(qǐng)參看各排序的詳解：

一、插入排序

插入排序分為兩種：直接插入排序和希爾排序

直接插入排序

基本思想：
直接插入排序的核心思想就是：將數(shù)組中的所有元素依次跟前面已經(jīng)排好的元素相比較肠套，如果選擇的元素比已排序的元素小舰涌，則交換，直到全部元素都比較過你稚。
因此瓷耙，從上面的描述中我們可以發(fā)現(xiàn)，直接插入排序可以用兩個(gè)循環(huán)完成：

• 第一層循環(huán)：遍歷待比較的所有數(shù)組元素
• 第二層循環(huán)：將本輪選擇的元素與已經(jīng)排好序的元素相比較刁赖。
  如果：selected > ordered搁痛，那么將二者交換

def insert_sort(array):
    for i in range(len(array)):
        for j in range(i):
            if array[i] < array[j]:
                array.insert(j, array.pop(i))
                break
    return array

希爾排序

基本思想：
將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序，重復(fù)這過程宇弛，不過每次用更長的列（步長更長了鸡典，列數(shù)更少了）來進(jìn)行。最后整個(gè)表就只有一列了枪芒。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法彻况，算法本身還是使用數(shù)組進(jìn)行排序。

希爾排序(Shell Sort)是插入排序的一種舅踪。也稱縮小增量排序纽甘，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法抽碌。該方法因DL．Shell于1959年提出而得名悍赢。 希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序货徙；隨著增量逐漸減少左权，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)痴颊，整個(gè)文件恰被分成一組赏迟，算法便終止。

def shell_sort(alist):
    n = len(alist)
    # 初始步長
    gap = n // 2
    while gap > 0:
        # 按步長進(jìn)行插入排序
        for i in range(gap,n):
            j = i
            # 原地插入排序祷舀，之前的插入排序另辟空間存儲(chǔ)的
            while j>=gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        # 得到新的步長
        gap = gap //2
    return alist

最壞情況O(n^2) 瀑梗，平均O(nlog(n))~O(n^{2)烹笔，最好O(n}1.3) 裳扯，不穩(wěn)定抛丽。

二、選擇排序

選擇排序分為簡(jiǎn)單選擇排序和堆排序

簡(jiǎn)單選擇排序

基本思想：
比較+交換饰豺。

1. 從待排序序列中亿鲜，找到關(guān)鍵字最小的元素；
2. 如果最小元素不是待排序序列的第一個(gè)元素冤吨，將其和第一個(gè)元素互換蒿柳；
3. 從余下的 N - 1 個(gè)元素中，找出關(guān)鍵字最小的元素漩蟆，重復(fù)(1)垒探、(2)步，直到排序結(jié)束怠李。
   因此我們可以發(fā)現(xiàn)圾叼，簡(jiǎn)單選擇排序也是通過兩層循環(huán)實(shí)現(xiàn)。

• 第一層循環(huán)：依次遍歷序列當(dāng)中的每一個(gè)元素
• 第二層循環(huán)：將遍歷得到的當(dāng)前元素依次與余下的元素進(jìn)行比較捺癞，符合最小元素的條件夷蚊，則交換。

def select_sort(array):
    for i in range(len(array)):
        x = i  # min index
        for j in range(i, len(array)):
            if array[j] < array[x]:
                x = j
        array[i], array[x] = array[x], array[i]
    return array

堆排序

基本思想：
堆排序可以按照以下步驟來完成：

1. 首先將序列構(gòu)建成為大頂堆髓介；
   （這樣滿足了大頂堆那條性質(zhì)：位于根節(jié)點(diǎn)的元素一定是當(dāng)前序列的最大值）
2. 取出當(dāng)前大頂堆的根節(jié)點(diǎn)惕鼓，將其與序列末尾元素進(jìn)行交換；
   （此時(shí)：序列末尾的元素為已排序的最大值；由于交換了元素路鹰，當(dāng)前位于根節(jié)點(diǎn)的堆并不一定滿足大頂堆的性質(zhì)）
3. 對(duì)交換后的n-1個(gè)序列元素進(jìn)行調(diào)整凤薛，使其滿足大頂堆的性質(zhì)；
4. 重復(fù)2.3步驟叫胁，直至堆中只有1個(gè)元素為止

堆排序的時(shí)間復(fù)雜度分為兩個(gè)部分一個(gè)是建堆的時(shí)候所耗費(fèi)的時(shí)間，一個(gè)是進(jìn)行堆調(diào)整的時(shí)候所耗費(fèi)的時(shí)間汞幢。而堆排序則是調(diào)用了建堆和堆調(diào)整驼鹅。
建堆是一個(gè)線性過程，從len/2-0一直調(diào)用堆調(diào)整的過程森篷，相當(dāng)于o(h1)+o(h2)+…+o(hlen/2)這里的h表示節(jié)點(diǎn)深度输钩，len/2表示節(jié)點(diǎn)深度，對(duì)于求和過程仲智，結(jié)果為線性的O（n） 堆調(diào)整為一個(gè)遞歸的過程买乃，調(diào)整堆的過程時(shí)間復(fù)雜度與堆的深度有關(guān)系，相當(dāng)于lgn的操作钓辆。 因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O（n）,調(diào)整堆的時(shí)間復(fù)雜度是lgn剪验，所以堆排序的時(shí)間復(fù)雜度是O（nlgn）肴焊。

def heap_sort(array):
    def heap_adjust(parent):
        child = 2 * parent + 1  # left child
        while child < len(heap):
            if child + 1 < len(heap):
                if heap[child + 1] > heap[child]:
                    child += 1  # right child
            if heap[parent] >= heap[child]:
                break
            heap[parent], heap[child] = \
                heap[child], heap[parent]
            parent, child = child, 2 * child + 1
    heap, array = array.copy(), []
    for i in range(len(heap) // 2, -1, -1):
        heap_adjust(i)
    while len(heap) != 0:
        heap[0], heap[-1] = heap[-1], heap[0]
        array.insert(0, heap.pop())
        heap_adjust(0)
    return array

三、歸并排序

基本思想：
歸并排序是建立在歸并操作上的一種有效的排序算法功戚，該算法是采用分治法的一個(gè)典型的應(yīng)用娶眷。它的基本操作是：將已有的子序列合并，達(dá)到完全有序的序列啸臀；即先使每個(gè)子序列有序届宠，再使子序列段間有序。
歸并排序其實(shí)要做兩件事：

分解----將序列每次折半拆分

合并----將劃分后的序列段兩兩排序合并
因此乘粒，歸并排序?qū)嶋H上就是兩個(gè)操作豌注，拆分+合并

合并:
L[first...mid]為第一段，L[mid+1...last]為第二段灯萍，并且兩端已經(jīng)有序轧铁，現(xiàn)在我們要將兩端合成達(dá)到L[first...last]并且也有序。

首先依次從第一段與第二段中取出元素比較旦棉，將較小的元素賦值給temp[]
重復(fù)執(zhí)行上一步齿风，當(dāng)某一段賦值結(jié)束，則將另一段剩下的元素賦值給temp[]
此時(shí)將temp[]中的元素復(fù)制給L[]他爸，則得到的L[first...last]有序

分解:
在這里聂宾，我們采用遞歸的方法，首先將待排序列分成A,B兩組诊笤；然后重復(fù)對(duì)A系谐、B序列
分組；直到分組后組內(nèi)只有一個(gè)元素讨跟，此時(shí)我們認(rèn)為組內(nèi)所有元素有序纪他，則分組結(jié)束。

def merge_sort(nums):  # 變成二次樹
    if len(nums) == 1:
        return nums
    mid = len(nums) // 2
    left = nums[:mid]
    right = nums[mid:]
    a = merge_sort(left)
    b = merge_sort(right)
    return merge(a, b)
def merge(left, right):  # 整合排序
    c = []
    j = k = 0
    while len(left) > j and len(right) > k:
        if left[j] <= right[k]:
            c.append(left[j])
            j += 1
        else:
            c.append(right[k])
            k += 1
    if j == len(left):
        for i in right[k:]:
            c.append(i)
    else:
        for i in left[j:]:
            c.append(i)
    return c

四晾匠、基數(shù)排序

基本思想：
通過序列中各個(gè)元素的值茶袒，對(duì)排序的N個(gè)元素進(jìn)行若干趟的“分配”與“收集”來實(shí)現(xiàn)排序。

分配：我們將L[i]中的元素取出凉馆，首先確定其個(gè)位上的數(shù)字薪寓，根據(jù)該數(shù)字分配到與之序號(hào)相同的桶中

收集：當(dāng)序列中所有的元素都分配到對(duì)應(yīng)的桶中，再按照順序依次將桶中的元素收集形成新的一個(gè)待排序列L[ ]
對(duì)新形成的序列L[]重復(fù)執(zhí)行分配和收集元素中的十位澜共、百位...直到分配完該序列中的最高位向叉，則排序結(jié)束
根據(jù)上述“基數(shù)排序”的展示，我們可以清楚的看到整個(gè)實(shí)現(xiàn)的過程

def radix_sort(array):
    bucket, digit = [[]], 0
    while len(bucket[0]) != len(array):
        bucket = [[], [], [], [], [], [], [], [], [], []]
        for i in range(len(array)):
            num = (array[i] // 10 ** digit) % 10
            bucket[num].append(array[i])
        array.clear()
        for i in range(len(bucket)):
            array += bucket[i]
        digit += 1
    return array

五嗦董、交換排序

交換排序分為兩種：冒泡排序和快速排序

冒泡排序

基本思想：

• 將序列當(dāng)中的左右元素母谎，依次比較，保證右邊的元素始終大于左邊的元素京革；
  （ 第一輪結(jié)束后奇唤，序列最后一個(gè)元素一定是當(dāng)前序列的最大值幸斥；）
• 對(duì)序列當(dāng)中剩下的n-1個(gè)元素再次執(zhí)行步驟1。
• 對(duì)于長度為n的序列咬扇，一共需要執(zhí)行n-1輪比較
  （利用while循環(huán)可以減少執(zhí)行次數(shù)）

def bubble_sort(array):
    for i in range(len(array)):
        for j in range(i, len(array)):
            if array[i] > array[j]:
                array[i], array[j] = array[j], array[i]
    return array

快速排序

基本思想：挖坑填數(shù)+分治法

從序列當(dāng)中選擇一個(gè)基準(zhǔn)數(shù)(pivot)
在這里我們選擇序列當(dāng)中第一個(gè)數(shù)最為基準(zhǔn)數(shù)
將序列當(dāng)中的所有數(shù)依次遍歷甲葬，比基準(zhǔn)數(shù)大的位于其右側(cè)，比基準(zhǔn)數(shù)小的位于其左側(cè)
重復(fù)步驟1.2冗栗，直到所有子集當(dāng)中只有一個(gè)元素為止演顾。
用偽代碼描述如下：
1．i =L; j = R; 將基準(zhǔn)數(shù)挖出形成第一個(gè)坑a[i]供搀。
2．j--由后向前找比它小的數(shù)隅居，找到后挖出此數(shù)填前一個(gè)坑a[i]中。
3．i++由前向后找比它大的數(shù)葛虐，找到后也挖出此數(shù)填到前一個(gè)坑a[j]中胎源。
4．再重復(fù)執(zhí)行2，3二步屿脐，直到i==j涕蚤，將基準(zhǔn)數(shù)填入a[i]中

def quick_sort(array):
    sys.setrecursionlimit(10 ** 8)
    def recursive(begin, end):
        if begin > end:
            return
        l, r = begin, end
        pivot = array[l]
        while l < r:
            while l < r and array[r] > pivot:
                r -= 1
            while l < r and array[l] <= pivot:
                l += 1
            array[l], array[r] = array[r], array[l]
        array[l], array[begin] = pivot, array[l]
        recursive(begin, l - 1)
        recursive(r + 1, end)

    recursive(0, len(array) - 1)
    return array

六、總結(jié)

• (1)若n較小(如n≤50)的诵，可采用直接插入或直接選擇排序万栅。
  　當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好西疤；否則如果直接選擇移動(dòng)的記錄數(shù)少于直接插人烦粒，應(yīng)選直接選擇排序?yàn)橐恕?/li>
• (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插入代赁、冒泡或隨機(jī)的快速排序?yàn)橐耍?/li>
• (3)若n較大扰她，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序芭碍。
  　快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法徒役，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短窖壕；
  　堆排序所需的輔助空間少于快速排序忧勿，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的瞻讽。
  　若要求排序穩(wěn)定鸳吸，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的排序算法并不值得提倡卸夕，通巢闶停可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件快集，然后再兩兩歸并之贡羔。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的廉白，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。

七乖寒、參考文獻(xiàn)

[1] 李春葆． 數(shù)據(jù)結(jié)構(gòu)教程[M]．北京市：清華大學(xué)出版社猴蹂，2013．

[2] li563868273．各種排序的比較和使用場(chǎng)景分析．CSDN，2016.

[3] LeeLom． 數(shù)據(jù)結(jié)構(gòu)常見的八大排序算法．簡(jiǎn)書楣嘁，2016．

[4] woider． Python 八大排序算法速度比較．博客園磅轻，2016．