歸並排序
歸並排序也稱合並排序，是分治法的典型應用。分治思想是將每個問題分解成個個小問題，將每個小問題解決，然後合並。
具體的歸並排序就是，將壹組無序數按n/2遞歸分解成只有壹個元素的子項，壹個元素就是已經排好序的了。然後將這些有序的子元素進行合並。
合並的過程就是 對 兩個已經排好序的子序列，先選取兩個子序列中最小的元素進行比較，選取兩個元素中最小的那個子序列並將其從子序列中
去掉添加到最終的結果集中，直到兩個子序列歸並完成。
代碼如下：
#!/usr/bin/python?import sysdef merge(nums, first, middle, last):?''''' merge '''?# 切片邊界,左閉右開並且是了0為開始?lnums = nums[first:middle+1]?rnums = nums[middle+1:last+1]?lnums.append(sys.maxint)?rnums.append(sys.maxint)?l = 0?r = 0?for i in range(first, last+1):?if lnums[l] < rnums[r]:?nums[i] = lnums[l]?l+=1?else:?nums[i] = rnums[r]?r+=1?def merge_sort(nums, first, last):?''''' merge sortmerge_sort函數中傳遞的是下標，不是元素個數'''?if first < last:?middle = (first + last)/2?merge_sort(nums, first, middle)?merge_sort(nums, middle+1, last)?merge(nums, first, middle,last)if __name__ == '__main__':?nums = [10,8,4,-1,2,6,7,3]?print 'nums is:', nums?merge_sort(nums, 0, 7)?print 'merge sort:', nums
穩定，時間復雜度 O(nlog n)
插入排序
代碼如下：
#!/usr/bin/python?importsysdefinsert_sort(a):?''''' 插入排序有壹個已經有序的數據序列，要求在這個已經排好的數據序列中插入壹個數，但要求插入後此數據序列仍然有序。剛開始 壹個元素顯然有序，然後插入壹個元素到適當位置，然後再插入第三個元素，依次類推'''?a_len = len(a)?if a_len = 0 and a[j] > key:?a[j+1] = a[j]?j-=1?a[j+1] = key?return aif __name__ == '__main__':?nums = [10,8,4,-1,2,6,7,3]?print 'nums is:', nums?insert_sort(nums)?print 'insert sort:', nums
穩定，時間復雜度 O(n^2)
交換兩個元素的值python中妳可以這麽寫：a, b = b, a，其實這是因為賦值符號的左右兩邊都是元組
（這裏需要強調的是，在python中，元組其實是由逗號“,”來界定的，而不是括號）。
選擇排序
選擇排序(Selection sort)是壹種簡單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到
排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所
有元素均排序完畢。