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

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

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

1. 冒泡排序

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

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

接下來(lái)通過(guò)一個(gè)案例來(lái)學(xué)習(xí)冒泡排序。有一個(gè)待排序序列[49,38,65,97,76,13,27,49]，使用冒泡排序?qū)⒘斜碇械捻?xiàng)由小到大進(jìn)行排列。

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

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

繼續(xù)使用上述方法對(duì)待排序序列進(jìn)行排序，直到待排序序列中沒(méi)有項(xiàng)為止。

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

1. >>> nums = [49, 38, 65, 97, 76, 13, 27, 49]   # 使用列表存儲(chǔ)待排序序列 
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個(gè)項(xiàng)的待排序序列看作是一個(gè)有序序列和一個(gè)無(wú)序序列。初始有序序列中只包含第1項(xiàng)，無(wú)序序列中包含除第1項(xiàng)之外的n-1個(gè)項(xiàng)，排序過(guò)程中每次從無(wú)序序列中退出第一個(gè)項(xiàng)，將它插入有序序列的適當(dāng)位置，使之成為新的有序序列，有序序列中項(xiàng)的個(gè)數(shù)加1。這樣經(jīng)過(guò)n-1次插入后，無(wú)序序列變?yōu)榭招蛄�，有序序列中包含了全部n個(gè)項(xiàng)，排序完畢。

接下來(lái)通過(guò)一個(gè)案例來(lái)學(xué)習(xí)直接插入排序。有一個(gè)待排序序列[9,3,1,4,2,7,8,6,5]，使用直接插入排序?qū)⒘斜碇械捻?xiàng)由小到大進(jìn)行排列，代碼如下：

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