整個排序算法分兩部分來總結，這篇總結第一部分一些相對簡單和常用的排序算法，包括 冒泡排序 、 選擇排序 、 插入排序 和 希爾排序 。

冒泡排序

冒泡排序應該是大家接觸的最早的排序方法了，理解起來也十分簡單。冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

算法描述

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；
• 針對所有的元素重復以上的步驟，除了最后一個；
• 重復步驟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
            
          

選擇排序

表現最穩定的排序算法之一，因為無論什么數據進去都是O(n2)的時間復雜度，所以用到它的時候，數據規模越小越好。唯一的好處可能就是不占用額外的內存空間了吧。理論上講，選擇排序可能也是平時排序一般人想到的最多的排序方法了吧。

選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

算法分析

最佳情況：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）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

算法描述

• 從第一個元素開始，該元素可以認為已經被排序；
• 取出下一個元素，在已經排序的元素序列中從后向前掃描；
• 如果該元素（已排序）大于新元素，將該元素移到下一位置；
• 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
• 將新元素插入到該位置后；
• 重復步驟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年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。

希爾排序是把記錄按下表的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

算法過程的理解如下：

算法分析

最佳情況：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):
                #在每個子序列中進行直接插入排序
                for j in range(i + increasement, len(arr), increasement):
                    #相比于直接插入排序，這里增加一個比較，由于增量分組大部分都已有序，可降低復雜度，從而發揮增量分組的優勢
                    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
            
          

?

?