【Python基礎知識】Python中基于列表的算法

算法是為解決具體問題而采取的確定的、有限的操作步驟。

基于列表的算法最主要的是排序。所謂排序，就是使一串記錄按照其中的某個或某些關鍵字的大小，遞增或遞減地排列起來的操作。列表中的sort()方法可以進行排序，這其實是調用了一個接口，本節將試著自己編寫代碼來實現排序的算法。

排序算法很經典，目前流行的排序算法有冒泡排序、直接插入排序、選擇排序、快速排序、堆排序、歸并排序、希爾排序等。

1. 冒泡排序

冒泡算法的算法思想如下：

對待排序序列從前向后依次比較相鄰項的值，若發現存在逆序(即前一個項的值大于后一個項的值)則交換，使值較大的項逐漸從索引較小的位置移向索引較大的位置，就像水底的氣泡一樣逐漸向上冒。一趟下來，值最大的項就被交換到了待排序序列的最后一個位置。下一趟排序時前一趟確定的值最大的項不再參與排序，一趟排序的結果又把參與排序的值最大的項交換到待排序序列的最后一個位置……這樣一趟一趟進行排序，直到待排序序列中沒有項為止。

接下來通過一個案例來學習冒泡排序。有一個待排序序列[49,38,65,97,76,13,27,49]，使用冒泡排序將列表中的項由小到大進行排列。

第一趟排序：比較49與38，49>38，交換位置;49<65，保持不變;65<97，保持不變;97>76，交換位置;97>13，交換位置;97>27，交換位置;97>49，交換位置。經過第一趟排序，最大的97就被交換到了最后一個位置。第一趟排序一共進行了7次比較，比較次數是待排序序列的個數減1。

第二趟的排序：38<49，保持不變;49<65，保持不變;65<76，保持不變;76>13，交換位置;76>27，交換位置;76>49，交換位置。經過第二趟排序，76移到了倒數第二個位置。第二趟排序一共進行了6次比較。

繼續使用上述方法對待排序序列進行排序，直到待排序序列中沒有項為止。

使用Python實現冒泡排序，代碼如下：

1. >>> nums = [49, 38, 65, 97, 76, 13, 27, 49]   # 使用列表存儲待排序序列 
2. ... for i in range(len(nums) - 1): 
3. ...     for j in range(len(nums) - i - 1): 
4. ...         if nums[j] > nums[j + 1]:   # 若逆序則交換 
5. ...             nums[j], nums[j + 1] = nums[j + 1], nums[j] 
6. ... 
7. >>> print(nums) 
8. [13, 27, 38, 49, 49, 65, 76, 97] 

2. 直接插入排序

直接插入排序的算法思想如下：

把含有n個項的待排序序列看作是一個有序序列和一個無序序列。初始有序序列中只包含第1項，無序序列中包含除第1項之外的n-1個項，排序過程中每次從無序序列中退出第一個項，將它插入有序序列的適當位置，使之成為新的有序序列，有序序列中項的個數加1。這樣經過n-1次插入后，無序序列變為空序列，有序序列中包含了全部n個項，排序完畢。

接下來通過一個案例來學習直接插入排序。有一個待排序序列[9,3,1,4,2,7,8,6,5]，使用直接插入排序將列表中的項由小到大進行排列，代碼如下：

1. >>> nums = [9, 3, 1, 4, 2, 7, 8, 6, 5] 
2. >>> for i in range(1, len(nums)): 
3. ...     if nums[i - 1] > nums[i]: 
4. ...         temp = nums[i] 
5. ...         index = i 
6. ...         while index > 0 and nums[index - 1] > temp: 
7. ...             nums[index] = nums[index - 1] 
8. ...             index -= 1 
9. ...             nums[index] = temp 
10. ... 
11. >>> print(nums) 
12. [1, 2, 3, 4, 5, 6, 7, 8, 9] 

首先設計兩個循環，外層for循環是判斷待插入的項與其前面有序序列的大小關系，由于有序序列已經有序，因此，如果待插入的項大于有序序列最后一個項，那么形成了新的有序序列，則進行下一次外層循環;否則進入內層while循環，待插入的項需要與有序序列中所有的項依次進行比較，若小于則交換位置，直到大于有序序列中的某項或者到達有序序列的第1項為止。