Python实现各种排序.docVIP

在Python实践中，我们往往遇到排序问题，比如在对有哪些信誉好的足球投注网站结果打分的排序（没有排序就没有Google等有哪些信誉好的足球投注网站引擎的存在），当然，这样的例子数不胜数。《数据结构》也会花大量篇幅讲解排序。之前一段时间，由于需要，我复习了一下排序算法，并用Python实现了各种排序算法，放在这里作为参考。 最简单的排序有三种：插入排序，选择排序和冒泡排序。这三种排序比较简单，它们的平均时间复杂度均为O(n^2)，在这里对原理就不加赘述了。代码直接贴出来。 插入排序： def?insertion_sort(sort_list): ????iter_len?=?len(sort_list) ????if?iter_len ?2: ????????return?sort_list ????for?i?in?range(1, iter_len): ????????key?=?sort_list[i] ????????j?=?i?-?1 ????????while?j=0?and?sort_list[j]key: ????????????sort_list[j+1]?=?sort_list[j] ????????????j?-=?1 ????????sort_list[j+1]?=?key ????return?sort_list 　　 冒泡排序： def?bubble_sort(sort_list): ????iter_len?=?len(sort_list) ????if?iter_len ?2: ????????return?sort_list ????for?i?in?range(iter_len-1): ????????for?j?in?range(iter_len-i-1): ????????????if?sort_list[j] sort_list[j+1]: ????????????????sort_list[j], sort_list[j+1]?=?sort_list[j+1], sort_list[j] ????return?sort_list 　　 选择排序： def?selection_sort(sort_list): ????iter_len?=?len(sort_list) ????if?iter_len ?2: ????????return?sort_list ????for?i?in?range(iter_len-1): ????????smallest?=?sort_list[i] ????????location?=?i ????????for?j?in?range(i, iter_len): ????????????if?sort_list[j] smallest: ????????????????smallest?=?sort_list[j] ????????????????location?=?j ????????if?i !=?location: ????????????sort_list[i], sort_list[location]?=?sort_list[location], sort_list[i] ????return?sort_list 　　 这里我们可以看到这样的句子： sort_list[i], sort_list[location]?=?sort_list[location], sort_list[i] 　　 不了解Python的同学可能会觉得奇怪，没错，这是交换两个数的做法，通常在其他语言中如果要交换a与b的值，常常需要一个中间变量temp，首先把a赋给temp，然后把b赋给a，最后再把temp赋给b。但是在python中你就可以这么写：a, b = b, a，其实这是因为赋值符号的左右两边都是元组（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。 平均时间复杂度为O(nlogn)的算法有：归并排序，堆排序和快速排序。 归并排序。对于一个子序列，分成两份，比较两份的第一个元素，小者弹出，然后重复这个过程。对于待排序列，以中间值分成左右两个序列，然后对于各子序列再递归调用。源代码如下，由于有工具函数，所以写成了callable的类： class?merge_sort(object): ????def?_merge(self, alist, p, q, r): ????????left?=?alist[p:q+1] ????????right?=?alist[q+1:r+1] ????????for?i?in?range(p, r+1): ??????