排序算法

一、快速排序

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序,递归实现

def quick_sort(num_list):
    """
    快速排序
    """
    if num_list == []:
        return num_list
    smallList = []
    bigList = []
    middleElement = num_list[0]
    for i in num_list[1:]:
        if i <= middleElement:
            smallList.append(i)
        else:
            bigList.append(i)
    return quick_sort(smallList)+[middleElement]+quick_sort(bigList)

二、插入排序

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

插入排序

def insert_sort(num_list):
    """
    插入排序
    """
    for i in range(len(num_list)-1):
        for j in range(i+1, len(num_list)):
            if num_list[i]>num_list[j]:
                num_list[i],num_list[j] = num_list[j],num_list[i]
    return num_list

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Selenium 学习

    官方教程: http://selenium-python.readthedocs.org/

    lpe234
  • Spring 当一个接口多个实现时,怎么注入

    lpe234
  • 关于跨域以及Spring Boot的解决方案

    同源策略(Same origin policy)是一种约定,它是浏览器最核心也最基本的安全功能,如果缺少了同源策略,则浏览器的正常功能可能都会受到影响。可以说W...

    lpe234
  • 算法05:Golang快速排序Quick Sort

    快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较.在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常...

    mojocn
  • Python之list、tuple

    前段时间看了看Python,最近在工作中频繁使用,发现自己对Python的掌握还是不够,于是决定,好好整理一阵子关于Python的东西,如果工作当天有更好...

    AsiaYe
  • ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题

    平时我们使用ArrayList比较多,但是我们是否知道ArrayList在进行foreach的时候不能直接通过list的add或者move方法进行删除呢,

    小勇DW3
  • Python发邮件

    week
  • 算法02 七大排序之:直接选择排序和堆排序

    上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

    nnngu
  • Java设计模式之工厂模式(简单工厂模式,工厂方法模式,抽象工厂模式)

    在java中,创建一个对象最简单的方法就是使用new关键字。但在一些复杂的业务逻辑中,创建一个对象不只需要new一行代码就成了,可能需要一些列的初始化设置,或先...

    用户2409797
  • Microsoft Web Farm Framework (WFF) 2.0正式发布

    Microsoft Web Farm Framework (WFF) 2.0 是微软开发的、基于IIS 7.x的小插件,能够帮助我们轻松实现Web网站的高性能、...

    张善友

扫码关注云+社区

领取腾讯云代金券