劍指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è)計(jì)的一種排序算法，堆排序是一種選擇排序端圈，它的最好焦读、最壞、平均時間復(fù)雜度為O(nlogn)舱权，它是不穩(wěn)定排序
堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值矗晃，稱為大頂堆，或者每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值宴倍，稱為小頂堆张症。
我們用簡單的公式來描述一下堆的定義就是(索引從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é)點(diǎn)吠冤。將其與末尾元素進(jìn)行交換，此時末尾就是最大值恭理。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值郭变，如此反復(fù)執(zhí)行颜价，就能得到一個有序序列。
一般升序采用大頂堆诉濒，降序采用小頂堆
所以堆排序的關(guān)鍵就在于如何將一個序列構(gòu)造成一個堆周伦。可以從最后一個非葉子結(jié)點(diǎn)開始未荒，從左至右专挪，從下至上進(jìn)行調(diào)整。根據(jù)完全二叉樹的性質(zhì)片排，可以知道最后一個非葉子結(jié)點(diǎn)的索引就是len(array)//2 - 1(根結(jié)點(diǎn)索引為0)寨腔，那么它之前的所有結(jié)點(diǎn)都是非葉子結(jié)點(diǎn)，只需要按照這個順序去構(gòu)造大頂堆或小頂堆就可以了率寡。
以下自己用python實(shí)現(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）是利用歸并的思想實(shí)現(xiàn)的排序方法冶共，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解乾蛤，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起每界，即分而治之)。

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ū)⒋庞涗浄指畛瑟?dú)立的兩部分鸥滨，其中一部分記錄的關(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)憾儒。

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

(1)若n較小(如n≤50)乃沙，可采用直接插入或直接選擇排序起趾。
　當(dāng)記錄規(guī)模較小時，直接插入排序較好警儒；否則因?yàn)橹苯舆x擇移動的記錄數(shù)少于直接插人训裆，應(yīng)選直接選擇排序?yàn)橐恕?br> (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人蜀铲、冒泡或隨機(jī)的快速排序?yàn)橐耍?br> (3)若n較大边琉，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序蝙茶。
　快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時诸老，快速排序的平均時間最短隆夯；
　堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況别伏。這兩種排序都是不穩(wěn)定的蹄衷。
　若要求排序穩(wěn)定，則可選用歸并排序厘肮。但前面介紹的從單個記錄起進(jìn)行兩兩歸并的排序算法并不值得提倡愧口，通常可以將它和直接插入排序結(jié)合在一起使用类茂。先利用直接插入排序求得較長的有序子序列耍属，然后再兩兩歸并之托嚣。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定 的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的厚骗。