Note:
寫后感：
理解算法思想很重要！
理解算法思想很重要！
理解算法思想很重要！
之后嘗試自己獨(dú)立碼代碼對(duì)算法的理解更深刻！

本文章所有算法默認(rèn)從小到大排序。

1. 冒泡排序(Bubble Sort)

自然語言描述

按照列表中待排序的先后順序，依次比較相鄰的兩個(gè)數(shù)，若兩者是升序則不做任何操作，否則交換兩者位置。

核心算法舉例

以第一趟為例
1 5 7 3 9 2 6 8 1 與 5比較，不變
1 5 7 3 9 2 6 8 5 與 7比較，不變
1 5 3 7 9 2 6 8 7 與 3比較，交換位置
1 5 3 7 9 2 6 8 7 與 9比較，不變
1 5 3 7 2 9 6 8 9 與 2比較， 交換位置
1 5 3 7 2 6 9 8 9 與 6比較，交換位置
1 5 3 7 2 6 8 9 9 與 8比較，交換位置
所以第一趟結(jié)束后，排序結(jié)果為
1 5 3 7 2 6 8 9 9為最大數(shù)，后續(xù)不需要比較

算法優(yōu)劣分析

• 一共比較((N-1)+(N-2)+...+2+1)次
• 最好情況下交換0次
• 最壞情況下交換((N-1)+(N-2)+...+2+1)次
• 平均時(shí)間復(fù)雜度O(n2)

算法實(shí)現(xiàn)

#-*-coding=UTF-8-*-
class BubbleSort:
    def __init__(self,list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        for i in range(0,len(self.list_)-1):
            for j in range(0, len(self.list_)-i-1):
                if self.list_[j]>self.list_[j+1]:
                    temp = self.list_[j]
                    self.list_[j] = self.list_[j+1]
                    self.list_[j+1] = temp

#實(shí)例化
list1 = BubbleSort([1,8,4,9,2])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

2. 選擇排序算法(Selection Sort)

自然語言描述

• 遍歷列表所有元素，最?。ù螅┑脑胤旁谧钭螅ㄓ遥┻叀?/li>
• 確定第一個(gè)元素位置后，遍歷剩下的所有元素，最?。ù螅┑脑胤旁谧钭螅ㄓ遥┻叀?/li>
• 以此類推，直到倒數(shù)第二個(gè)元素。

核心算法舉例

第二趟比較為例(以找最小數(shù)為例)
此時(shí)min_index = 1
1 7 5 9 4
7 與 5 作比較，min_index更新為2
5 與 9 作比較，min_index不變
5 與 4 作比較，min_index更新為4
將index = 4與index=1的元素交換位置
1 4 5 9 7

算法優(yōu)劣分析

• 一共比較((N-1)+(N-2)+...+2+1)次，交換N次。
• 平均時(shí)間復(fù)雜度O(n2)

算法實(shí)現(xiàn)

#-*-coding = utf-8-*-
class SelectionSort:
    def __init__(self,list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        for i in range(0,len(self.list_)-1):
            min_index, swap_temp = i, i
            for j in range(i, len(self.list_)-1):
                if self.list_[min_index] > self.list_[j+1]:
                    min_index = j + 1
            swap_temp = self.list_[min_index]
            self.list_[min_index] = self.list_[i]
            self.list_[i] = swap_temp
        return self.list_
#實(shí)例化
list1 = SelectionSort([1,7,4,9,2])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

3. 直接插入算法(Insertion Sort)

自然語言描述

在前面已經(jīng)排好序的列表中插入新元素。步驟：

• 將第二元素與第一個(gè)元素比較，如果小于第一個(gè)元素則交換位置，反之不變。
• 將第三個(gè)元素分別與前兩個(gè)元素比較(這里的算法用的是與之前一個(gè)的位置比較)，插入合適位置。
• 以此類推，直到最后一個(gè)元素。

核心算法舉例

第二趟比較為例
此時(shí) current_value = 1
5 7 1
current_value = 1 與7作比較
5 7 7
current_value = 1 與5作比較
5 5 7
將 current_value = 1 插入
1 5 7

算法優(yōu)劣分析

• 最壞的情況下，一共比較并交換（1+2+...+(N-1)）次
• 最好的情況下，只需比較(N-1)次，無需交換
• 平均時(shí)間復(fù)雜度O(n2)
• 穩(wěn)定

插入排序適用于數(shù)量較小，部分或者全部排序過的列表。盡管插入排序的時(shí)間復(fù)雜度也是O(n2)，但一般情況下，插入排序會(huì)比冒泡排序快一倍，要比選擇排序還要快一點(diǎn)。并且，直接插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，可以達(dá)到線性排序的效率。

算法實(shí)現(xiàn)

#-*-coding = UTF-8-*-
class InsertionSort:
    def __init__(self,list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        for i in range(1,len(self.list_)):
            position = i
            current_value = self.list_[i]
            while position>0 and self.list_[position-1]>current_value:
                self.list_[position] = self.list_[position-1]
                position = position - 1
            self.list_[position] = current_value
        return self.list_
#實(shí)例化
list1 = InsertionSort([1,9,3,7])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

4. 希爾排序(Shell Sort)

自然語言描述

直接插入算法一趟只能為數(shù)據(jù)移動(dòng)一位，比較低效。希爾排序作為直接插入算法的優(yōu)化，又稱縮小增量排序、遞減增量排序。

以步長分區(qū)，對(duì)跳過步長的數(shù)進(jìn)行直接插入算法排序，直至步長為1。

步長是希爾排序的精髓，已知的最好步長序列是由Sedgewick提出的 1，5，19，41，109，...

核心算法舉例

原列表：[4,6,8,2,9,3,7,5,1]
步長增量：9/2=4, 4/2=2, 2/2=1 (Note: 取列表長度的一半作為最初步長，這里的步長使用的是Donald Shell的建議)
第一趟(步長為4)：

原列表 4 6 8 2 9 3 7 5 1，分組后為：
4 6 8 2
9 3 7 5
1
排序后為：
1 3 7 2
4 6 8 5
9
即排序后列表順序?yàn)椋?/p>

1 3 7 2 4 6 8 5 9

第二趟(步長為2)

待排序列表1 3 7 2 4 6 8 5 9，分組后為：
1 3
7 2
4 6
8 5
9
排序后為：
1 2
4 3
7 5
8 6
9
即排序后列表順序?yàn)椋?br> 1 2 4 3 7 5 8 6 9

第三趟(步長為1), 即直接插入排序

待排序列表1 2 4 3 7 5 8 6 9
排序后列表順序?yàn)椋? 2 3 4 5 6 7 8 9

算法優(yōu)劣分析

• 希爾排序比插入排序要快，甚至在小數(shù)組中比快速排序和堆排序還快，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢。
• 不穩(wěn)定
• 平均時(shí)間復(fù)雜度O(nlog2n)「n倍的log以2為底n」

算法實(shí)現(xiàn)

巧記：將直接插入算法的步長從1改為gap，加入限制條件gap > 0即可

#-*-coding = utf-8 -*-
class ShellSort():
    def __init__(self, list_=[]):
        self.list_ = list_
    def get_current_list(self):
        return self.list_
    def ascent_sort(self):
        gap = len(self.list_)/2
        while gap > 0:
            for i in range(gap, len(self.list_)):
                current_value = self.list_[i]
                position = i    
                while position >0 and self.list_[position - gap] > current_value:
                    self.list_[position] = self.list_[position - gap]
                    position = position - gap
                self.list_[position] = current_value
            gap = gap/2
        return self.list_

list1 = ShellSort([1,9,3,2,5,8])
print list1.get_current_list()
list1.ascent_sort()
print list1.get_current_list()

5. 歸并排序(Merge Sort)

自然語言描述

將兩個(gè)有序表合并成一個(gè)有序表。歸并排序算法依賴于歸并操作。

from Wikipedia

兩個(gè)有序表，left = [0,3,5,7], right = [1,4]，
合成的有序列表result = []
left[0] < right[0] ----> result = [0]
left[1] > right[0] ----> result = [0,1]
left[1] < right[1] ----> result = [0,1,3]
left[2] > right[1] ----> result = [0,1,3,4]
此時(shí)right[]為空，將left[]剩余的元素依次放入result列表中：result = [0,1,3,4,5,7]

兩種核心算法

遞歸法

遞歸算法思想?yún)⒖歼@里

設(shè)計(jì)遞歸，將復(fù)雜的問題分解為最小規(guī)模子問題。

• 將列表分解為 兩個(gè)更小的列表。
• 遞歸分解，將更小的列表繼續(xù)分解，直到達(dá)到最小規(guī)模，也就是只有一個(gè)元素的時(shí)候。
• 對(duì)已經(jīng)排序好的列表 進(jìn)行合并。單個(gè)元素的列表，認(rèn)為是已經(jīng)排序好的。

from Wikipedia

遞歸python實(shí)現(xiàn)

#-*-coding=utf-8-*-
#遞歸算法
def mergeSort(seq=[]):
    if len(seq) == 1:
        return seq
    else:
        mid = len(seq)/2
        left = []
        right = []
        left = mergeSort(seq[:mid])
        right = mergeSort(seq[mid:])
        return merge(left,right)
#將排好序的
def merge(left=[],right=[]):
    #i, j are index for left and right seperately
    i, j = 0,0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    #將剩余的部分依次加入result
    result = result + left[i:]
    result = result + right[j:]
    return result

#實(shí)例化
list1 = [2,6,8,1,3,9,4]
print list1
print mergeSort(list1)
#time consume
import random,time
start_time = time.time()
seq = random.sample(range(10000), 10000) #random.sample(取值范圍, 獲取的個(gè)數(shù))
result = mergeSort(seq)
print 'Time consume:{}'.format(time.time()-start_time) 

非遞歸法（迭代法）

從最小的子問題開始解決，直到復(fù)雜的問題。要搞清每次排序歸并的對(duì)象。

非遞歸算法（迭代法）

第一次：我們將數(shù)組分為 8個(gè)子數(shù)組 每個(gè)數(shù)組 1 個(gè)元素，對(duì)相鄰的兩個(gè)數(shù)組進(jìn)行排序合并。
第二次：我們將數(shù)組分為 4個(gè)子數(shù)組 每個(gè)數(shù)組 2 個(gè)元素，對(duì)相鄰的兩個(gè)數(shù)組進(jìn)行排序合并。
第三次：我們將數(shù)組分為 2個(gè)子數(shù)組 每個(gè)數(shù)組 4 個(gè)元素，對(duì)相鄰的兩個(gè)數(shù)組進(jìn)行排序合并。
至此：排序完畢。
分析
第一步：每一次子數(shù)組的元素個(gè)數(shù)

k = 1 #子數(shù)組的個(gè)數(shù)
while k <len(seq):
k = k*2

第二步：確定要合并的兩個(gè)相鄰數(shù)組的區(qū)間[low:mid)[mid:height)

low = low(之前的low) +2k
mid = low(現(xiàn)在的low)+k
height = low(現(xiàn)在的low) + 2k
并且，
height不能越界（不能超過數(shù)組長度）；
mid不能大于height（mid大于height說明此時(shí)子數(shù)組個(gè)數(shù)不足k，那么這個(gè)時(shí)候該子數(shù)組不給予拆分直接pass，下圖給予說明）

來自http://www.itdecent.cn/p/3f27384387c1

非遞歸python實(shí)現(xiàn)

#-:-coding=utf-8-*-
class MergeSort:
    def __init__(self,seq=[]):
        self.seq = seq
    def get_current_seq(self):
        return self.seq
    def ascent_sort(self):
        k = 1         #子數(shù)組元素的個(gè)數(shù)
        while k < len(self.seq):
            low = 0
            while low < len(self.seq):
                height = min(low + 2*k, len(self.seq))
                mid = low + k
                if mid < height:
                    '''mergeSort'''
                    left = self.seq[low:mid]
                    right = self.seq[mid:height]
                    result =[]
                    i,j = 0,0
                    while i < len(left) and j < len(right):
                        if left[i] < right[j]:
                            result.append(left[i])
                            i += 1
                        else:
                            result.append(right[j])
                            j += 1
                    result = result + left[i:]
                    result = result + right[j:]
                    '''將原始數(shù)組的[low,height)替代為已經(jīng)排好序的數(shù)組'''
                    self.seq[low:height] = result
                low = low + 2*i

            k *= 2
        return self.seq
list1 = MergeSort([3,5,2,1])
print list1.get_current_seq()
list1.ascent_sort()
print list1.get_current_seq()

6. 堆排序(HeapSort)

堆排序是對(duì)簡單選擇排序的一種優(yōu)化。
堆的定義及性質(zhì)見這里。

堆的主要性質(zhì)：

• 若根的index為1，則最后一個(gè)非葉子節(jié)點(diǎn)的index為len(seq)/2。此時(shí)對(duì)于index為i的節(jié)點(diǎn)，其左節(jié)點(diǎn)的index為2i；右節(jié)點(diǎn)的index為2i+1。
• 若根的index為0，最后一個(gè)非葉子節(jié)點(diǎn)的index為len(seq)/2-1。此時(shí)對(duì)于index為i的節(jié)點(diǎn)；其左節(jié)點(diǎn)的index為2i+1，右節(jié)點(diǎn)的index為2i+2。

堆排序需要解決兩個(gè)主要的問題：

• P1：如何將無序的列表構(gòu)建成最小堆

  
  
  

  P1：如何從無序數(shù)組構(gòu)建最小堆

• P2：將最小堆的頂部取出后如何重建最小堆

  
  
  

  P2：如何重構(gòu)最小堆

堆排序過程演示：

from Wikipedia

堆排序的三個(gè)步驟：

• 構(gòu)建堆
• 調(diào)整堆
• 堆排序

堆排序python實(shí)現(xiàn)

#-*-coding=utf-8-*-
def build_max_heap(seq):
    """建立一個(gè)堆"""
    #根據(jù)完全二叉樹的性質(zhì)，根的index為0，非葉子節(jié)點(diǎn)的index為1至len(seq)/2-1，
    #
    for i in range(len(seq)/2-1, -1, -1):
        max_heap(seq, len(seq), i)
 
def max_heap(seq, heap_size, index):
    """調(diào)整列表中的元素以保證以index為根的堆是一個(gè)最大堆--->從而最終得到從小到大的排列順序"""
    
    # 將當(dāng)前結(jié)點(diǎn)與其左右子節(jié)點(diǎn)比較，將較大的結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)交換，然后遞歸地調(diào)整子樹
    left_child = 2 * index + 1
    right_child = left_child + 1
    if left_child < heap_size and seq[left_child] > seq[index]:
        largest = left_child
    else:
        largest = index
    if right_child < heap_size and seq[right_child] > seq[largest]:
        largest = right_child
    if largest != index:
        seq[index], seq[largest] = seq[largest], seq[index] #python特有，不需temp
        max_heap(seq, heap_size, largest)
        
def heap_sort(to_sort_list):
    """堆排序"""
    
    # 先將列表調(diào)整為堆
    build_max_heap(to_sort_list)
    heap_size = len(to_sort_list)
    # 調(diào)整后列表(此時(shí)為堆）的第一個(gè)元素就是這個(gè)列表中最大的元素，將其與最后一個(gè)元素交換，然后將剩余的列表再調(diào)整為最大堆
    for i in range(len(to_sort_list) - 1, 0, -1):
        to_sort_list[i], to_sort_list[0] = to_sort_list[0], to_sort_list[i]
        heap_size -= 1
        max_heap(to_sort_list, heap_size, 0)
        
   
to_sort_list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heap_sort(to_sort_list)
print to_sort_list

算法優(yōu)劣分析

• 平均時(shí)間復(fù)雜度O(nlogn)
• 空間復(fù)雜度O(1)

7. 快速排序(QuikSort)

自然語言描述

對(duì)冒泡排序的有效改進(jìn)?？焖倥判蚴且环N不穩(wěn)定的排序算法，即多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。

假設(shè)要排序的列表a[0],a[1]...a[n-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用a[0]）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。整個(gè)排序過程可以遞推進(jìn)行，從而使整個(gè)列表變得有序。

更具體一些：

• 設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=n-1；
• 以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key = a[0]；
• 從j開始向前搜索 (順序不能調(diào)轉(zhuǎn)，因?yàn)槟愕谋容^對(duì)象是a[0])，即由后開始向前搜索，找到第一個(gè)小于key的值list[j]，將list[j]賦值給list[i], 并令i++；
• 從i開始向后搜索，即由前開始向后搜索，找到第一個(gè)大于key的list[i]，將list[i]賦值給list[j]，并令j--；
• 重復(fù)第3、4步，直到i = j（下面有圖解說明這一結(jié)束條件）。
  Note:
• 3,4步中，沒找到符合條件時(shí)，改變j、i的值，使得j = j-1，i = i+1，直至找到為止。
• 找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變，只交換所指的值。
• i == j這一過程一定正好是i++或j--完成的時(shí)候，此時(shí)令循環(huán)結(jié)束。

不多說了，上圖！

一趟比較的圖解：

字太丑湊活看

快速排序python實(shí)現(xiàn)

#-*-coding=UTF-8-*-
def quick_sort(a,left,right):
    if len(a) <= 1 or right < 0 or left >= len(a) or right <= left:
        return a
    key = a[left]
    i, j = left, right

    while i < j:
        while a[j] > key and i < j:
            j -= 1
        if a[j] < key and i < j:
            a[i] = a[j]
            i += 1
        while a[i] < key and i < j:
            i += 1
        if a[i] > key and i < j:
            a[j] = a[i]
            j -= 1

    a[i] = key
    quick_sort(a, left, i-1)
    quick_sort(a, i+1, right)
    return a

list1 = [67,23,89,35,28,90,10,24]
left = 0
right = len(list1)-1
print(quick_sort(list1, left, right))

總結(jié)比較

七大算法的比較

補(bǔ)充：

基于桶排序的思想

計(jì)數(shù)排序

class CountingSort:
    def countingSort(self, A, n):
        # Assume that there are only 1000 numbers
        buckets = [0] * 1001
        for num in A:
            buckets[num] += 1
        sorted_arr = []
        for i in range(0, 1001):
            if buckets[i] != 0:
                sorted_arr += [i] * buckets[i]
        return sorted_arr

基數(shù)排序

class RadixSort:
    def radixSort(self, A, n):
        # write code here
        bucket = [[] for l in range(10)]
        for i in range(4):
            for number in A:
                value = (number//10**i)%10
                bucket[value].append(number)
            temp = []
            for j in range(len(bucket)):
                while bucket[j]:
                    temp.append(bucket[j].pop(0))
            A = temp
        return A