一、排序的基本概念和分類(lèi)
所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。排序算法，就是如何使得記錄按照要求排列的方法。
排序的穩(wěn)定性：
經(jīng)過(guò)某種排序后，如果兩個(gè)記錄序號(hào)同等，且兩者在原無(wú)序記錄中的先后秩序依然保持不變，則稱(chēng)所使用的排序方法是穩(wěn)定的，反之是不穩(wěn)定的。
內(nèi)排序和外排序
- 內(nèi)排序：排序過(guò)程中，待排序的所有記錄全部放在內(nèi)存中
- 外排序：排序過(guò)程中，使用到了外部存儲(chǔ)。
通常討論的都是內(nèi)排序。
影響內(nèi)排序算法性能的三個(gè)因素：
- 時(shí)間復(fù)雜度：即時(shí)間性能，高效率的排序算法應(yīng)該是具有盡可能少的關(guān)鍵字比較次數(shù)和記錄的移動(dòng)次數(shù)
- 空間復(fù)雜度：主要是執(zhí)行算法所需要的輔助空間，越少越好。
- 算法復(fù)雜性。主要是指代碼的復(fù)雜性。
增長(zhǎng)量級(jí)(order of growth)是一個(gè)函數(shù)集合，集合中函數(shù)的增長(zhǎng)行為被認(rèn)為是相當(dāng)?shù)摹?例如2n、100n和n+1屬于相同的增長(zhǎng)量級(jí)，可用 大O符號(hào)(Big-Oh notation) 寫(xiě)成O(n)， 而且常被稱(chēng)作 線性級(jí) (linear)，因?yàn)榧现械拿總€(gè)函數(shù)隨著n線性增長(zhǎng)。
首項(xiàng)為 n2 的函數(shù)屬于 O(n2)；它們被稱(chēng)為 二次方級(jí) (quadratic)。
下表列出了算法分析中最通常的一些增長(zhǎng)量級(jí)，按照運(yùn)行效率從高到低排列
constant：常數(shù)級(jí)；logarithmic：對(duì)數(shù)級(jí)；linear：線性級(jí)；linearithmic：線性對(duì)數(shù)級(jí)；quadratic：二次方級(jí)；cubic：三次方級(jí)；exponential：指數(shù)級(jí)
對(duì)于對(duì)數(shù)級(jí)，對(duì)數(shù)的基數(shù)并不影響增長(zhǎng)量級(jí)。 改變基數(shù)等價(jià)于乘以一個(gè)常數(shù)，其不改變?cè)鲩L(zhǎng)量級(jí)。相應(yīng)的，所有的指數(shù)級(jí)數(shù)都屬于相同的增長(zhǎng)量級(jí)，而無(wú)需考慮指數(shù)的基數(shù)大小。指數(shù)函數(shù)增長(zhǎng)量級(jí)增長(zhǎng)的非?？?，因此指數(shù)級(jí)算法只用于小規(guī)模問(wèn)題。
根據(jù)排序過(guò)程中借助的主要操作，可把內(nèi)排序分為：
- 插入排序
- 交換排序
- 選擇排序
- 歸并排序
按照算法復(fù)雜度可分為兩類(lèi)：
- 簡(jiǎn)單算法：包括冒泡排序、簡(jiǎn)單選擇排序和直接插入排序
- 改進(jìn)算法：包括希爾排序、堆排序、歸并排序和快速排序
以下的七種排序算法只是所有排序算法中最經(jīng)典的幾種，不代表全部。
二、 冒泡排序
冒泡排序（Bubble sort）：時(shí)間復(fù)雜度O(n^2)
交換排序的一種。其核心思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序記錄為止。
其實(shí)現(xiàn)細(xì)節(jié)可以不同，比如下面3種：
- 最簡(jiǎn)單排序?qū)崿F(xiàn):bubble_sort_simple
- 冒泡排序:bubble_sort
- 改進(jìn)的冒泡排序:bubble_sort_advance
# -*- coding:utf-8 -*-
# Python 3.6.5
# 冒泡排序算法
class SQList:
def __init__(self, lis=None):
self.r = lis
def swap(self, i, j):
"""定義一個(gè)交換元素的方法，方便后面調(diào)用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def bubble_sort_simple(self):
"""
最簡(jiǎn)單的交換排序，時(shí)間復(fù)雜度O(n^2)
"""
lis = self.r
length = len(self.r)
for i in range(length):
for j in range(i+1, length):
if lis[i] > lis[j]:
self.swap(i, j)
def bubble_sort(self):
"""
冒泡排序，時(shí)間復(fù)雜度O(n^2)
"""
lis = self.r
length = len(self.r)
for i in range(length):
j = length-2
while j >= i:
if lis[j] > lis[j+1]:
self.swap(j, j+1)
j -= 1
def bubble_sort_advance(self):
"""
冒泡排序改進(jìn)算法，時(shí)間復(fù)雜度O(n^2)
設(shè)置flag，當(dāng)一輪比較中未發(fā)生交換動(dòng)作，則說(shuō)明后面的元素其實(shí)已經(jīng)有序排列了。
對(duì)于比較規(guī)整的元素集合，可提高一定的排序效率。
"""
lis = self.r
length = len(self.r)
flag = True
i = 0
while i < length and flag:
flag = False
j = length - 2
while j >= i:
if lis[j] > lis[j + 1]:
self.swap(j, j + 1)
flag = True
j -= 1
i += 1
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4,1,7,3,8,5,9,2,6])
# sqlist.bubble_sort_simple()
# sqlist.bubble_sort()
sqlist.bubble_sort_advance()
print(sqlist)
三、簡(jiǎn)單選擇排序
簡(jiǎn)單選擇排序（simple selection sort）:時(shí)間復(fù)雜度O(n^2)
通過(guò)n-i次關(guān)鍵字之間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i（1<=i<=n)個(gè)記錄進(jìn)行交換。
通俗的說(shuō)就是，對(duì)尚未完成排序的所有元素，從頭到尾比一遍，記錄下最小的那個(gè)元素的下標(biāo)，也就是該元素的位置。再把該元素交換到當(dāng)前遍歷的最前面。其效率之處在于，每一輪中比較了很多次，但只交換一次。因此雖然它的時(shí)間復(fù)雜度也是O(n^2)，但比冒泡算法還是要好一點(diǎn)。
# -*- coding:utf-8 -*-
# Python 3.6.5
# 簡(jiǎn)單選擇排序
class SQList:
def __init__(self, lis=None):
self.r = lis
def swap(self, i, j):
"""定義一個(gè)交換元素的方法，方便后面調(diào)用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def select_sort(self):
"""
簡(jiǎn)單選擇排序，時(shí)間復(fù)雜度O(n^2)
"""
lis = self.r
length = len(self.r)
for i in range(length):
minimum = i
for j in range(i+1, length):
if lis[minimum] > lis[j]:
minimum = j
if i != minimum:
self.swap(i, minimum)
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
sqlist.select_sort()
print(sqlist)
四、直接插入排序
直接插入排序（Straight Insertion Sort）:時(shí)間復(fù)雜度O(n^2)
基本操作是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。
# -*- coding:utf-8 -*-
# Python 3.6.5
# 直接插入排序
class SQList:
def __init__(self, lis=None):
self.r = lis
def insert_sort(self):
lis = self.r
length = len(self.r)
# 下標(biāo)從1開(kāi)始
for i in range(1, length):
if lis[i] < lis[i-1]:
temp = lis[i]
j = i-1
while lis[j] > temp and j >= 0:
lis[j+1] = lis[j]
j -= 1
lis[j+1] = temp
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0])
sqlist.insert_sort()
print(sqlist)
該算法需要一個(gè)記錄的輔助空間。最好情況下，當(dāng)原始數(shù)據(jù)就是有序的時(shí)候，只需要一輪對(duì)比，不需要移動(dòng)記錄，此時(shí)時(shí)間復(fù)雜度為O(n)。然而，這基本是幻想。
五、希爾排序
希爾排序（Shell Sort）是插入排序的改進(jìn)版本，其核心思想是將原數(shù)據(jù)集合分割成若干個(gè)子序列，然后再對(duì)子序列分別進(jìn)行直接插入排序，使子序列基本有序，最后再對(duì)全體記錄進(jìn)行一次直接插入排序。
這里最關(guān)鍵的是跳躍和分割的策略，也就是我們要怎么分割數(shù)據(jù)，間隔多大的問(wèn)題。通常將相距某個(gè)“增量”的記錄組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。下面的例子中通過(guò)：increment = int(increment/3)+1來(lái)確定“增量”的值。
希爾排序的時(shí)間復(fù)雜度為：O(n^(3/2))
# -*- coding:utf-8 -*-
# Python 3.6.5
# 希爾排序
class SQList:
def __init__(self, lis=None):
self.r = lis
def shell_sort(self):
"""希爾排序"""
lis = self.r
length = len(lis)
increment = len(lis)
while increment > 1:
increment = int(increment/3)+1
for i in range(increment+1, length):
if lis[i] < lis[i - increment]:
temp = lis[i]
j = i - increment
while j >= 0 and temp < lis[j]:
lis[j+increment] = lis[j]
j -= increment
lis[j+increment] = temp
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22])
sqlist.shell_sort()
print(sqlist)
六、堆排序
堆是具有下列性質(zhì)的完全二叉樹(shù)：
每個(gè)分支節(jié)點(diǎn)的值都大于或等于其左右孩子的值，稱(chēng)為大頂堆；
每個(gè)分支節(jié)點(diǎn)的值都小于或等于其做右孩子的值，稱(chēng)為小頂堆；
因此，其根節(jié)點(diǎn)一定是所有節(jié)點(diǎn)中最大（最?。┑闹?。
如果按照層序遍歷的方式（廣度優(yōu)先）給節(jié)點(diǎn)從1開(kāi)始編號(hào)，則節(jié)點(diǎn)之間滿足如下關(guān)系：
堆排序（Heap Sort）就是利用大頂堆或小頂堆的性質(zhì)進(jìn)行排序的方法。堆排序的總體時(shí)間復(fù)雜度為O(nlogn)。（下面采用大頂堆的方式）
其核心思想是：將待排序的序列構(gòu)造成一個(gè)大頂堆。此時(shí)，整個(gè)序列的最大值就是堆的根節(jié)點(diǎn)。將它與堆數(shù)組的末尾元素交換，然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)大頂堆。反復(fù)執(zhí)行前面的操作，最后獲得一個(gè)有序序列。
# -*- coding:utf-8 -*-
# Python 3.6.5
# 堆排序
class SQList:
def __init__(self, lis=None):
self.r = lis
def swap(self, i, j):
"""定義一個(gè)交換元素的方法，方便后面調(diào)用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def heap_sort(self):
length = len(self.r)
i = int(length/2)
# 將原始序列構(gòu)造成一個(gè)大頂堆
# 遍歷從中間開(kāi)始，到0結(jié)束，其實(shí)這些是堆的分支節(jié)點(diǎn)。
while i >= 0:
self.heap_adjust(i, length-1)
i -= 1
# 逆序遍歷整個(gè)序列，不斷取出根節(jié)點(diǎn)的值，完成實(shí)際的排序。
j = length-1
while j > 0:
# 將當(dāng)前根節(jié)點(diǎn)，也就是列表最開(kāi)頭，下標(biāo)為0的值，交換到最后面j處
self.swap(0, j)
# 將發(fā)生變化的序列重新構(gòu)造成大頂堆
self.heap_adjust(0, j-1)
j -= 1
def heap_adjust(self, s, m):
"""核心的大頂堆構(gòu)造方法，維持序列的堆結(jié)構(gòu)。"""
lis = self.r
temp = lis[s]
i = 2*s
while i <= m:
if i < m and lis[i] < lis[i+1]:
i += 1
if temp >= lis[i]:
break
lis[s] = lis[i]
s = i
i *= 2
lis[s] = temp
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
sqlist.heap_sort()
print(sqlist)
堆排序的運(yùn)行時(shí)間主要消耗在初始構(gòu)建堆和重建堆的反復(fù)篩選上。
其初始構(gòu)建堆時(shí)間復(fù)雜度為O(n)。
正式排序時(shí)，重建堆的時(shí)間復(fù)雜度為O(nlogn)。
所以堆排序的總體時(shí)間復(fù)雜度為O(nlogn)。
堆排序?qū)υ加涗浀呐判驙顟B(tài)不敏感，因此它無(wú)論最好、最壞和平均時(shí)間復(fù)雜度都是O(nlogn)。在性能上要好于冒泡、簡(jiǎn)單選擇和直接插入算法。
空間復(fù)雜度上，只需要一個(gè)用于交換的暫存單元。但是由于記錄的比較和交換是跳躍式的，因此，堆排序也是一種不穩(wěn)定的排序方法。
此外，由于初始構(gòu)建堆的比較次數(shù)較多，堆排序不適合序列個(gè)數(shù)較少的排序工作。
七、歸并排序
歸并排序（Merging Sort）：建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。
# -*- coding:utf-8 -*-
# Python 3.6.5
# 歸并排序
class SQList:
def __init__(self, lis=None):
self.r = lis
def swap(self, i, j):
"""定義一個(gè)交換元素的方法，方便后面調(diào)用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def merge_sort(self):
self.msort(self.r, self.r, 0, len(self.r)-1)
def msort(self, list_sr, list_tr, s, t):
temp = [None for i in range(0, len(list_sr))]
if s == t:
list_tr[s] = list_sr[s]
else:
m = int((s+t)/2)
self.msort(list_sr, temp, s, m)
self.msort(list_sr, temp, m+1, t)
self.merge(temp, list_tr, s, m, t)
def merge(self, list_sr, list_tr, i, m, n):
j = m+1
k = i
while i <= m and j <= n:
if list_sr[i] < list_sr[j]:
list_tr[k] = list_sr[i]
i += 1
else:
list_tr[k] = list_sr[j]
j += 1
k += 1
if i <= m:
for l in range(0, m-i+1):
list_tr[k+l] = list_sr[i+l]
if j <= n:
for l in range(0, n-j+1):
list_tr[k+l] = list_sr[j+l]
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 12, 77, 34, 23])
sqlist.merge_sort()
print(sqlist)
另外一個(gè)版本：
def merge(lfrom, lto, low, mid, high):
"""
兩段需要?dú)w并的序列從左往右遍歷，逐一比較，小的就放到
lto里去，lfrom下標(biāo)+1，lto下標(biāo)+1，然后再取，再比，再放，
最后lfrom里的兩段比完了，lto里留下的就是從小到大排好的一段。
:param lfrom: 原來(lái)的列表
:param lto: 緩存的列表
:param low: 左邊一段的開(kāi)頭下標(biāo)
:param mid: 左右兩段的中間相隔的下標(biāo)
:param high: 右邊一段的最右下標(biāo)
:return:
"""
i, j, k = low, mid, low
while i < mid and j < high:
if lfrom[i] <= lfrom[j]:
lto[k] = lfrom[i]
i += 1
else:
lto[k] = lfrom[j]
j += 1
k += 1
while i < mid:
lto[k] = lfrom[i]
i += 1
k += 1
while j < high:
lto[k] = lfrom[j]
j += 1
k += 1
def merge_pass(lfrom, lto, llen, slen):
"""
用來(lái)處理所有需要合并的段，這需要每段的長(zhǎng)度，以及列表的總長(zhǎng)。
最后的if語(yǔ)句處理表最后部分不規(guī)則的情況。
:param lfrom: 原來(lái)的列表
:param lto: 緩存的列表
:param llen: 列表總長(zhǎng)
:param slen: 每段的長(zhǎng)度
:return:
"""
i = 0
while i+2*slen < llen:
merge(lfrom, lto, i, i+slen, i+2*slen)
i += 2*slen
if i+slen < llen:
merge(lfrom, lto, i, i+slen, llen)
else:
for j in range(i, llen):
lto[j] = lfrom[j]
def merge_sort(lst):
"""
主函數(shù)。
先安排一個(gè)同樣大小的列表，作為輔助空間。
然后在兩個(gè)列表直接做往復(fù)的歸并，每歸并一次slen的長(zhǎng)度增加一倍，
逐漸向llen靠攏，當(dāng)slen==llen時(shí)說(shuō)明歸并結(jié)束了。
歸并完成后最終結(jié)果可能恰好保存在templist里，因此代碼里做兩次歸并，
保證最后的結(jié)果體現(xiàn)在原始的lst列表里。
:param lst: 要排序的原始列表
:return:
"""
slen, llen = 1, len(lst)
templist = [None]*llen
while slen < llen:
merge_pass(lst, templist, llen, slen)
slen *= 2
merge_pass(templist, lst, llen, slen)
slen *= 2
歸并排序?qū)υ夹蛄性胤植记闆r不敏感，其時(shí)間復(fù)雜度為O(nlogn)。
歸并排序在計(jì)算過(guò)程中需要使用一定的輔助空間，用于遞歸和存放結(jié)果，因此其空間復(fù)雜度為O(n+logn)。
歸并排序中不存在跳躍，只有兩兩比較，因此是一種穩(wěn)定排序。
總之，歸并排序是一種比較占用內(nèi)存，但效率高，并且穩(wěn)定的算法。
八、快速排序
快速排序（Quick Sort）由圖靈獎(jiǎng)獲得者Tony Hoare發(fā)明，被列為20世紀(jì)十大算法之一。冒泡排序的升級(jí)版，交換排序的一種?？焖倥判虻臅r(shí)間復(fù)雜度為O(nlog(n))。
快速排序算法的核心思想：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后分別對(duì)這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)記錄集合的排序目的。
# -*- coding:utf-8 -*-
# Python 3.6.5
# 快速排序
class SQList:
def __init__(self, lis=None):
self.r = lis
def swap(self, i, j):
"""定義一個(gè)交換元素的方法，方便后面調(diào)用。"""
temp = self.r[i]
self.r[i] = self.r[j]
self.r[j] = temp
def quick_sort(self):
"""調(diào)用入口"""
self.qsort(0, len(self.r)-1)
def qsort(self, low, high):
"""遞歸調(diào)用"""
if low < high:
pivot = self.partition(low, high)
self.qsort(low, pivot-1)
self.qsort(pivot+1, high)
def partition(self, low, high):
"""
快速排序的核心代碼。
其實(shí)就是將選取的pivot_key不斷交換，將比它小的換到左邊，將比它大的換到右邊。
它自己也在交換中不斷變換自己的位置，直到完成所有的交換為止。
但在函數(shù)調(diào)用的過(guò)程中，pivot_key的值始終不變。
:param low:左邊界下標(biāo)
:param high:右邊界下標(biāo)
:return:分完左右區(qū)后pivot_key所在位置的下標(biāo)
"""
lis = self.r
pivot_key = lis[low]
while low < high:
while low < high and lis[high] >= pivot_key:
high -= 1
self.swap(low, high)
while low < high and lis[low] <= pivot_key:
low += 1
self.swap(low, high)
return low
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0, 123, 22])
sqlist.quick_sort()
print(sqlist)
另外的一個(gè)版本：
def quick_sort(nums):
# 封裝一層的目的是方便用戶調(diào)用
def qsort(lst, begin, end):
if begin >= end:
return
i = begin
key = lst[begin]
for j in range(begin+1, end+1):
if lst[j] < key:
i += 1
lst[i], lst[j] = lst[j], lst[i]
lst[begin], lst[i] = lst[i], lst[begin]
qsort(lst, begin, i-1)
qsort(lst,i+1,end)
qsort(nums, 0, len(nums)-1)
- 快速排序的時(shí)間性能取決于遞歸的深度。
- 當(dāng)pivot_key恰好處于記錄關(guān)鍵碼的中間值時(shí)，大小兩區(qū)的劃分比較均衡，接近一個(gè)平衡二叉樹(shù)，此時(shí)的時(shí)間復(fù)雜度為O(nlog(n))。
- 當(dāng)原記錄集合是一個(gè)正序或逆序的情況下，分區(qū)的結(jié)果就是一棵斜樹(shù)，其深度為n-1，每一次執(zhí)行大小分區(qū)，都要使用n-i次比較，其最終時(shí)間復(fù)雜度為O(n^2)。
- 在一般情況下，通過(guò)數(shù)學(xué)歸納法可證明，快速排序的時(shí)間復(fù)雜度為O(nlog(n))。
- 但是由于關(guān)鍵字的比較和交換是跳躍式的，因此，快速排序是一種不穩(wěn)定排序。
- 同時(shí)由于采用的遞歸技術(shù)，該算法需要一定的輔助空間，其空間復(fù)雜度為O(logn)。
下面是一個(gè)實(shí)例測(cè)試數(shù)據(jù)：
| 測(cè)試數(shù)據(jù)量（個(gè)） | 100 | 1000 | 10000 | 100000 | 1000000 |
|---|---|---|---|---|---|
| 冒泡 | 0.001 | 0.11 11s | - | - | - |
| 反序冒泡 | 0.001 | 0.14 | 14s | - | - |
| 快速排序 | 0.001 | 0.003~0.004 | 0.040~0.046 | 0.51~0.53 | 6.36~6.56s |
從數(shù)據(jù)中可見(jiàn)：
- 數(shù)據(jù)過(guò)萬(wàn)，冒泡算法基本不可用。測(cè)試時(shí)間忠實(shí)的反映了n平方的時(shí)間復(fù)雜度，數(shù)據(jù)擴(kuò)大10倍，耗時(shí)增加100倍
- 對(duì)于Python的列表，反序遍歷比正序遍歷還是要消耗一定的時(shí)間的
- 快速排序在數(shù)據(jù)較大時(shí)，其威力顯現(xiàn)，但不夠穩(wěn)定，總體還是維護(hù)了nlog(n)的復(fù)雜度。
基本的快速排序還有可以優(yōu)化的地方：
1. 優(yōu)化選取的pivot_key
前面我們每次選取pivot_key的都是子序列的第一個(gè)元素，也就是lis[low]，這就比較看運(yùn)氣。運(yùn)氣好時(shí)，該值處于整個(gè)序列的靠近中間值，則構(gòu)造的樹(shù)比較平衡，運(yùn)氣比較差，處于最大或最小位置附近則構(gòu)造的樹(shù)接近斜樹(shù)。
為了保證pivot_key選取的盡可能適中，采取選取序列左中右三個(gè)特殊位置的值中，處于中間值的那個(gè)數(shù)為pivot_key，通常會(huì)比直接用lis[low]要好一點(diǎn)。在代碼中，在原來(lái)的pivot_key = lis[low]這一行前面增加下面的代碼：
m = low + int((high-low)/2)
if lis[low] > lis[high]:
self.swap(low, high)
if lis[m] > lis[high]:
self.swap(high, m)
if lis[m] > lis[low]:
self.swap(m, low)
如果覺(jué)得這樣還不夠好，還可以將整個(gè)序列先劃分為3部分，每一部分求出個(gè)pivot_key，再對(duì)3個(gè)pivot_key再做一次上面的比較得出最終的pivot_key。這時(shí)的pivot_key應(yīng)該很大概率是一個(gè)比較靠譜的值。
2. 減少不必要的交換
原來(lái)的代碼中pivot_key這個(gè)記錄總是再不斷的交換中，其實(shí)這是沒(méi)必要的，完全可以將它暫存在某個(gè)臨時(shí)變量中，如下所示：
def partition(self, low, high):
lis = self.r
m = low + int((high-low)/2)
if lis[low] > lis[high]:
self.swap(low, high)
if lis[m] > lis[high]:
self.swap(high, m)
if lis[m] > lis[low]:
self.swap(m, low)
pivot_key = lis[low]
# temp暫存pivot_key的值
temp = pivot_key
while low < high:
while low < high and lis[high] >= pivot_key:
high -= 1
# 直接替換，而不交換了
lis[low] = lis[high]
while low < high and lis[low] <= pivot_key:
low += 1
lis[high] = lis[low]
lis[low] = temp
return low
3. 優(yōu)化小數(shù)組時(shí)的排序
快速排序算法的遞歸操作在進(jìn)行大量數(shù)據(jù)排序時(shí)，其開(kāi)銷(xiāo)能被接受，速度較快。但進(jìn)行小數(shù)組排序時(shí)則不如直接插入排序來(lái)得快，也就是殺雞用牛刀，未必就比菜刀來(lái)得快。
因此，一種很樸素的做法就是根據(jù)數(shù)據(jù)的多少，做個(gè)使用哪種算法的選擇而已，如下改寫(xiě)qsort方法：
def qsort(self, low, high):
"""根據(jù)序列長(zhǎng)短，選擇使用快速排序還是簡(jiǎn)單插入排序"""
# 7是一個(gè)經(jīng)驗(yàn)值，可根據(jù)實(shí)際情況自行決定該數(shù)值。
MAX_LENGTH = 7
if high-low < MAX_LENGTH:
if low < high:
pivot = self.partition(low, high)
self.qsort(low, pivot - 1)
self.qsort(pivot + 1, high)
else:
# insert_sort方法是我們前面寫(xiě)過(guò)的簡(jiǎn)單插入排序算法
self.insert_sort()
4. 優(yōu)化遞歸操作
可以采用尾遞歸的方式對(duì)整個(gè)算法的遞歸操作進(jìn)行優(yōu)化，改寫(xiě)qsort方法如下：
def qsort(self, low, high):
"""根據(jù)序列長(zhǎng)短，選擇使用快速排序還是簡(jiǎn)單插入排序"""
# 7是一個(gè)經(jīng)驗(yàn)值，可根據(jù)實(shí)際情況自行決定該數(shù)值。
MAX_LENGTH = 7
if high-low < MAX_LENGTH:
# 改用while循環(huán)
while low < high:
pivot = self.partition(low, high)
self.qsort(low, pivot - 1)
# 采用了尾遞歸的方式
low = pivot + 1
else:
# insert_sort方法是我們前面寫(xiě)過(guò)的簡(jiǎn)單插入排序算法
self.insert_sort()
九、排序算法總結(jié)
排序算法的分類(lèi)：
沒(méi)有十全十美的算法，有有點(diǎn)就會(huì)有缺點(diǎn)，即使是快速排序算法，也只是整體性能上的優(yōu)越，也存在排序不穩(wěn)定，需要大量輔助空間，不適于少量數(shù)據(jù)排序等缺點(diǎn)。
七種排序算法性能對(duì)比
- 如果待排序列基本有序，請(qǐng)直接使用簡(jiǎn)單的算法，不要使用復(fù)雜的改進(jìn)算法。
- 歸并排序和快速排序雖然性能高，但是需要更多的輔助空間。其實(shí)就是用空間換時(shí)間。
- 待排序列的元素個(gè)數(shù)越少，就越適合用簡(jiǎn)單的排序方法；元素個(gè)數(shù)越多就越適合用改進(jìn)的排序算法。
- 簡(jiǎn)單選擇排序雖然在時(shí)間性能上不好，但它在空間利用上性能很高。特別適合，那些數(shù)據(jù)量不大，每條數(shù)據(jù)的信息量又比較多的一類(lèi)元素的排序。
參考：http://codingpy.com/books/thinkpython2/21-analysis-of-algorithms.html#id4
