劍指offer已經(jīng)刷完一遍了，今天開始學(xué)習(xí)整理一下排序算法。爭取每天整理兩個。
參考博客：http://www.cnblogs.com/feixuelove1009/p/6143539.html

2018.10.19

一、排序的概念和分類

1、排序的穩(wěn)定性：

經(jīng)過某種排序后，如果兩個記錄序號同等，且兩者在原無序記錄中的先后秩序依然保持不變，則稱所使用的排序方法是穩(wěn)定的，反之是不穩(wěn)定的。
舉個例子，要排序的內(nèi)容是一組原本按照價格高低排序的對象，如今需要按照銷量高低排序，使用穩(wěn)定性算法，可以使得想同銷量的對象依舊保持著價格高低的排序展現(xiàn)，只有銷量不同的才會重新排序。

image.png

該圖有個錯的地方，簡單選擇排序是不穩(wěn)定的算法。

2、內(nèi)排序和外排序：

內(nèi)排序：排序過程中，待排序的所有記錄全部放在內(nèi)存中
外排序：排序過程中，使用到了外部存儲。
通常討論的都是內(nèi)排序。

3、影響內(nèi)排序算法性能的三個因素：

時間復(fù)雜度：即時間性能，高效率的排序算法應(yīng)該是具有盡可能少的關(guān)鍵字比較次數(shù)和記錄的移動次數(shù)
空間復(fù)雜度：主要是執(zhí)行算法所需要的輔助空間，越少越好。
算法復(fù)雜性：主要是指代碼的復(fù)雜性。

二、冒泡排序

冒泡排序（Bubble sort）：時間復(fù)雜度O(n^2)
交換排序的一種。其核心思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序記錄為止。
先定義一個交換元素位置的函數(shù)：

class SQList():

    def __init__(self, nums):
        self.nums = nums

    def swap(self, i, j):
        '''將nums數(shù)組的第i個元素和第j個元素交換位置'''
        self.nums[i] , self.nums[j] = self.nums[j], self.nums[i]
        return

冒泡排序是最簡單的一種排序方法。
可以細(xì)分為以下三種：

1、簡單排序

簡單排序的思想很簡單，將第一個元素與后面所有元素依次進(jìn)行比較，如果第一個元素更大，則交換兩元素的位置，經(jīng)過一輪比較后，第一個元素就是該列表中最小的數(shù)，然后再用第二個元素依次與后面的元素比較。時間復(fù)雜度為O(n^2)。

def simple_sort(self):
    '''簡單排序'''
    for i in range(len(self.nums)):
        for j in range(i+1, len(self.nums)):
            if self.nums[i] > self.nums[j]:
                self.swap(i, j)
    return self.nums

2、冒泡排序

冒泡排序雖然也是兩兩比較，但是跟簡單排序不一樣，冒泡排序是每兩個相鄰的元素比較，如果大小相反則交換，如果從數(shù)組第一個元素開始比較的話，經(jīng)過一輪后，最大的數(shù)就排到了數(shù)組的最后一位，然后再接著排第二大的數(shù)。時間復(fù)雜度為O(n^2)。

def simple_bubble(self):
    '''簡單冒泡排序'''
    j = 0
    while j <= len(self.nums)-1:
        for i in range(len(self.nums)-j-1):
            if self.nums[i] > self.nums[i+1]:
                self.swap(i, i+1)
        j += 1
    return self.nums

3、改進(jìn)版冒泡排序

改進(jìn)的冒泡排序的思路跟冒泡排序是一樣的，不過增加了一個提前中止的條件，如果在某一輪比較中，沒有任何兩個元素交換位置，那么此時的序列已經(jīng)是有序的，可以提前中止。時間復(fù)雜度為O(n^2)。

def bubble(self):
    '''改進(jìn)版冒泡排序'''
    j = 0
    while j <= len(self.nums)-1:
        flag = False
        for i in range(len(self.nums)-j-1):
            if self.nums[i] > self.nums[i+1]:
                self.swap(i, i+1)
                flag = True
        if not flag:
            return self.nums
        j += 1
    return self.nums

冒泡排序整理完了，下面開始第二大排序算法

三、簡單選擇排序

冒泡排序是每次比較如果位置錯了就會交換一次位置，換了很多次位置后才確定了一個元素的位置。那么我們可不可以只用一次交換就確定一個元素的位置呢？當(dāng)我們要排第一個位置的元素時，我們可以找到第一個以后所有元素的最小值，再和第一個位置比較，如果位置錯誤，那么就交換位置。那樣我們雖然遍歷了整個列表，但是只用了一次交換函數(shù)，雖然時間復(fù)雜度跟冒泡排序一樣，但是只調(diào)用了一次交換函數(shù)，所以相對冒泡排序還是有一定程度的改進(jìn)。時間復(fù)雜度為O(n^2)

def select_sort(self):
    '''簡單選擇排序'''
    for i in range(len(self.nums)-1):
        temp = [None, -1]
        for j in range(i, len(self.nums)):
            if not temp[0]:
                temp = [self.nums[j], j]
            if self.nums[j] < temp[0]:
                temp = [self.nums[j], j]
        if temp[0] < self.nums[i]:
            self.swap(i, temp[1])
    return self.nums

2018.10.20

四、直接插入排序

直接插入排序的思想是將一個新的元素插入到前面排好序的序列中。時間復(fù)雜度為O(n^2)

def insert_sort(self):
    '''插入排序'''
    for i in range(1, len(self.nums)):
        j = i - 1
        temp = self.nums[i]
        while j >= 0 and temp < self.nums[j]:
            self.nums[j+1] = self.nums[j]
            j -= 1
        self.nums[j+1] = temp
    return self.nums

抄原文一張圖

image.png

五、希爾排序

希爾排序是對直接插入排序的改進(jìn)版，其核心思想是將原始數(shù)據(jù)集分割成若干個子序列，然后再對子序列分別進(jìn)行插入排序，使子序列基本有序，最后再對全體進(jìn)行一次插入排序。
這里最關(guān)鍵的是跳躍和分割的策略，也就是我們要怎么分割數(shù)據(jù)，間隔多大的問題。通常將相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。下面的例子中通過：increment = int(increment/3)+1來確定“增量”的值。
第一遍沒看明白，后來查了其它的資料，才完全明白是怎么回事。以下內(nèi)容來自博客：https://www.cnblogs.com/chengxiao/p/6104371.html

image.png

image.png

希爾排序的時間復(fù)雜度為：O(n^(3/2))
根據(jù)這個思路自己寫的代碼:

def shell_sort(self):
    def insertSortPerGap(nums, gap):
        for i in range(1, len(nums)):
            j = i - gap
            temp = nums[i]
            while j >= 0 and temp < nums[j]:
                nums[j+gap] = nums[j]
                j -= gap
            nums[j + gap] = temp
        return
    gap = int(len(self.nums)/2)
    while gap>=1:
        insertSortPerGap(self.nums, gap)
        gap = int(gap/2)
    return self.nums

2018.10.21

六、堆排序

參考的也是寫希爾排序的博客：https://www.cnblogs.com/chengxiao/p/6129630.html
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最好、最壞、平均時間復(fù)雜度為O(nlogn)，它是不穩(wěn)定排序
堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆，或者每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆。
我們用簡單的公式來描述一下堆的定義就是(索引從0開始)：
大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想是：將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母Y(jié)點。將其與末尾元素進(jìn)行交換，此時末尾就是最大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值，如此反復(fù)執(zhí)行，就能得到一個有序序列。
一般升序采用大頂堆，降序采用小頂堆
所以堆排序的關(guān)鍵就在于如何將一個序列構(gòu)造成一個堆?？梢詮淖詈笠粋€非葉子結(jié)點開始，從左至右，從下至上進(jìn)行調(diào)整。根據(jù)完全二叉樹的性質(zhì)，可以知道最后一個非葉子結(jié)點的索引就是len(array)//2 - 1(根結(jié)點索引為0)，那么它之前的所有結(jié)點都是非葉子結(jié)點，只需要按照這個順序去構(gòu)造大頂堆或小頂堆就可以了。
以下自己用python實現(xiàn)的代碼：

def heap_sort(self):

    def heap_adjust(nums, length):
        index_root = int(length // 2 - 1)
        while index_root >= 0:
            index_kid1 = index_root * 2 + 1
            index_kid2 = index_root * 2 + 2
            if nums[index_root] < nums[index_kid1]:
                self.swap(index_root, index_kid1)
            if index_kid2 <= length - 1:
                if nums[index_root] < nums[index_kid2]:
                    self.swap(index_root, index_kid2)
            index_root -= 1

    length = len(self.nums)
    while length >= 2:
        heap_adjust(self.nums, length)
        self.swap(0, length - 1)
        length -= 1
    return self.nums

七、歸并排序

思想比較簡單，參考https://www.cnblogs.com/chengxiao/p/6194356.html
歸并排序（MERGE-SORT）是利用歸并的思想實現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

image.png

def merge_sort(self):

    def msort(nums):
        if len(nums) <= 1:
            return nums
        mid = len(nums)//2
        left = msort(nums[:mid])
        right = msort(nums[mid:])
        return merge(left+right)

    def merge(numbers):
        temp = [0] * len(numbers)
        i = 0
        j = len(numbers) // 2
        index = 0
        while i < len(numbers) // 2 and j < len(numbers):
            if numbers[i] < numbers[j]:
                temp[index] = numbers[i]
                index += 1
                i += 1
            else:
                temp[index] = numbers[j]
                index += 1
                j += 1
        if i < len(numbers) // 2:
            temp[index:] = numbers[i:len(numbers) // 2]
        else:
            temp[index:] = numbers[j:]
        numbers = temp
        return numbers
    return msort(self.nums)

2018.10.22
今天就只剩最后一個快速排序了。

八、快速排序

快速排序（Quick Sort）由圖靈獎獲得者Tony Hoare發(fā)明，被列為20世紀(jì)十大算法之一。冒泡排序的升級版，交換排序的一種。快速排序的時間復(fù)雜度為O(nlog(n))。

快速排序算法的核心思想：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后分別對這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個記錄集合的排序目的。

核心的交換代碼我自己寫的比較復(fù)雜，以下是我自己寫的：

def splitByK(numbers):
    times = 0
    leftindex = 0
    rightindex = len(numbers) - 1
    k = numbers[0]
    while rightindex > leftindex:
        if times % 2 == 0:
            if numbers[rightindex] < k:
                numbers[leftindex] = numbers[rightindex]
                times += 1
                leftindex += 1
            else:
                rightindex -= 1
        if times % 2 == 1:
            if numbers[leftindex] >= k:
                numbers[rightindex] = numbers[leftindex]
                times += 1
                rightindex -= 1
            else:
                leftindex += 1
    numbers[rightindex] = k

然后參考別人的代碼思路，重新碼了一遍：

def partition(nums):
    leftindex = 0
    rightindex = len(nums) - 1
    k = nums[0]
    while leftindex < rightindex:

        while leftindex < rightindex and nums[rightindex] > k:
            rightindex -= 1
        swap(nums, leftindex, rightindex)

        while leftindex < rightindex and nums[leftindex] < k:
            leftindex += 1
        swap(nums, leftindex, rightindex)

最后是完整代碼:

def quick_sort(self):

    def partition(nums, leftindex, rightindex):
        leftindex = leftindex
        rightindex = rightindex
        k = nums[leftindex]
        while leftindex < rightindex:

            while leftindex < rightindex and nums[rightindex] > k:
                rightindex -= 1
            self.swap(leftindex, rightindex)

            while leftindex < rightindex and nums[leftindex] < k:
                leftindex += 1
            self.swap(leftindex, rightindex)
        return leftindex

    def qsort(nums, low, high):
        if low < high:
            pivot = partition(nums, low, high)
            qsort(nums, 0, pivot)
            qsort(nums, pivot+1, high)

    qsort(self.nums, 0, len(self.nums)-1)
    return self.nums

快速排序的時間性能取決于遞歸的深度。
當(dāng)pivot_key恰好處于記錄關(guān)鍵碼的中間值時，大小兩區(qū)的劃分比較均衡，接近一個平衡二叉樹，此時的時間復(fù)雜度為O(nlog(n))。
當(dāng)原記錄集合是一個正序或逆序的情況下，分區(qū)的結(jié)果就是一棵斜樹，其深度為n-1，每一次執(zhí)行大小分區(qū)，都要使用n-i次比較，其最終時間復(fù)雜度為O(n^2)。
在一般情況下，通過數(shù)學(xué)歸納法可證明，快速排序的時間復(fù)雜度為O(nlog(n))。
但是由于關(guān)鍵字的比較和交換是跳躍式的，因此，快速排序是一種不穩(wěn)定排序。
同時由于采用的遞歸技術(shù)，該算法需要一定的輔助空間，其空間復(fù)雜度為O(logn)。

最后再補充一點各個排序的應(yīng)用場景，參考：https://blog.csdn.net/mbuger/article/details/67643185

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。
　當(dāng)記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。
(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜；
(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
　快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短；
　堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。
　若要求排序穩(wěn)定，則可選用歸并排序。但前面介紹的從單個記錄起進(jìn)行兩兩歸并的排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起使用。先利用直接插入排序求得較長的有序子序列，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定 的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。