【Python基礎(chǔ)知識】Python中基于列表的算法

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

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

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

1. 冒泡排序

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

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

接下來通過一個案例來學(xué)習(xí)冒泡排序。有一個待排序序列[49,38,65,97,76,13,27,49]，使用冒泡排序?qū)⒘斜碇械捻椨尚〉酱筮M行排列。

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

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

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

使用Python實現(xiàn)冒泡排序，代碼如下：

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個項，排序過程中每次從無序序列中退出第一個項，將它插入有序序列的適當(dāng)位置，使之成為新的有序序列，有序序列中項的個數(shù)加1。這樣經(jīng)過n-1次插入后，無序序列變?yōu)榭招蛄�，有序序列中包含了全部n個項，排序完畢。

接下來通過一個案例來學(xué)習(xí)直接插入排序。有一個待排序序列[9,3,1,4,2,7,8,6,5]，使用直接插入排序?qū)⒘斜碇械捻椨尚〉酱筮M行排列，代碼如下：

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] 

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