整個(gè)排序算法分兩部分來(lái)總結(jié)，這篇總結(jié)第一部分一些相對(duì)簡(jiǎn)單和常用的排序算法，包括 冒泡排序 、 選擇排序 、 插入排序 和 希爾排序 。

冒泡排序

冒泡排序應(yīng)該是大家接觸的最早的排序方法了，理解起來(lái)也十分簡(jiǎn)單。冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

算法描述

• 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
• 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
• 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
• 重復(fù)步驟1~3，直到排序完成。

算法分析

最佳情況：T(n) = O(n)? ?最差情況：T(n) = O(n^2)? ?平均情況：T(n) = O(n^2)

            
              #冒泡排序
    def BubbleSort(self, arr):
        if len(arr) == 0:
            return arr
        for i in range(0, len(arr)-1):
            for j in range(0, len(arr)-i-1):
                if arr[j+1] < arr[j]:
                    temp = arr[j+1]
                    arr[j+1] = arr[j]
                    arr[j] = temp
        return arr
            
          

選擇排序

表現(xiàn)最穩(wěn)定的排序算法之一，因?yàn)闊o(wú)論什么數(shù)據(jù)進(jìn)去都是O(n2)的時(shí)間復(fù)雜度，所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講，選擇排序可能也是平時(shí)排序一般人想到的最多的排序方法了吧。

選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

算法分析

最佳情況：T(n) = O(n2)??最差情況：T(n) = O(n^2)??平均情況：T(n) = O(n^2)

            
              #選擇排序
    def SelectionSort(self, arr):
        if len(arr) == 0:
            return arr
        for i in range(0, len(arr)-1):
            min_index = i
            for j in range(i, len(arr)):
                if arr[j] < arr[min_index]:
                    min_index = j
            if min_index == i:
                continue
            else:
                temp = arr[i]
                arr[i] = arr[min_index]
                arr[min_index] = temp
        return arr
            
          

插入排序

插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

算法描述

• 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
• 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
• 如果該元素（已排序）大于新元素，將該元素移到下一位置；
• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
• 將新元素插入到該位置后；
• 重復(fù)步驟2~5。

算法分析

最佳情況：T(n) = O(n)? ?最壞情況：T(n) = O(n^2)? ?平均情況：T(n) = O(n^2)

            
              #插入排序
    def InsertSort(self, arr):
        if len(arr) == 0 or len(arr) == 1:
            return arr
        for i in range(1, len(arr)):
            current = arr[i]
            j = i
            while j > 0 and arr[j-1] > current:
                arr[j] = arr[j-1]
                j -= 1
            arr[j] = current
        return arr
            
          

希爾排序

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序，同時(shí)該算法是沖破O(n2）的第一批算法之一。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。

希爾排序是把記錄按下表的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

算法過(guò)程的理解如下：

算法分析

最佳情況：T(n) = O()??最壞情況：T(n) = O()??平均情況：T(n) =O()

            
              #希爾排序
    def ShellSort(self, arr):
        if len(arr) == 0:
            return arr
        increasement = len(arr)
        while increasement > 1:
            #每次縮小增量
            increasement = increasement // 3 + 1
            for i in range(0, increasement):
                #在每個(gè)子序列中進(jìn)行直接插入排序
                for j in range(i + increasement, len(arr), increasement):
                    #相比于直接插入排序，這里增加一個(gè)比較，由于增量分組大部分都已有序，可降低復(fù)雜度，從而發(fā)揮增量分組的優(yōu)勢(shì)
                    if arr[j] < arr[j - increasement]:
                        current = arr[j]
                        k = j
                        while k > 0 and arr[k - increasement] > current:
                            arr[k] = arr[k - increasement]
                            k -= increasement
                        arr[k] = current
        return arr
            
          

?

?