排序算法列表電梯：
選擇排序算法：詳見 《算法4》2.1 - 選擇排序算法(Selection Sort), Python實(shí)現(xiàn)
插入排序算法(Insertion Sort)：詳見《算法4》2.1 - 插入排序算法(Insertion Sort), Python實(shí)現(xiàn)
插入排序算法和選擇排序算法的復(fù)雜度分析:
插入排序和選擇排序都有兩層循環(huán)掏缎，外循環(huán)遍歷整個數(shù)組，內(nèi)循環(huán)稍有區(qū)別：
- 選擇排序的內(nèi)循環(huán)是遍歷一組未排過序的數(shù)組，
- 插入排序的內(nèi)循環(huán)是遍歷一組已排過序的數(shù)組答恶，
在此基礎(chǔ)上蔚晨，進(jìn)行比較或交換齿诞。看起來已經(jīng)排序過的數(shù)組中進(jìn)行插入會感覺性能要好一點(diǎn)乞巧，實(shí)際未必，這要看數(shù)組的具體情況摊鸡，比如最壞情況下所有數(shù)組元素都得過一遍绽媒。
插入排序在插入的時候可以做交換操作，也可以不做交換免猾。
改進(jìn)插入排序算法可以使用二分法等是辕，這里只探討普通的插入排序。
算法復(fù)雜度
| 算法 | 最好情況 | 最壞情況 |
|---|---|---|
| 選擇排序 | 交換0次猎提，比較n(n-1)/2次 | 交換N次 |
| 插入排序 | 交換0次获三，比較N-1次 | 交換n(n-1)/2次，比較n(n-1)/2次 |
看過一些教材，普遍說插入排序算法比選擇排序要快石窑，實(shí)際上從上面的分析可以看出牌芋，其實(shí)二者的復(fù)雜度差不多，都是O(N平方)松逊。后面的代碼實(shí)現(xiàn)測試中也證實(shí)了這一點(diǎn)躺屁。
插入排序和選擇排序算法的比較：
我們的python測試程序，考慮了不同大小的數(shù)組排序:
- 1000
- 10000
- 20000
每種又考慮了三種情況：
- 隨機(jī)生成數(shù)
- 最好情況：原數(shù)組已從小到大排好
- 最壞情況：原數(shù)組已從大到小排好
并與python自帶的sort方法作了比較经宏。
完整代碼如下：
sizes = [
1000,
5000,
10000
]
for size in sizes:
# random generation of items to be sorted
items = range
print "-"*10 + "sorting numbers" + "-"*10
items = []
for i in range(0,size):
items.append(random.randint(2,999))
#print "original items: %r" % items
# the worse case
items_worse = range (size-1,-1,-1)
# the best case
items_best = range(0,size)
to_be_sorted = [
("random case",items),
("worse case",items_worse),
("best case",items_best)
]
def duration(sort_method):
# calculate execution time for our selection sort method
start = time.clock()
sort_method.sort()
end = time.clock()
duration = end - start
return duration
for item in to_be_sorted:
temp = copy.deepcopy(item) # for reversing use after a certain sort
print "-"*10 + item[0] + "-"*10
# calculate duration for insertion sort
insertion_sort = InsertionSort(item[1])
dinsertion = duration(insertion_sort)
item = temp
# calculate duration for selection sort
selection_sort = SelectionSort(item[1])
dselection = duration(selection_sort)
item = temp
# calculate duration for python builtin sort
dpython = duration(item[1])
print "%s: %ds" % ("insertion sort",dinsertion)
print "%s: %ds" % ("selection sort",dselection)
print "%s: %ds" % ("python built-in",dpython)
運(yùn)行結(jié)果：
size = 1000：挺不錯犀暑，都是毫秒級，但是看不出區(qū)別
----------random case----------
item len: 1000
insertion sort: 0s
selection sort: 0s
python built-in: 0s
----------worse case----------
item len: 1000
insertion sort: 0s
selection sort: 0s
python built-in: 0s
----------best case----------
item len: 1000
insertion sort: 0s
selection sort: 0s
python built-in: 0s
size=10000: 有區(qū)別了烁兰，但是很少耐亏，1s差別。不過可以明顯看出沪斟，最好情況下選擇排序卻用了6s多广辰，最壞情況下，插入排序比選擇排序慢了主之。
----------random case----------
item len: 10000
insertion sort: 6s
selection sort: 7s
python built-in: 0s
----------worse case----------
item len: 10000
insertion sort: 8s
selection sort: 7s
python built-in: 0s
----------best case----------
item len: 10000
insertion sort: 0s
selection sort: 6s
python built-in: 0s
size=20000: 兩種排序算法的耗時都明顯提高了择吊，但差別除了最好情況，差別仍然不大槽奕，基本說明二者的復(fù)雜度是差不多的几睛。python自帶的sort方法仍是毫秒級，過段時間等其他排序算法學(xué)了后研究下源碼粤攒。
----------random case----------
item len: 20000
insertion sort: 30s
selection sort: 33s
python built-in: 0s
----------worse case----------
item len: 20000
insertion sort: 39s
selection sort: 33s
python built-in: 0s
----------best case----------
item len: 20000
insertion sort: 0s
selection sort: 32s
python built-in: 0s
