插入排序与希尔排序

栏目: 编程工具 · 发布时间: 5年前

内容简介:插入排序(Insertion-Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。操作步骤:示例,动图演示:

插入排序(Insertion-Sort)是一种简单直观的 排序 算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

操作步骤:

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)。

示例,动图演示:

插入排序与希尔排序

Python 实现

def insertion_sort(nums):
    for i in range(len(nums)):
        tmp = nums[i]
        index = i
        while index > 0 and nums[index-1] > tmp:
            nums[index] = nums[index-1]
            index -= 1
        nums[index] = tmp
        print(nums)

时间复杂度

  • 平均时间复杂度:O(n**2)。
  • 最优时间复杂度:O(n)。
  • 最坏时间复杂度:O(n**2)。
  • 空间复杂度:O(1)。
  • 稳定性:稳定。

希尔排序

基本思路

递减增量排序算法,对 插入排序 的改进,实质是分组插入排序,又叫 缩小增量排序希尔排序 提升排序的奥秘就在于 数据元素越有序,使用插入排序效率越高

操作步骤:

插入排序
插入排序

示例,动图演示:

插入排序与希尔排序

Python 实现

def shell_sort(nums):
    step = len(nums) // 2
    while step:
        for i in range(step, len(nums)):
            print(i)
            while i >= step and nums[i - step] > nums[i]:  # 子序列执行插入排序
                nums[i], nums[i - step] = nums[i - step], nums[i]
                i -= step
        step = step // 2
    return nums

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

机器学习系统设计

机器学习系统设计

[德] Willi Richert、Luis Pedro Coelho / 刘峰 / 人民邮电出版社 / 2014-7-1 / CNY 49.00

如今,机器学习正在互联网上下掀起热潮,而Python则是非常适合开发机器学习系统的一门优秀语言。作为动态语言,它支持快速探索和实验,并且针对Python的机器学习算法库的数量也与日俱增。本书最大的特色,就是结合实例分析教会读者如何通过机器学习解决实际问题。 本书将向读者展示如何从原始数据中发现模式,首先从Python与机器学习的关系讲起,再介绍一些库,然后就开始基于数据集进行比较正式的项目开......一起来看看 《机器学习系统设计》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

html转js在线工具
html转js在线工具

html转js在线工具