课程频道导航
课程分类导航
当前位置：首页 > Python教程 > python技巧

各种排序算法的Python实现。

大学的算法导论课确实是混过去的，到了毕业的时候结果连个冒泡排序都不能裸写出来，只记得一些算法的基本理论，如分治法、递归、动态规划、回溯、图论、时间空间理论这些。大概知道这些排序算法的实现原理，真在纸上写出来脑子又是一团浆糊。最近在网上看到九章算法的网络课程费用是1299，团购价是799，真是狠不下心去买，也后悔大学里没好好学点算法，浪费了那些学费。

 
今天花了一天的时间用Python实现了7种排序算法，刚开始的时候觉得非常乱，完全不知道怎么写。不过写着写着思路就变得清晰了，对于排序算法的理解也越发清晰了，好像脑子里有一排数字在比来比去、移来移去，真的是非常有意思。真得感叹一声，抽象能力真的是软件工程师的必备能力啊！
 
排序算法的本质其实是数字的各种比较方式和移动方式。回到我们大一C语言求一个数组中的最大数和最小数的那门上机课上。其实现原理很简单，就是把第一个数字作为初始数字跟后面的数字依次比较，若后面的数字比它大就跳过，若比它小就拿后面的数字替换掉它，直到遍历这个数组结束，最后得出的这个数就是最小数。
  1. def the_min_of_lists ( lists ):
  2. min = lists [ 0 ]
  3. for i in range ( 1 , len ( lists )):
  4. if min > lists [ i ]:
  5. min , lists [ i ] = lists [ i ], min
  6. return min
 
  • 冒泡排序（bubble_sort）
          冒泡排序可以把排序的变化过程想象成气泡从水中升起一样，非常的富有美感。谁有程序员没有审美的？     
         上面我们通过拿第一个数跟后面的依次比较，最后得出了最小数。如果我们用同样的方法从剩余的数组中拿出第二小的数，拿出第三小的数，这样我们不就完成了数组的排序么？理一下思路，我们需要两层循环。
  1. def bubble_sort ( lists ):
  2. count = len ( lists )
  3. for i in range ( 0 , count ):
  4. for j in range ( i + 1 , count ):
  5. if lists [ i ] > lists [ j ]:
  6. lists [ i ], lists [ j ] = lists [ j ], lists [ i ]
  7. return lists
 
  • 插入排序（insert_sort）
         在玩扑克的时候我们通常会选择把抽到的牌插入到合适的位置，这样就可以保证在抽牌结束之后我们手中的牌是呈序列显示。借鉴此思路，我们可以拿当前的数与排序好的数组比较，若比已排好的数组中的数值小，则已排的数值后移，继续比较，指到遇到比已拍好的数值小的，则将其放入即可。后续重复进行此操作。
  1. def insert_sort ( lists ):
  2. for i in range ( 1 , len ( lists )):
  3. key = lists [ i ]
  4. j = i - 1
  5. while j >= 0 :
  6. if key < lists [ j ]:
  7. # key = lists[j] #这样写会改变key的值，在插入排序的过程中，key值保持不变
  8. # lists[j+1] = lists[j]
  9. lists [ j + 1 ] = lists [ j ]
  10. lists [ j ] = key
  11. j -= 1
  12. return lists
  • 快速排序（quick_sort）
         快速排序运用了典型的分治、递归的思想实现排序。取数组第一个数作为一个标准，拿数组的值依次跟它比较，比它小的就放在它的左边，比它大的就放在它的右边，此时这个标准数在排序后的数组中的位置就确定了。左右两边的数组采取上述相同的办法即可。
  1. def quick_sort ( lists , left , right ):
  2. if left > right :
  3. return lists
  4. low , high = left , right
  5. key = lists [ left ] #key即是标准数
  6. while left < right :
  7. while left < right and lists [ right ] >= key :
  8. right -= 1
  9. lists [ left ] = lists [ right ]
  10. while left < right and lists [ left ] <= key :
  11. left += 1
  12. lists [ right ] = lists [ left ]
  13. lists [ right ] = key
  14. quick_sort ( lists , low , left - 1 )
  15. quick_sort ( lists , right + 1 , high )
  16. return lists
 
  • 选择排序（select_sort）
         选择排序跟冒泡排序非常相似，冒泡排序是每次如果比它小就会交换位置，而选择排序不会马上交换位置，而是将比它小的数字的位置保存下来，直到循环结束后才交换位置。
  1. def select_sort ( lists ):
  2. count = len ( lists )
  3. for i in range ( 0 , count ):
  4. min = i
  5. for j in range ( i + 1 , count ):
  6. if lists [ min ] > lists [ j ]:
  7. min = j
  8. lists [ min ], lists [ i ] = lists [ i ], lists [ min ]
  9. return lists
 
  • 归并排序（merge_sort）(此命名应包含递归和合并的意思)
         归并排序将数组分成两个已排好的数组，拿这个两个数组的数字依次比较，比较小的那个就放到新的数组中，这样就完成了排序。关键算法部分是如果比较的过程。
  1. #归并排序用两个已拍好的序列比较排序，采用递归的方式实现
  2. def merge_sort ( lists ):
  3. if len ( lists ) < 2 :
  4. return lists
  5. num = len ( lists )/ 2
  6. left = merge_sort ( lists [: num ])
  7. right = merge_sort ( lists [ num :])
  8. return merge ( left , right )
  10. def merge ( left , right ):
  11. i , j = 0 , 0
  12. result =[]
  13. while i < len ( left ) and j < len ( right ):
  14. if left [ i ] < right [ j ]:
  15. result . append ( left [ i ])
  16. i += 1
  17. else :
  18. result . append ( right [ j ])
  19. j += 1
  20. result += left [ i :] #若比较结束，将尚未比较完的那组加到result的后面
  21. result += right [ j :]
  22. return result
 
  • 希尔排序(shell_sort)
         希尔排序是插入排序的一种优化形式，由shell提出，故命名为shell。其核心思想为每隔一个增量去取数组中的元素，将这些元素组成一个新的数组，对这个数组使用插入排序算法。然后依次减小这个增量继续执行上述操作，这些待增量等于1时，这个数组就会变得有序。
  1. def shell_sort ( lists ):
  2. gap = 2
  3. group = len ( lists )/ gap
  4. while group > 1 :
  5. for i in range ( 0 , group ):
  6. j = i + group
  7. while j < len ( lists ):
  8. k = j - group
  9. key = lists [ j ]
  10. while k >= 0 :
  11. if key < lists [ k ]:
  12. lists [ k + group ] = lists [ k ]
  13. lists [ k ] = key
  14. k -= group
  15. j += group
  16. group /= gap
  17. return lists
 
  • 堆排序(heap_sort)
         堆排序是利用了最大堆的性质来进行排序的，即父节点大于左右子树。而我们可以把堆看成一个完全二叉树来进行处理。首先我们要将一个数组变成堆，这是一个建堆的过程，也是算法的核心。若得到堆结构的数组，再进行排序就会变得非常简单。
  1. #堆排序分为最大堆和最小堆，是完全二叉树。
  2. def build_heap ( lists , size ):
  3. for i in range ( 0 ,( size / 2 ))[::- 1 ]:
  4. adjust_heap ( lists , i , size )
  6. def adjust_heap ( list , i , size ):
  7. lchild = 2 * i + 1
  8. rchild = 2 * i + 2
  9. max = i
  10. if i < size / 2 :
  11. if lchild < size and list [ lchild ] > list [ max ]:
  12. max = lchild
  13. if rchild < size and list [ rchild ] > list [ max ]:
  14. max = rchild
  15. if max != i :
  16. list [ max ], list [ i ] = list [ i ], list [ max ]
  17. adjust_heap ( list , max , size )
  19. def heap_sort ( lists ):
  20. size = len ( lists )
  21. build_heap ( lists , size )
  22. for i in range ( 0 , size )[::- 1 ]:
  23. lists [ 0 ], lists [ i ] = lists [ i ], lists [ 0 ]
  24. adjust_heap ( lists , 0 , i )
  • 基数排序(radix_sort)
         网上的代码实现看得不太懂。主要是用于大数的比较，将数组中的数字前面补0使之保持位数一样，再依次从最高位比较即可。
 
 
算法高度体现了人类的智慧，是每一个软件工程师都必须掌握的技能。 纸上来得终觉浅，绝知此事要躬行。在脑海中实现一遍算法，然后在纸上写出来，这样可以避免提笔忘字的尴尬，也能飞快是计算机上打出来，是一个很不错的学习算法的方法。
 
 
 



原文：http://www.cnblogs.com/fengmanlou/p/4841858.html
【说明】：本文章由站长整理发布，文章内容不代表本站观点，如文中有侵权行为，请与本站客服联系(QQ:254677821)！

相关教程推荐

其他课程推荐