最近在復(fù)習(xí)經(jīng)典排序算法，自己用python也實(shí)現(xiàn)了一下，這里不會涉及到原理（因?yàn)榫W(wǎng)上方法已經(jīng)很詳細(xì)啦），就把函數(shù)貼上來，可以讓大家自己試著運(yùn)行下，再結(jié)合別處的原理也可以更好地理解它們的實(shí)現(xiàn)。
如果有錯誤請指出，或者優(yōu)化的地方，謝謝啦。(′▽｀)

1. 冒泡排序

冒泡排序是實(shí)現(xiàn)起來最簡單的排序算法，時間復(fù)雜度是O（n^2），它的代碼核心是兩層嵌套的for循環(huán)，循環(huán)里一個判斷數(shù)組相鄰兩個元素大小，如果不滿足就交換。
冒泡排序有一個小的優(yōu)化的點(diǎn)：如果在外層循環(huán)的一趟里沒有交換任何元素，就說明排序完成了，就不需要再繼續(xù)排了。所以也設(shè)置了一個flag判斷。
代碼如下：

"""
bubble sorting
"""
 def bubble_sorting(array):
    for i in range(len(array)-1):
        flag = False
        for j in range(len(array)-i-1):
            if array[j]>array[j+1]:
                flag = True
                tmp = array[j]
                array[j] = array[j+1]
                array[j+1] = tmp
        if not flag:
            break
    return array
array = [0,1,0,7,9,8,5,4,2,0]
print(bubble_sorting(array))

運(yùn)行結(jié)果就是[0, 0, 0, 1, 2, 4, 5, 7, 8, 9]

2. 選擇排序

選擇排序也是一種時間復(fù)雜度是O（n^2）的穩(wěn)定排序算法，它的核心思想就是每次遍歷數(shù)組選出最小的放在左邊 ，這樣右邊無序區(qū)越來越小，左邊有序區(qū)越來越大。也是兩層循環(huán)嵌套。
代碼如下：

def select_sorting(array):
    for i in range(len(array)):
        min = array[i]
        min_index = i
        for j in range(i,len(array)):
            if array[j]<min:
                min = array[j]
                min_index = j
        array[min_index] = array[i]
        array[i] = min
    return array
print(select_sorting(array))

運(yùn)行結(jié)果 也是[0, 0, 0, 1, 2, 4, 5, 7, 8, 9]

3. 插入排序

插入排序跟上面兩種排序算法比起來就算有點(diǎn)點(diǎn)繞了，它雖然也是需要兩層循環(huán)，但是內(nèi)層不再是遍歷。插入排序要注意的是外層循環(huán)從第二個值開始，把第一個值當(dāng)作是有序區(qū)。這樣每一個新的值都會跟前面的有序區(qū)進(jìn)行比較，如果小于前一個數(shù)就插到前面，一直到合適的位置為止。

def insert_sorting(array):
    for i in range(1,len(array)):
        j = i-1
        while j >= 0 and array[j]>array[j+1]:
            tmp = array[j+1]
            array[j+1] = array[j]
            array[j] = tmp
            j -= 1
    return array
print(insert_sorting(array))

7-28修改：之前還是覺得內(nèi)層循環(huán)并不是插入排序，而是冒泡排序了，實(shí)際上并不需要每一個結(jié)果都要和上一個交換，因?yàn)椴迦肱判驊?yīng)該是新的數(shù)和前面有序區(qū)的每一個數(shù)比較，如果仍然大于就把前面的數(shù)挪到后面，最后再插入新數(shù)。所以算法優(yōu)化如下。
這里面的最后j+1其實(shí)也卡了我很久，但是后來想到：循環(huán)退出時一定不滿足條件了，要么是j小于零，要么是終于找到了合適的位置。這讓我想到一個小的腦筋急轉(zhuǎn)彎：如果一個新的數(shù)比第二個數(shù)小，那么應(yīng)該插入到哪里？答案是第二個。所以最后要把1加回來。

def insert_sorting1(array):
    for i in range(1,len(array)):
        j = i-1
        tmp = array[i]
        while j >= 0 and array[j]>tmp:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = tmp
    return array

print(insert_sorting1([3,5,4,2,9,1,1,7,8,4]))

4. 快速排序

快速排序……卡了我很久很久，因?yàn)槲乙恢痹趪L試用循環(huán)遞推做，我……失敗了。快排本身是一種很常用（超重要，面試也經(jīng)常考的排序算法），它是一種“分治”的思想，就是要用遞歸的意思，接受了這一點(diǎn)再來寫，就不會自己難為自己了。它始終選一個基準(zhǔn)，一般是左邊第一個，然后注意從右往左推，找到比他更小的就停止，然后從左往右推，找到比他更大的停止，然后判斷下左右兩個指針仍未相遇的話，就交換左右的值。此時左邊都比基準(zhǔn)小，右邊都比基準(zhǔn)大。再對左右兩個子列表分別用這個方法，直到整個列表都有序。
接下來獻(xiàn)上我很丑的代碼：

def quick_sorting(start, end, array):
   if start >= end:
       return
   min = start
   max = end
   pivot = array[min]
   while start < end:
       while start < end and array[end] > pivot:
           end -= 1
       while start < end and array[start] < pivot:
           start += 1
       if start < end:
           array[start], array[end] = array[end], array[start]

   quick_sorting(min, start-1, array)
   quick_sorting(start+1,max,array)

   return array

假如你并不需要保留重復(fù)的項(xiàng)，或者需要排序的列表沒有重復(fù)項(xiàng)，那么可以用一個真正簡單美麗的遞歸解決問題，其實(shí)這個就是剛才的算法的簡化：

def quick_sort(array):
    if len(array)<2:
        return array
    pivot = array[0]
    left = [i for i in array if i < pivot]
    right = [i for i in array if i > pivot]
    return quick_sort(left)+[pivot]+quick_sort(right)
print(quick_sort(array))

7-25 修改：

剛剛想到一個方法可以使上面的快排保留重復(fù)的值，只要做一點(diǎn)小的變化：

def quick_sorting(array):
    if len(set(array))<2:
        return array
    middle = array[0]
    left = [i for i in array if i <middle]
    pivot = [i for i in array if i == middle]
    right = [i for i in array if i > middle]

    return quick_sorting(left)+quick_sorting(pivot)+quick_sorting(right)

print(quick_sorting([9,9,1,8,5,2,3,3,7,14,2,2,2,2]))

所以以后偷懶的快排就可以這么寫啦。

5. 堆排序（堆的基本操作）

我是按照小灰這一篇堆排序的文章寫的代碼，可以參考：
漫畫：什么是二叉堆？（修正版）
總結(jié)起來，堆排序首先要理解二叉堆，大頂堆，小頂堆的概念，然后堆的基本操作有：插入（向上調(diào)整），刪除（向下調(diào)整），調(diào)整二叉堆等。
希望大家有空可以讀一下小灰的那篇文章～寫得很清楚了，我這里就貼自己寫得代碼和用例吧。

# coding:utf-8
import sys

class HeapSorting():

    def __init__(self,array):
        self.arr = array

    def insert(self,value):
        child_index = len(self.arr)
        self.arr.append(value) # add the new value at the end of array
        tmp = self.arr[child_index]
        while child_index >= 1 :
            parent_index = (child_index - 1) // 2
            if self.arr[parent_index] < tmp:
                break
            self.arr[child_index] = self.arr[parent_index]
            child_index = parent_index
        array[child_index] = tmp

        return self.arr


    def delete(self):
        # delete the first value, make the last one the top
        self.arr[0] = self.arr[-1]
        del self.arr[-1]
        parent_index = 0
        child_index = parent_index*2+1
        while child_index <= len(self.arr)-1:
            child_index = parent_index * 2 + 2 if parent_index * 2 + 2 <= len(self.arr) - 1 and self.arr[
                parent_index * 2 + 2] < self.arr[parent_index * 2 + 1] else parent_index * 2 + 1
            if self.arr[parent_index] < self.arr[child_index]:
                break
            tmp = self.arr[parent_index]
            self.arr[parent_index] = self.arr[child_index]
            self.arr[child_index] = tmp
            parent_index = child_index
            child_index = parent_index*2+1
        return self.arr

    def down_adjust(self,parent_index):

        child_index = parent_index*2+1
        while child_index <= len(self.arr)-1:
            child_index = parent_index * 2 + 2 if parent_index * 2 + 2 <= len(self.arr) - 1 and self.arr[
                parent_index * 2 + 2] < self.arr[parent_index * 2 + 1] else parent_index * 2 + 1
            if self.arr[parent_index] < self.arr[child_index]:
                break
            tmp = self.arr[parent_index]
            self.arr[parent_index] = self.arr[child_index]
            self.arr[child_index] = tmp
            parent_index = child_index
            child_index = parent_index*2+1
        return self.arr

    def adjust(self):
        # start from the last non-leaf node
        node = (len(self.arr)-2)//2

        for i in range(node,-1,-1):
            self.arr = self.down_adjust(i)
        return self.arr

array = [7, 2, 6, 3, 9, 8, 5, 10, 12]
heap = HeapSorting(array)
heap_insert = heap.insert(1)
heap_delete = heap.delete() # delete the value on top of the heap
heap_adjust = heap.adjust()

print(heap_adjust)

上面的操作對于理解堆來說非常重要。
過兩天還會補(bǔ)上正式的堆排序～就先寫到這里（鞠躬）