關于冒泡、選擇、快速排序算法的Python實作代碼，此處不贅述，完整代碼請檢視：
冒泡排序
選擇排序
快速排序
問題1：就這三種排序算法而言，快排是否是最優方案？
問題2：冒泡和選擇的時間複雜度相同，其時間性能表現是否真的相同（或者相差無幾）？
一、在數組的無序程度較高的情況下
下面直接比較它們的時間性能，代碼如下：
if __name__ == '__main__':
import numpy
import time
t = time.time()
for i in range(10000):
array = list(numpy.random.randint(0, 100, 50))
t0 = time.time() - t
print('numpy生成50個0~100之間的數字，10000次所需時間：', t0, 's')
t = time.time()
for i in range(10000):
array = list(numpy.random.randint(0, 100, 50))
bubble_sort(array)
print('冒泡排序：', time.time() - t - t0, 's')
t = time.time()
for i in range(10000):
array = list(numpy.random.randint(0, 100, 50))
select_sort(array)
print('選擇排序：', time.time() - t - t0, 's')
t = time.time()
for i in range(10000):
array = list(numpy.random.randint(0, 100, 50))
quick_sort(array)
print('快速排序：', time.time() - t - t0, 's')
10000次的50是數字的排序時間消耗，多次試驗結果如下：
numpy生成50個0~100之間的數字，10000次所需時間： 0.18699336051940918 s
冒泡排序： 1.6431183815002441 s
選擇排序： 0.7640233039855957 s
快速排序： 0.4690079689025879 s
numpy生成50個0~100之間的數字，10000次所需時間： 0.1920773983001709 s
冒泡排序： 1.551903486251831 s
選擇排序： 0.7149889469146729 s
快速排序： 0.5479793548583984 s
numpy生成50個0~100之間的數字，10000次所需時間： 0.20493817329406738 s
冒泡排序： 1.5134046077728271 s
選擇排序： 0.6773779392242432 s
快速排序： 0.4561192989349365 s
numpy生成50個0~100之間的數字，10000次所需時間： 0.1710827350616455 s
冒泡排序： 1.5479202270507812 s
選擇排序： 0.7355144023895264 s
快速排序： 0.49486231803894043 s
結論：
1、雖然選擇排序和冒泡排序的時間複雜度都是O(n^2)，但是顯然選擇排序要優于冒泡排序，時間消耗大約是其1/2，大約節省50%的時間。
2、快速排序在這三個方法中表現最好，時間消耗大約是冒泡排序的1/3。
二、在數組為正序（從小到大排列）的情況下
if __name__ == '__main__':
import time
print([i for i in range(50)])
t = time.time()
for i in range(10000):
array = [i for i in range(50)]
t0 = time.time() - t
print('生成10000次資料所需時間：', t0, 's')
t = time.time()
for i in range(10000):
array = [i for i in range(50)]
bubble_sort(array)
print('冒泡排序：', time.time() - t - t0, 's')
t = time.time()
for i in range(10000):
array = [i for i in range(50)]
select_sort(array)
print('選擇排序：', time.time() - t - t0, 's')
t = time.time()
for i in range(10000):
array = [i for i in range(50)]
quick_sort(array)
print('快速排序：', time.time() - t - t0, 's')
測試結果：
生成10000次資料所需時間： 0.012993097305297852 s
冒泡排序： 0.8310296535491943 s
選擇排序： 0.6019954681396484 s
快速排序： 1.3461222648620605 s
生成10000次資料所需時間： 0.01307988166809082 s
冒泡排序： 0.8245120048522949 s
選擇排序： 0.6059088706970215 s
快速排序： 1.3093125820159912 s
生成10000次資料所需時間： 0.012005090713500977 s
冒泡排序： 0.9179930686950684 s
選擇排序： 0.6651043891906738 s
快速排序： 1.4826264381408691 s
總結：在正序（已排好序）的情況下，快排算法的優勢就發揮不出來了，變成了最差者；選擇排序依然優于冒泡排序，大約節省25%的時間。
三、在數組為反序（從大到小排列）的情況下
if __name__ == '__main__':
import time
print([i for i in range(50, 0, -1)])
t = time.time()
for i in range(10000):
array = [i for i in range(50, 0, -1)]
t0 = time.time() - t
print('生成10000次資料所需時間：', t0, 's')
t = time.time()
for i in range(10000):
array = [i for i in range(50, 0, -1)]
bubble_sort(array)
print('冒泡排序：', time.time() - t - t0, 's')
t = time.time()
for i in range(10000):
array = [i for i in range(50, 0, -1)]
select_sort(array)
print('選擇排序：', time.time() - t - t0, 's')
t = time.time()
for i in range(10000):
array = [i for i in range(50, 0, -1)]
quick_sort(array)
print('快速排序：', time.time() - t - t0, 's')
測試結果：
生成10000次資料所需時間： 0.014925479888916016 s
冒泡排序： 2.075543165206909 s
選擇排序： 0.7910571098327637 s
快速排序： 1.2525396347045898 s
生成10000次資料所需時間： 0.012000799179077148 s
冒泡排序： 2.0227086544036865 s
選擇排序： 0.7382717132568359 s
快速排序： 1.2780859470367432 s
生成10000次資料所需時間： 0.012999534606933594 s
冒泡排序： 2.0591678619384766 s
選擇排序： 0.7919540405273438 s
快速排序： 1.3123962879180908 s
總結：在反序（順序正好是由大到小排列的）的情況下，快排依然不理想。冒泡排序也變得更差了，選擇比冒泡節省大約60%的時間。選擇排序是三者的最優算法。
“敲黑闆”
1、雖然選擇排序和冒泡排序的時間複雜度都是O(n^2)，但時間複雜度和實際的時間消耗并不嚴格對等，在上述三種情況下，選擇排序都優于冒泡排序。是以不要陷入“時間複雜度相同，其時間消耗就應該很相近”的誤區中。
2、快排的優勢隻能在無序程度較高的情況下才能發揮出來，對于已經有序的數列（無論是正序還是反序），其表現都不會很優秀。
3、選擇排序是三者中，選擇排序是時間性能最穩定的一個，基本在0.6~0.8s；冒泡排序是三種中時間性能最不穩定的一個，基本在0.8~2.0s。
Mr.bai
![[轉]九大排序算法——C語言實作及詳解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)