首页 > 编程语言 > 详细

各种排序算法的Python实现。

时间：2015-09-27 10:00:58      阅读：456      评论：0      收藏：0      [点我收藏+]

大学的算法导论课确实是混过去的，到了毕业的时候结果连个冒泡排序都不能裸写出来，只记得一些算法的基本理论，如分治法、递归、动态规划、回溯、图论、时间空间理论这些。大概知道这些排序算法的实现原理，真在纸上写出来脑子又是一团浆糊。最近在网上看到九章算法的网络课程费用是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使之保持位数一样，再依次从最高位比较即可。
 
 
算法高度体现了人类的智慧，是每一个软件工程师都必须掌握的技能。 纸上来得终觉浅，绝知此事要躬行。在脑海中实现一遍算法，然后在纸上写出来，这样可以避免提笔忘字的尴尬，也能飞快是计算机上打出来，是一个很不错的学习算法的方法。
 
 
 





各种排序算法的Python实现。

原文：http://www.cnblogs.com/fengmanlou/p/4841858.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！