Python里面几种排序算法的比较,sorted的底层实现,虽然我们知道sorted的实现方式,但是却写不出这样的速度

  1. 云栖社区>
  2. 博客>
  3. 正文

Python里面几种排序算法的比较,sorted的底层实现,虽然我们知道sorted的实现方式,但是却写不出这样的速度

雁横 2018-07-21 23:28:35 浏览2152

算法与数据结构基础

原文链接:http://note.youdao.com/noteshare?id=7b9757930ce3cc9e0a5e61e4d0aa9ea2⊂=2726FFA02ADE4E74A302D8DA7646FB46

查找算法:

二分查找法:

简介:二分查找法又被称为折半查找法,用于预排序的查找问题

过程

  1. 如果在列表a中查找元素t,先将列表a中间位置的项与查找关键字t比较,如果两者相等,则成功。
  2. 否则,将表分为前后两个子表
  3. 如果中间位置大于t,则进一步查找前一子表,否则,查找后一子表
  4. 重复上述过程

优劣

  1. 时间复杂度为O(log~2~N),比较快
  2. 缺点就是必须是有序列表

排序算法:

冒泡排序

简介:两两比较大小,如果不满足升序关系,则交换

过程:略

优劣:

  1. 时间复杂度为O(N^2^),速度较慢
  2. 稳定

选择排序

简介:找出最小值,然后放入一个新的列表中

过程:略

优劣:

  1. 时间复杂度为O(N^2^),速度较慢
  2. 稳定

插入排序法

简介:依次检查需要排序的列表,每次取出一个元素放入另一个排好序的列表中的适当位置。

过程:略

优劣:

  1. 时间复杂度为O(N^2^)
  2. 速度不稳定,最佳情况为线性增长,最差情况为N^2^,所以速度实际上比前两种快

归并排序

简介:分而制之的思想

过程

  1. 将包含N个元素的列表分为两个含N/2元素的子列表.
  2. 对两个子列表递归调用归并排序(最后将两个子列表分解为N个子列表)。
  3. 合并已排序好的列表。

优劣::速度较快且稳定,时间复杂度为O(Nlog~2~N)

实现代码:

def merge(left,right):
    merged = []
    i,j = 0,0
    left_len,right_len = len(left),len(right)
    while i<left_len and j<right_len:
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged

def mergeSort(a):
    if len(a) <= 1:
        return a
    else:
        mid = len(a) // 2
        left = mergeSort(a[:mid])
        right = mergeSort(a[mid:])
        merge(left,right)
        return merge(left,right)

def main():
    a = [59,12,77,64,72,69,46,89,31,9]
    a1 = mergeSort(a)
    print(a1)

if __name__ == '__main__':
    main()

快速排序 #:

简介:对冒泡排序的改进

过程

  1. 设置两个变量i和j,作为列表首末两端的下标,即i=0,j=N-1
  2. 设置列表的第一个元素作为关键数据,即key=A[0]
  3. 从j开始向前搜索,找到第一个小于key的值A[j],将A[j]和A[i]互换
  4. 从i开始向后搜索,找到第一个大于key的值A[i],将A[i]和A[j]互换
  5. 重复3~4步,直到i = j

优劣:

  1. 平均情况时间复杂度为O(Nlog~2~N),比较快。
  2. 最差情况下时间复杂度为O(N^2^)

Python语言中提供的排序算法

内置数据类型list的方法sort(),内置函数sorted()

这个的底层实现就是归并排序,只是使用了Python无法编写的底层实现,从而避免了Python本身附加的大量开销,速度比我们自己写的归并排序要快很多(10~20倍),所以说我们一般排序都尽量使用sorted和sort