Python实现各种排序

《Python实现各种排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、在Python实践中，我们往往遇到排序问题，比如在对搜索结果打分的排序（没有排序就没有Google等搜索引擎的存在），当然，这样的例子数不胜数。《数据结构》也会花大量篇幅讲解排序。之前一段时间，由于需要，我复习了一下排序算法，并用Python实现了各种排序算法，放在这里作为参考。最简单的排序有三种：插入排序，选择排序和冒泡排序。这三种排序比较简单，它们的平均时间复杂度均为O(n^2)，在这里对原理就不加赘述了。代码直接贴出来。插入排序：def insertion_sort(sort_list):    iter_len = len(sort_lis

2、t)    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 

3、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[

4、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]

5、mallest:                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_lis

6、t[i]　　不了解Python的同学可能会觉得奇怪，没错，这是交换两个数的做法，通常在其他语言中如果要交换a与b的值，常常需要一个中间变量temp，首先把a赋给temp，然后把b赋给a，最后再把temp赋给b。但是在python中你就可以这么写：a,b=b,a，其实这是因为赋值符号的左右两边都是元组（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。平均时间复杂度为O(nlogn)的算法有：归并排序，堆排序和快速排序。归并排序。对于一个子序列，分成两份，比较两份的第一个元素，小者弹出，然后重复这个过程。对于待排序列，

7、以中间值分成左右两个序列，然后对于各子序列再递归调用。源代码如下，由于有工具函数，所以写成了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):            if len(left)>0 and len(right)>0:                if left[0]<=rig

8、ht[0]:                    alist[i] = left.pop(0)