冒泡排序

冒泡排序的核心思想是相邻的两个数据进行比较，假设数列A有n个数据，先比较第1个和第2个数据，如果A1 > A2,则交换他们的位置，确保较大的那个数在右侧。
接下来比较A2和A3，采用相同的规则，较大的数向右移动，最后会比较An-1 和An的大小，如果An-1 > An，那么交换他们的位置，这时，An是数列中的最大值。
你肯定已经发现，经过这一轮比较后，数列仍然是无序的，但是没有关系，我们已经找到了最大值An，而且它在队列的末尾。
接下来要做的事情，就是简单的重复之前的过程，整个数列，先暂时把An排除在外，这n-1个无序的数，仍然可以采用之前的方法，找出n-1个数当中的最大值，这样An-1就是第2大的数，继续对n-2个数做相同的事情
为了让你更容易理解冒泡排序，我们先实现一个简单的函数

  1. def move_max(lst, max_index):
  2.     """
  3.     将索引0到max_index这个范围内的最大值移动到max_index位置上
  4.     :param lst:
  5.     :param max_index:
  6.     :return:
  7.     """
  8.     for i in range(max_index):
  9.         if lst[i] > lst[i+1]:
  10.             lst[i], lst[i+1] = lst[i+1], lst[i]
  11. if __name__ == '__main__':
  12.     lst = [7, 1, 4, 2, 3, 6]
  13.     move_max(lst, len(lst)-1)
  14.     print(lst)

这个函数只完成一个简单的功能，它将列表从索引0到max_index之间的最大值移动max_index索引上，这正是冒泡排序的核心思想。
当我们完成这一步，剩下的事情，就是不断的重复这个过程。

  1. def pop_sort(lst):
  2.     for i in range(len(lst)-1, 0, -1):
  3.         move_max(lst, i)
  4. def move_max(lst, max_index):
  5.     """
  6.     将索引0到max_index这个范围内的最大值移动到max_index位置上
  7.     :param lst:
  8.     :param max_index:
  9.     :return:
  10.     """
  11.     for i in range(max_index):
  12.         if lst[i] > lst[i+1]:
  13.             lst[i], lst[i+1] = lst[i+1], lst[i]
  14. if __name__ == '__main__':
  15.     lst = [7, 1, 4, 2, 3, 6]
  16.     pop_sort(lst)
  17.     print(lst)

插入排序

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
咱们举一个例子，你就能明白插入排序的精髓所在

  1. lst = [1, 2, 6, 7, 5]

lst是一个待排序的列表，你仔细观察不难发现，这个列表里的前4个数据已经是有序的了，现在，只需要把最后一个元素5插入到一个合适的位置就可以了。
从7开始向左遍历，比5大的数向右移动，当遇到一个小于等于5的数就停下来，这个位置就是5应该在的位置。当7向右移动时，占据了5的位置，因此，程序里需要一个变量把5保存下来，还需要一个变量把向左遍历时的索引记录下来，最后这个索引就是5应该在的位置。

  1. def insert(lst, index):
  2.     """
  3.     列表lst从索引0到索引index-1 都是有序的
  4.     函数将索引index位置上的元素插入到前面的一个合适的位置
  5.     :param lst:
  6.     :param index:
  7.     :return:
  8.     """
  9.     if lst[index-1] < lst[index]:
  10.         return
  11.     tmp = lst[index]
  12.     tmp_index = index
  13.     while tmp_index > 0 and lst[tmp_index-1] > tmp:
  14.         lst[tmp_index] = lst[tmp_index-1]
  15.         tmp_index -= 1
  16.     lst[tmp_index] = tmp
  17. if __name__ == '__main__':
  18.     lst = [1, 2, 6, 7, 5]
  19.     insert(lst, 4)
  20.     print(lst)

函数默认列表lst从0到index-1都是有序的，现在只需要将索引index位置上的数据插入到合适的位置就可以了。
你可能已经产生了疑惑，咱们是要排序啊，你这函数默认前面index-1个数据都是有序的，这不合理啊，前面index-1个数据如果是无序的，你怎么办呢？
看下面的代码，你就全明白了

  1. def insert(lst, index):
  2.     """
  3.     列表lst从索引0到索引index-1 都是有序的
  4.     函数将索引index位置上的元素插入到前面的一个合适的位置
  5.     :param lst:
  6.     :param index:
  7.     :return:
  8.     """
  9.     if lst[index-1] < lst[index]:
  10.         return
  11.     tmp = lst[index]
  12.     tmp_index = index
  13.     while tmp_index > 0 and lst[tmp_index-1] > tmp:
  14.         lst[tmp_index] = lst[tmp_index-1]
  15.         tmp_index -= 1
  16.     lst[tmp_index] = tmp
  17. def insert_sort(lst):
  18.     for i in range(1, len(lst)):
  19.         insert(lst, i)
  20. if __name__ == '__main__':
  21.     lst = [1, 6, 2, 7, 5]
  22.     insert_sort(lst)
  23.     print(lst)

第1个元素单独看做一个数列，它本身就是有序的，那么只需要执行insert(lst, 1)，就可以保证前两个数据变成有序的，然后执行insert(lst, 2)，此时，从索引0到索引1是有需的，只需要将索引为2的数据插入到合适的位置就可以了。

对代码做了一些优化：

  1. def insert(lst,index):    
  2.     for i in range(index,0,-1):
  3.         if lst[i-1]<lst[i]:
  4.             return 
  5.         else:
  6.             lst[i-1],lst[i]=lst[i],lst[i-1]
  8. def sort(lst):
  9.     for i in range(1,len(lst)):
  10.         insert(lst,i)
  12. if __name__ == "__main__":
  13.     lst=[2,1,34,5,677,3,1,34,12,45,76]
  14.     sort(lst)
  15.     print(lst)

选择排序

假设有一个序列，a[0],a[1],a[2]…a[n]现在，对它进行排序。我们先从0这个位置到n这个位置找出最小值，然后将这个最小值与a[0]交换，然后呢，a[1]到a[n]就是我们接下来要排序的序列
我们可以从1这个位置到n这个位置找出最小值，然后将这个最小值与a[1]交换，之后，a[2]到a[n]就是我们接下来要排序的序列
每一次，我们都从序列中找出一个最小值，然后把它与序列的第一个元素交换位置，这样下去，待排序的元素就会越来越少，直到最后一个

示例代码

  1. def select_sort(lst):
  2.     for i in range(len(lst)):
  3.         min = i
  4.         for j in range(min,len(lst)):
  5.             # 寻找min 到len(lst)-1 这个范围内的最小值
  6.             if lst[min] > lst[j]:
  7.                 min = j
  8.         lst[i], lst[min] = lst[min], lst[i]
  9. lst = [2,6,1,8,2,4,9]
  10. select_sort(lst)
  11. print lst

希尔排序

算法定义

希尔排序，又称缩小增量排序，不要被这个名字吓到，其实，它只是对插入算法的改进而已。
当待排序列基本有序的情况下，插入算法的效率非常高，那么希尔排序就是利用这个特点对插入算法进行了改造升级

分组

待排序数组为

  1. 4,1,67,34,12,35,14,8,6,19

第一轮希尔排序

希尔排序的关键在于对待排序列进行分组，这个分组并不是真的对序列进行了拆分，而仅仅是虚拟的分组
首先，用10/2 = 5, 这里的5就是缩小增量排序中的那个“增量”。从第0个元素开始，每个元素都与自己距离为5的元素分为一组，那么这样一来分组情况就是

  1. 4   35
  2. 1   14
  3. 67  8
  4. 34  6
  5. 12  19

需要注意的是，所谓的分组，仅仅是逻辑上的分组，这10个元素仍然在原来的序列中。上面一共分了5组，每一组都进行插入排序，67 和 8 交换位置，34 和6 交换位置，这样第一次分组后并对各组进行插入排序后，序列变成了

  1. 4, 1, 8, 6, 12, 35, 14, 67, 34, 19

第二轮希尔排序

上一轮排序时，增量为5，那么这一轮增量为5/2 = 2，这就意味着，从第0个元素开始，每个元素都与自己距离为2的元素分为一组，分组情况如下

  1. 4 8 12 14 34
  2. 1 6 35 67 19

整个序列被分成了两组，分别对他们进行插入排序，排序后的结果为

  1. 4, 1, 8, 6, 12, 19, 14, 35, 34, 67

第三轮希尔排序

上一轮排序时，增量为2，这一轮增量为2 /2 = 1，当增量为1的时候，其实就只能分出一个组了，这样，就完全的退化成插入排序了，但是，由于已经进行了两轮希尔排序，使得序列已经基本有序了，那么此时进行插入排序，效果就会非常好
增量从5变为2，从2变为1，是逐渐减小的过程，增量是分组时所使用的步长。

示例代码

有了前面的概念以及算法的理解，写出代码就变得容易了，先分组，然后进行插入排序，你唯一要注意的地方是进行插入排序时，要弄清楚，哪些元素是一组的

  1. lst = [4,1,67,34,12,35,14,8,6,19]
  2. length = len(lst)
  3. step = length//2
  4. while step > 0:
  5.     for i in range(step):
  6.         # 插入排序
  7.         for j in range(i+step, length, step):
  8.             if lst[j] < lst[j-step]:
  9.                 tmp = lst[j]
  10.                 k = j-step
  11.                 while k >= 0 and lst[k] > tmp:
  12.                     lst[k+step] = lst[k]
  13.                     k -= step
  14.                 lst[k+step] = tmp
  15.     step //= 2 #缩小增量
  16. print lst

优化后的代码：

  1. #希尔排序
  3. lst=[4,23,45,67,8,9,341,354,213,4,52,42,45,2,51,3,1]
  5. length=len(lst)
  6. step=length//2
  8. while step>0:
  9.     for i in range(step):
  10.         for j in range(i+step,length,step):
  11.             k=j
  12.             while k>=step and lst[k-step]>lst[k]:
  13.                 lst[k-step],lst[k]=lst[k],lst[k-step]
  14.                 k-=step
  15.     step//=2
  17. print(lst)

快速排序

快速排序的思路可以归结为3个步骤

  1. 从待排序数组中随意选中一个数值，作为基准值
  2. 移动待排序数组中的元素，是的基准值左侧的数值都小于等于它，右侧的数值大于等于它
  3. 基准值将原来的数组分为两部分，针对这两部分，重复步骤1，2， 3

通过分析，可以确定，必然要使用递归算法，遇到递归不要害怕，先把1，2两步分区实现，最后实现第3步的递归
先实现分区

  1. def partition(lst,start,end):
  2.     """
  3.     用lst[start] 做基准值，在start到end这个范围进行分区
  4.     """
  5.     pivot = lst[start]
  6.     while start < end :
  7.         while start < end and lst[end] >= pivot:
  8.             end -= 1
  9.         lst[start] = lst[end]
  10.         while start < end and lst[start] <= pivot:
  11.             start += 1
  12.         lst[end] = lst[start]
  13.     lst[start] = pivot
  14.     return start

partition函数返回基准值最后的索引，知道这个索引，才能将之前的待排序数组分为两部分，下面是递归部分的实现

  1. def my_quick_sort(lst,start,end):
  2.     if start>= end:
  3.         return
  4.     index = partition(lst,start,end)
  5.     my_quick_sort(lst,start,index-1)
  6.     my_quick_sort(lst,index+1,end)

虽然这两段代码里的逻辑，你还有些不清楚，但整个的分析过程应该说是比较清晰的，先实现分区，然后实现递归，在编写算法时，很忌讳大包大揽的考虑问题，不分层次，不分先后，不分轻重。
分区虽然没有让整个数组变得有序，但是让基准值找到了自己应该在的位置，对左右两侧重复分区动作，每一次分区动作都至少让一个元素找到自己应该在的位置。
验证代码

  1. if __name__ == '__main__':
  2.     lst = [4,3,2,4,1,5,7,2]
  3.     my_quick_sort(lst,0,len(lst)-1)
  4.     print lst

我的代码：

  1. #快速排序
  2. def quick_sort(lst,start,end):
  3.     if start>=end:
  4.         return
  6.     mid=lst[start]
  7.     low=start
  8.     high=end
  9.     while low<high:
  10.         while low<high and mid<=lst[high]:
  11.             high-=1
  12.         lst[low]=lst[high]
  14.         while low<high and lst[low]<mid:
  15.             low+=1
  16.         lst[high]=lst[low]
  18.     lst[low]=mid
  20.     quick_sort(lst,start,low-1)
  22.     quick_sort(lst,low+1,end)
  25. if __name__ == "__main__":
  26.     lst=[54, 26, 93, 17, 77, 31, 44, 55, 20]
  27.     quick_sort(lst,0,len(lst)-1)
  29.     print(lst)

归并排序

合并两个有序集合

有两个有序的序列，分别为 [1,4,7] ,[2,3,5],现在请考虑将这两个序列合并成一个有序的序列。
其实方法真的非常简单

  1. 首先创建一个新的序列，分别从两个序列中取出第一个数，1和2，1比2小，把1放到新的序列中
  2. 第一个序列中的1已经放到新序列中，那么拿出4来进行比较，2比4小，把2放到新的序列中
  3. 第二个序列中的2已经放到新序列中，那么拿出3来进行比较，3比4小，把3放到新的序列中
  4. 第二个序列中的3已经放到新序列中，那么拿出5来进行比较，4比5小，把4放到新的序列中
  5. 第一个序列中的4已经放到新序列中，那么拿出7来进行比较，5比7小，把5放到新的序列中
  6. 最后把7放入到新的序列中

合并的方法就是分别从两个序列中拿出一个数来进行比较，小的那一个放到新序列中，然后，从这个小的数所属的序列中拿出一个数来继续比较
示例代码

  1. def merge_lst(left_lst,right_lst):
  2.     left_index, right_index = 0, 0
  3.     res_lst = []
  4.     while left_index < len(left_lst) and right_index < len(right_lst):
  5.         # 小的放入到res_lst中
  6.         if left_lst[left_index] < right_lst[right_index]:
  7.             res_lst.append(left_lst[left_index])
  8.             left_index += 1
  9.         else:
  10.             res_lst.append(right_lst[right_index])
  11.             right_index += 1
  12.     # 循环结束时,必然有一个序列已经都放到新序列里,另一个却没有
  13.     if left_index == len(left_lst):
  14.         res_lst.extend(right_lst[right_index:])
  15.     else:
  16.         res_lst.extend(left_lst[left_index:])
  17.     return res_lst

归并排序

归并排序，利用了合并有序序列的思想，把一个序列分成A,B两个序列，如果这两个序列是有序的，那么直接合并他们不就可以了么，但是A，B两个序列未必是有序的，没关系，就拿A序列来说，我把A序列再分一次，分成A1,A2，如果A1，A2有序我直接对他们进行合并，A不就变得有序了么，但是A1，A2未必有序啊，没关系，我继续分，直到分出来的序列里只有一个元素的时候，一个元素，就是一个有序的序列啊，这个时候不就可以合并了
这样一层一层的分组，分到最后，一个组里只有一个元素，终于符合合并的条件了，再一层一层的向上合并
完成示例代码：

  1. def merge_lst(left_lst,right_lst):
  2.     left_index, right_index = 0, 0
  3.     res_lst = []
  4.     while left_index < len(left_lst) and right_index < len(right_lst):
  5.         # 小的放入到res_lst中
  6.         if left_lst[left_index] < right_lst[right_index]:
  7.             res_lst.append(left_lst[left_index])
  8.             left_index += 1
  9.         else:
  10.             res_lst.append(right_lst[right_index])
  11.             right_index += 1
  12.     # 循环结束时,必然有一个序列已经都放到新序列里,另一个却没有
  13.     if left_index == len(left_lst):
  14.         res_lst.extend(right_lst[right_index:])
  15.     else:
  16.         res_lst.extend(left_lst[left_index:])
  17.     return res_lst
  18. def merge_sort(lst):
  19.     if len(lst) <= 1:
  20.         return lst
  21.     middle = len(lst)//2
  22.     left_lst = merge_sort(lst[:middle])
  23.     right_lst = merge_sort(lst[middle:])
  24.     return merge_lst(left_lst, right_lst)
  25. if __name__ == '__main__':
  26.     lst = [19,4,2,8,3,167,174,34]
  27.     print merge_sort(lst)

基数排序

1. 基数排序

直接使用维基百科里的定义：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列
乍一看，似乎还是没有思路，那我们就一点一点的来理解

2. 一个正整数有多少位？

一个正整数有几位呢？你以为这是一个很傻的问题，好，请用程序来回答
方法一，转成str，求len

  1. print(len(str(98372)))

方法二，log

  1. import math
  2. print(int(math.ceil(math.log(98372, 10))))

log(98372, 10) 的值是小于5的，而ceil返回的是上入整数，这样，也可以获得整数的位数

3. 从低位到高位输出一个正整数的每一位

  1. a = 98372
  2. index = 1
  3. while True:
  4.     b = a%(10**index)
  5.     c = b//(10**(index-1))
  6.     if c == 0 and b == a:
  7.         break
  8.     print(c)
  9.     index += 1

都是基本的对数字进行操作的算法，%是求模，/是进行除运算，什么时候break呢，c等于0且b等于a的时候，这个时候，index等于6，而a的位数只有5位

4. 算法推理过程

有了2，3做铺垫，我们可以开始理解基数排序了，假设有一个序列 lst = [3,56,1,24,134,67,356,321] 它是无序的
那么我们分配10个桶，编号从0到9，现在，请将个位数字是0的放在0号桶里，个位数字是1的放在1号桶里，以此类推，最后，这10个桶里的情况是下面的样子

  1. [[], [1, 321], [], [3], [24, 134], [], [56, 356], [67], [], []]

我们按照从小到大的顺序从桶里把数字都取出来，是这个样子，我们叫它序列 A

  1. [1, 321, 3, 24, 134, 56, 356, 67]

虽然还是无序的，但是，你仔细看，如果只看个位数，是不是已经变得有序了呢？1 1 3 4 6 6 7
接下来，我们再分配10个桶，编号从0到9，对于序列A，将十位数字是0的放在0号桶里，十位数字是1的放在1号桶里，以此类推，如果一个数字没有十位，那就是0呗，最后，桶里的情况是这样的

  1. [[1, 3], [], [321, 24], [134], [], [56, 356], [67], [], [], []]

现在，把这些数字都取出来，我们叫它序列B

  1. [1, 3, 321, 24, 134, 56, 356, 67]

依然是一个无序序列，但是，只看个位是有序的，只看十位也是有序的
最后，再分配10个桶，编号从0到9，对于序列B，将百位数字是0的放在0号桶里，百位数字是1的放在1号桶里，以此类推，如果没有百位，那就是0，最后，桶里的情况是这样的

  1. [[1, 3, 24, 56, 67], [134], [], [321, 356], [], [], [], [], [], []]

把这些数都取出来，结果如下

  1. [1, 3, 24, 56, 67, 134, 321, 356]

一个无序的序列，经过一轮轮排序，个位变得有序，在此基础上，十位变得有序，在此基础上百位变得有序。。。。。最后，整个序列都变得有序了

5. 示例代码

  1. import math
  2. def sort(a, radix=10):
  3.     """a为整数列表， radix为基数"""
  4.     K = int(math.ceil(math.log(max(a), radix))) # 最大值有几位数
  5.     bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
  6.     for i in range(1, K+1): # K次循环
  7.         for val in a:
  8.             bucket[val%(radix**i)//(radix**(i-1))].append(val) # 取整数第K位数字 （从低到高）
  9.         del a[:]
  10.         for each in bucket:
  11.             a.extend(each) # 桶合并
  12.         bucket = [[] for i in range(radix)]
  13. lst = [3,56,1,24,134,67,356,321]
  14. sort(lst)
  15. print(lst)