【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项为止。