几种排序算法及 Python 实现

cod7ce 发布于2019-07-31 11:05 / 3044人阅读

摘要：因为直接插入排序在元素基本有序的情况下接近最好情况，效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

插入排序

def insert_sort(list):
    n = len(list)
    for i in range(1, n):
        key = list[i]
        for j in range(i-1, -1, -1):
            if list[j] > key:
                list[j+1], list[j] = list[j], key
            else:
                break
    return list
   
print(insert_sort([3, 2, 5, 1, 4]))

希尔(缩小增量)排序

算法课没有讲希尔排序，所以记录一下其思想和复杂度分析

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

时间复杂度与步长选择有关，最坏情况下 $$ O(n^2) $$
不稳定

以 gap 替换插入排序中的 1

def shell_sort(list):
    n = len(list)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n, gap):
            key = list[i]
            for j in range(i-gap, -1, -gap):
                if key < list[j]:
                    list[j+gap], list[j] = list[j], key
                else:
                    break
        gap //= 2
    return list

快排

def quick_sort(list, left, right):
    if left >= right:
        return list
    key = list[right]
    high = right - 1
    low = left
    while low <= high:
        if list[low] > key:
            list[low], list[high] = list[high], list[low]
            high -= 1
        else:
            low += 1
    list[low], list[right] = list[right], list[low]
    quick_sort(list, left, low-1)
    quick_sort(list, low+1, right)
    return list
print(quick_sort([3, 2, 5, 1, 4, 6, 8, 7], 0, 7))

堆排序

def adjust_heap(list, i, n):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if lchild < n and list[lchild] > list[max]:
        max = lchild
    if rchild < n and list[rchild] > list[max]:
        max = rchild
    if max != i:
        list[i], list[max] = list[max], list[i]
        adjust_heap(list, max, n)
        
def build_heap(list, n):
    for i in range(int(n/2)-1, -1, -1):
        adjust_heap(list, i, n)

def heap_sort(list):
    build_heap(list, len(list))
    for i in range(len(list)-1, -1, -1):
        list[0], list[i] = list[i], list[0]
        adjust_heap(list, 0, i)
    return list
list = [3, 2, 5, 1, 4, 6, 8, 7]
print(heap_sort(list))

归并排序

自顶向下的递归实现：
$$T(n)=2Tleft(frac{n}{2} ight)+O(n)$$
$$Rightarrow T(n)=O(nlog n)$$

def merge(list1, list2):
    res = []
    n, m = len(list1), len(list2)
    i, j = 0, 0
    while i < n and j < m:
        if list1[i] < list2[j]:
            res.append(list1[i])
            i += 1
        else:
            res.append(list2[j])
            j += 1
    res += list1[i:]
    res += list2[j:]
    return res

def merge_sort(list):
    n = len(list)
    if n <= 1:
        return list
    left = merge_sort(list[:n//2])
    right = merge_sort(list[n//2:])
    return merge(left, right)

GPU云服务器云服务器排序算法图解排序算法总结桶排序算法学习排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44629.html

Javag工程师成神之路（2019正式版）

摘要：结构型模式适配器模式桥接模式装饰模式组合模式外观模式享元模式代理模式。行为型模式模版方法模式命令模式迭代器模式观察者模式中介者模式备忘录模式解释器模式模式状态模式策略模式职责链模式责任链模式访问者模式。主要版本更新时间备注 v1.0 2015-08-01 首次发布 v1.1 2018-03-12 增加新技术知识、完善知识体系 v2.0 2019-02-19 结构...

Olivia 2019-08-16 15:14 评论0 收藏0
前端面试题总结（js、html、小程序、React、ES6、Vue、算法、全栈热门视频资源）

摘要：并总结经典面试题集各种算法和插件前端视频源码资源于一身的文档，优化项目，在浏览器端的层面上提升速度，帮助初中级前端工程师快速搭建项目。本文是关注微信小程序的开发和面试问题，由基础到困难循序渐进，适合面试和开发小程序。并总结vue React html css js 经典面试题集各种算法和插件、前端视频源码资源于一身的文档，优化项目，在浏览器端的层面上提升速度，帮助初中级前端工程师快...

pumpkin9 2019-08-23 17:12 评论0 收藏0
前端面试题总结（js、html、小程序、React、ES6、Vue、算法、全栈热门视频资源）

摘要：并总结经典面试题集各种算法和插件前端视频源码资源于一身的文档，优化项目，在浏览器端的层面上提升速度，帮助初中级前端工程师快速搭建项目。本文是关注微信小程序的开发和面试问题，由基础到困难循序渐进，适合面试和开发小程序。并总结vue React html css js 经典面试题集各种算法和插件、前端视频源码资源于一身的文档，优化项目，在浏览器端的层面上提升速度，帮助初中级前端工程师快...

Carson 2019-07-31 10:21 评论0 收藏0
前端面试题总结（js、html、小程序、React、ES6、Vue、算法、全栈热门视频资源）

摘要：并总结经典面试题集各种算法和插件前端视频源码资源于一身的文档，优化项目，在浏览器端的层面上提升速度，帮助初中级前端工程师快速搭建项目。本文是关注微信小程序的开发和面试问题，由基础到困难循序渐进，适合面试和开发小程序。并总结vue React html css js 经典面试题集各种算法和插件、前端视频源码资源于一身的文档，优化项目，在浏览器端的层面上提升速度，帮助初中级前端工程师快...

muzhuyu 2019-07-01 12:43 评论0 收藏0