問題描述
將一組隨機(jī)排列的數(shù)字重新按照從小到大的順序排列。
插入算法
每次從數(shù)組中取一個(gè)數(shù)字，與現(xiàn)有數(shù)字比較并插入適當(dāng)位置。
如此重復(fù)，每次均可以保持現(xiàn)有數(shù)字按照順序排列，直到數(shù)字取完，即排序成功。
這很像打牌時(shí)的抓牌情況，
第一個(gè)條件：保持手上的牌的順序是正確的
第二個(gè)條件：每次抓到新的牌均按照順序插入手上的牌中間。
保證這兩條不變，那么無論抓了幾張牌，最后手上的牌都是依照順序排列的。
Python 實(shí)現(xiàn)：
def insertion_sort(n): if len(n) == 1: return n b = insertion_sort(n[1:]) m = len(b) for i in range(m): if n[0] <= b[i]: return b[:i]+[n[0]]+b[i:] return b + [n[0]]
另一個(gè)版本：
def insertion_sort(lst): if len(lst) == 1: return lst for i in xrange(1, len(lst)): temp = lst[i] j = i - 1 while j >= 0 and temp < lst[j]: lst[j + 1] = lst[j] j -= 1 lst[j + 1] = temp return lst
新聞熱點(diǎn)
疑難解答
圖片精選
