各种排序算法的Python实现。

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了各种排序算法的Python实现。，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4512字，纯文字阅读大概需要7分钟。

内容图文

大学的算法导论课确实是混过去的，到了毕业的时候结果连个冒泡排序都不能裸写出来，只记得一些算法的基本理论，如分治法、递归、动态规划、回溯、图论、时间空间理论这些。大概知道这些排序算法的实现原理，真在纸上写出来脑子又是一团浆糊。最近在网上看到九章算法的网络课程费用是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使之保持位数一样，再依次从最高位比较即可。

 

 

算法高度体现了人类的智慧，是每一个软件工程师都必须掌握的技能。 纸上来得终觉浅，绝知此事要躬行。在脑海中实现一遍算法，然后在纸上写出来，这样可以避免提笔忘字的尴尬，也能飞快是计算机上打出来，是一个很不错的学习算法的方法。

 

 

 

来自为知笔记(Wiz)

原文：http://www.cnblogs.com/fengmanlou/p/4841858.html

内容总结

以上是互联网集市为您收集整理的各种排序算法的Python实现。全部内容，希望文章能够帮你解决各种排序算法的Python实现。所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---