算法導論學習1

打算入算法的坑，今天才開始看算法導論這本書，剛好學完了Python基礎，那其中的算法就用Python實作一遍，當做是鞏固Python文法。

2.1 插入排序，概念不用說，大家都知道，就類似于左手一手撲克牌（已按順序排列），右手要插一張牌進去，我們要比較右手和左手牌的大小，以保證正确插入。

僞代碼如下式：

for j = 2 to A.length():
      key=A[j]
      i = j-1
      while i>0 and A[i]>key:
             A[i+1] = A[i]
             i = i -1
      A[i+1] = key
           

Python實作如下，從小到大：

def srt(arr):
	for j in range(1,len(arr)):
		if arr[j-1] > arr[j]:
			key = arr[j]
			i = j - 1
			while i >= 0 and arr[i] > key:
				arr[i+1] = arr[i]
				i = i - 1
			arr[i+1] = key
	print arr
           

從大到小：

def srt(arr):
	for j in range(1,len(arr)):
		if arr[j-1] < arr[j]:
			key = arr[j]
			i = j - 1
			while i >= 0 and arr[i] < key:
				arr[i+1] = arr[i]
				i = i - 1
			arr[i+1] = key
	print arr
           

這裡要提一個循環不變式的三條性質：

1.初始化：循環的第一次疊代前，要為真。

2.保持：如果循環某次疊代之前為真，那下次疊代之前仍為真。

3.終止：終止循環時，不變式為我們提供一個有用的的性質，有助于證明算法正确性。

輸入規模自然的量度是輸入中的項數，我們可以計算算法每步的代價（時間）以及次數，由此可以計算算法運作的時間，同時引入增長率或增長量級概念，比如隻考慮公式的

最高幂次項（an^2）,可以記算法的最壞情況用(Theta n^幂次)。

2.3 設計算法

   分治法思想：将原問題分解為幾個規模較小但類似于原問題的子問題，遞歸地解決這些子問題，然後在合并這些子問題的解來建立原問題的解。步驟可分為：分解--解決--合并。