插入排序的來(lái)源

在一個(gè)序列已經(jīng)有序的情況下，想在序列號(hào)中插入一個(gè)數(shù)，且插入后依舊有序。這個(gè)時(shí)候可以用插入排序

插入排序的基本思想

每一步將待排序的值，按其值與已經(jīng)排好序的序列比較大小，然后插入合適的位置。

python代碼實(shí)現(xiàn)

#!/usr/bin/python
# encoding: utf-8

# 插入排序

def insertSort(alist):
    # 迭代的次數(shù)
    for i in range(1,len(alist)):
        # 從序列中的第二個(gè)數(shù)作為待排序的數(shù)
        flag = alist[i]
        # 待排序的數(shù)與排好的序列 從后往前一次比較
        for j in range(i,0,-1):
            # 若小于序列中的數(shù)，則交換位置
            if alist[j-1] > alist[j]:
                alist[j-1],alist[j] = alist[j], alist[j-1]

elem = [3,5,2,1,6,7,4]
insertSort(elem)
print elem # [1, 2, 3, 4, 5, 6, 7]

折半插入排序

折半插入排序是對(duì)直接插入排序的一種優(yōu)化，在待排序數(shù)與已經(jīng)排好序的序列比較時(shí)，不從最后面一次往前面比較，而是從最中間的位置（k/2）比較，若大于這個(gè)最中間的數(shù)，則取k/2到k之間最中間的數(shù)繼續(xù)比較，最終找到插入的位置。

#!/usr/bin/python
# encoding: utf-8

def halfInsertSort(alist):
    # 迭代的次數(shù)
    for i in range(1, len(alist)):
        # 從序列中的第二個(gè)數(shù)作為待排序的數(shù)
        flag = alist[i]
        low, high = 0, i - 1
        # 待排序的數(shù)與排好的序列 比較
        while low <= high:
            # 中間值
            mid = (low+high)/2
            # 如果小于中間值，
            if alist[mid] > flag:
                # 則在小于中間值的那部分查找
                high = mid-1
            # 如果大于中間值
            else:
                # 則在大于中間值得那部分查找
                low = mid+1
        # 刪除這個(gè)位置的值
        alist.pop(i)
        # 添加flag到找到的位置(這里一定是low的位置，而不是high)
        alist.insert(low,flag)

elem = [3, 5, 2, 1, 6, 7, 4]
halfInsertSort(elem)
print elem  # [1, 2, 3, 4, 5, 6, 7]