Python的排序方式总结


from https://github.com/Tony-CCIE/Python_Sort 自己也是python初学者,这是从一个学长的github总结的,也是个人为数不多的不算太水的东西,希望社区能越来越热闹吧=。=

Table of Contents - Python编写的排序总结 - 1 插入排序 - 2 希尔排序 - 3 冒泡排序 - 4 快速排序 - 5 合并排序 - 6 选择排序

Python编写的排序总结

1 插入排序

描述

每次假设前面的元素都是已经排好序了的,然后将当前位置的元素插入到原来的序列中,为了尽快地查找合适的插入位置,可以使用二分查找。时间复杂度$O(n^2)$,别误以为二分查找可以降低它的复杂度,因为插入排序还需要移动元素的操作!

代码实现

 def insertion_sort(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        position = index
        while position > 0 and a_list[position - 1] > current_value:
            a_list[position] = a_list[position - 1]
            position = position - 1
        a_list[position] = current_value


def insertion_sort_binarysearch(a_list):
    for index in range(1, len(a_list)):
        current_value = a_list[index]
        position = index
        low=0
        high=index-1
        while low<=high:
            mid=(low+high)/2
            if a_list[mid]>current_value:
                high=mid-1
            else:
                low=mid+1
        while position > low:
            a_list[position] = a_list[position - 1]
            position = position -1
        a_list[position] = current_value


a_list = [54, 26, 93, 15, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print(a_list)
insertion_sort_binarysearch(a_list)
print(a_list)

2 希尔排序

描述

类似合并排序和插入排序的结合体,二路合并排序将原来的数组分成左右两部分,希尔排序则将数组按照一定的间隔分成几部分,每部分采用插入排序来排序,有意思的是这样做了之后,元素很多情况下就差不多在它应该呆的位置,所以效率不一定比插入排序差。时间复杂度为$[O(n),O(n^2)]$。

代码实现

def shell_sort(a_list):
    #how many sublists, also how many elements in a sublist
    sublist_count = len(a_list) // 2
    while sublist_count > 0:
        for start_position in range(sublist_count):
            gap_insertion_sort(a_list, start_position, sublist_count)
        print("After increments of size", sublist_count, "The list is", a_list)
        sublist_count = sublist_count // 2

def gap_insertion_sort(a_list, start, gap):
    #start+gap is the second element in this sublist
    for i in range(start + gap, len(a_list), gap):
        current_value = a_list[i]
        position = i
        while position >= gap and a_list[position - gap] > current_value:
            a_list[position] = a_list[position - gap] #move backward
            position = position - gap
            a_list[position] = current_value


a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20, 88]
shell_sort(a_list)
print(a_list)

3 冒泡排序

描述

每个回合都从第一个元素开始和他后面的元素比较,如果比它后面的元素更大的话就交换,一直重复,直到这个元素到了它能到达的位置。每次遍历都将剩下的元素中最大的那个放到了序列的“最后”(除去了前面已经排好的那些元素)。注意检测是否已经完成了排序,如果已完成就可以退出了。时间复杂度O(n^2)。

python支持对两个数字同时进行交换a,b = b,a就可以交换a和b的值了。

代码实现

def short_bubble_sort(a_list):
    exchanges = True
    pass_num = len(a_list) - 1
    while pass_num > 0 and exchanges:
        exchanges = False
        for i in range(pass_num):
            if a_list[i] > a_list[i + 1]:
                exchanges = True
                # temp = a_list[i]
                # a_list[i] = a_list[i + 1]
                # a_list[i + 1] = temp
                a_list[i],a_list[i+1] = a_list[i+1], a_list[i]
        pass_num = pass_num - 1


if __name__ == '__main__':
    a_list=[20, 40, 30, 90, 50, 80, 70, 60, 110, 100]
    short_bubble_sort(a_list)
    print(a_list)
 ```

## 4 快速排序

描述

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

代码实现

def quick_sort(lists, left, right): # 快速排序 if left >= right: return lists key = lists[left] low = left high = right while left < right: while left < right and lists[right] >= key: right -= 1 lists[left] = lists[right] while left < right and lists[left] <= key: left += 1 lists[right] = lists[left] lists[right] = key quick_sort(lists, low, left - 1) quick_sort(lists, left + 1, high) return lists

## 5 合并排序

描述

典型的是二路合并排序,将原始数据集分成两部分(不一定能够均分),分别对它们进行排序,然后将排序后的子数据集进行合并,这是典型的分治法策略。时间复杂度$O(nlogn)$

![](http://interactivepython.org/courselib/static/pythonds/_images/mergesortA.png)

![](http://interactivepython.org/courselib/static/pythonds/_images/mergesortB.png)

代码实现

def mergeSort(alist): print("Splitting ",alist) if len(alist)>1: mid = len(alist)//2 lefthalf = alist[:mid] righthalf = alist[mid:]

    mergeSort(lefthalf)
    mergeSort(righthalf)

    i=0
    j=0
    k=0
    while i < len(lefthalf) and j < len(righthalf):
        if lefthalf[i] < righthalf[j]:
            alist[k]=lefthalf[i]
            i=i+1
        else:
            alist[k]=righthalf[j]
            j=j+1
        k=k+1

    while i < len(lefthalf):
        alist[k]=lefthalf[i]
        i=i+1
        k=k+1

    while j < len(righthalf):
        alist[k]=righthalf[j]
        j=j+1
        k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20] mergeSort(alist) print(alist)

## 6 选择排序

描述

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

![](http://interactivepython.org/courselib/static/pythonds/_images/selectionsortnew.png)

代码实现

def selectionSort(alist): for fillslot in range(len(alist)-1,0,-1): positionOfMax=0 for location in range(1,fillslot+1): if alist[location]>alist[positionOfMax]: positionOfMax = location

   temp = alist[fillslot]
   alist[fillslot] = alist[positionOfMax]
   alist[positionOfMax] = temp

alist = [54,26,93,17,77,31,44,55,20] selectionSort(alist) print(alist)

```

  • 12 条回复 | 3 人参与
  • cosven # 1

    看到这个文章,想起一个事

    能不能单独弄一个发文章的版块啊 ~ @追梦人物

  • cosven # 2

    现在的这种排版:正文板块宽度貌似是固定的(大概 7/800px),对于文章这种篇幅长的内容来讲,有点窄了。

    感觉不是很适合看文章 (个人想法)

  • @cosven 你们有一些博客文章需要发布么?想集成一个文章发布系统的,不过目前还没上线。在工具资源或者项目分享里开一个 Blog 分类怎么样?

  • @cosven 是的,论坛的建设初衷不是用来发博客文章的,到时候会有专门的博客系统上线。主要还是希望大家能够讨论一些 python 的问题。分享一些好玩的项目,以及自己的作品。

  • cosven # 6

    @追梦人物 感觉作为一个 Python 论坛,有文章/技术分享版块应该挺正常,也有这个需求,就看怎么弄了。

    一般来说,文章和分享应该比讨论技术性更强,更正式一点。我觉得这个内容应该很重要。(如果站长也这么觉得的话。)

    另外就是,我觉得重要的东西一定要有 排行榜 。(就是要有个机制去鼓励大家在这种重要的版块创作)

    想想当年的 oschina 的代码分享版块,各种神器,但是没了排行榜,也就没了方便入口,个人就没怎么关注过了。

    具体怎么弄,我倒觉得弄一个文章的版块就好了。但是这个版块有热点排序啥的...

  • cosven # 7

    @追梦人物 我倒是没有发文章的需求。但是一些_同学_可能有。

    比如他们想要分享一些自己或者在其他地方发现的优质内容。一些篇幅长的东西往往不适用于这种论坛形式。

    不过站长可以根据站点定位,优先级开发啊

  • @cosven 嗯,非常同意你的说法。排行榜在考虑范围内,不过具体的产品设计还要更加细致的规划。目前我在考虑把全站迁移到 https 以及做开源准备所以没有添加什么新的功能特性。现在这个功能确实比较基础。如果有兴趣热烈欢迎参与到产品的设计中来。

  • cosven # 9

    @追梦人物 个人倒认为,上 https 不是那么紧急?上 https 也可能会有许多坑,虽然我也不知道坑在哪里... 开源,感觉不错 ~ 就是邀请爱好Python的朋友来论坛增加一点干货,感觉在目前应该挺重要紧急的? 对这个产品的设计,我也挺感兴趣的,不过感觉给不出什么建设性的意见。 话说有什么聊天群之类的么?

  • @cosven 暂时还没有,到时候建一个产品建议群。

  • cosven # 11

    @追梦人物 多嘴一句,感觉产品建议群一定不要选 QQ 微信啥的...

    个人推荐 slack 或者 irc

  • 嗯,这些我好像都没有过,研究研究。@cosven

添加一条新回复
登录 或者 注册 后发表回复