专栏首页Python乱炖几种基础排序算法的python实现

几种基础排序算法的python实现

最近利用晚上闲下来的时间整理了一些基础的排序算法,这些排序算法一般的就是在学习数据结构的时候都是要求掌握的,作为一个开发者来说,会排序那是最基础的技能,也是最重要的技能,下面我们就一起来看看吧!

插入排序

插入排序思想:每一趟将一个待排序元素,按其排序码大小插入到前面已经排好序的一组元素的适当位置上,直到所有待排序元素元素全部插入为止

思路:

假定前i个构成的子序列是处于已排序的情况下进行排序的,然后将第i个元素与前i个构成的子序列逆序进行比较,如果是要升序排序,则比较第i个元素是否比j=i-1(i-1需要>=0)的元素大,如果是则第i个元素的位置(即j+1的位置上)保持不动,反之则将j=i-1的元素放置到i的位置,再进行第i个元素与j=i-2(i-2需要>=0)的,依次进行,如果第i个元素刚好比j=i-3大,则将第i个元素插入到j=i-2(即j+1的位置)上。

代码:

def insertion_sort(a):
    l = len(a)
    j = 0
    for i in range(1, l):
        temp = a[i]
        for j in range(i - 1, -1, -1):
            if temp < a[j]:  # 如果第i个元素大于前i个元素中的第j个
                a[j + 1] = a[j]  # 则第j个元素先后移1位
            else:  # 如果第i个元素小于等于前i个元素中的第j个则结束循环
                break
        a[j + 1] = temp  # 将i个元素赋值给空着的位置
    for i in range(0, l):
        print(a[i])

快速排序

思路:

任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]互换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)

代码,使用递归算法来实现:

def quick_sort(arr, low, high):
    # temp = a[0]
    i = low
    j = high
    if i >= j:
        return arr
    temp = arr[i]
    while i < j:
        while i < j and arr[j] >= temp:
            j = j - 1
        arr[i] = arr[j]
        while i < j and arr[i] <= temp:
            i = i + 1
        arr[j] = arr[i]
    arr[i] = temp
    quick_sort(arr, low, i - 1)
    quick_sort(arr, j + 1, high)
    return arr

冒泡排序

思路:

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码:

def bubble_sort(arr):
    length = len(arr)
    while length > 0:
        for i in range(length - 1):
            if arr[i] > arr[i + 1]:
                arr[i] = arr[i] + arr[i + 1]
                arr[i + 1] = arr[i] - arr[i + 1]
                arr[i] = arr[i] - arr[i + 1]
        length -= 1

选择排序

思路:

每一趟从待排序的数据元素中选出最小(最大)的元素,顺序放在待排序的数列最前,直到全部待排序的数据元素全部排完。

例子: [4, 2, 3] 找出最小的:2,与第一个元素交换 [2, 4, 3] 找出最小的:3,与第二个元素交换 [2, 3, 4]

代码:

def selection_sort(a):    
    for j in range(0,len(a)-1):
        count = j  #记录最小元素下标
        #每次找出最小元素
        for i in range(j,len(a)-1):
            if a[count] > a[i+1]:
                count = i+1
            #python特有的交换值方法,交换最小元素和待排序元素中最前一个
        a[j], a[count] = a[count], a[j]
    for i in range(0,len(a)):
            print(a[i])

堆排序

先介绍一下堆,堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

思路:

将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。

在排序之前我们需要构造一个大顶堆,之后再使用堆排序

代码:

def adjustHead(a, i, l):
    temp = a[i] #取出当前元素
    k = 2*i + 1 #从左子节点开始,即2*i+1
    while k < l:
        if k+1 < l & a[k] < a[k+1]: #若果左子节点小于右子节点,k指向右子节点
            k=k+1
        if a[k] > temp: 
            a[i] = a[k]
            i = k
        else:
            break
        k = 2*k + 1 #把该节点当作父节点,继续操作
    a[i] = temp #将父节点值赋值给该子节点


def heap_sort(arr):
    l = len(arr)
    for i in range(int(l/2-1), -1, -1):
        adjustHead(arr,i,l)
      # 交换堆顶和最后一个元素,并调整堆结构
    for j in range(l-1, 0, -1):
        arr[0], arr[j] = arr[j], arr[0] #将堆顶元素和末尾元素进行交换
        adjustHead(arr, 0, j) #重新对对进行调整
    for k in range(0,l):
        print(arr[k])

基数排序

基数排序又称为“桶子法”,从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列,再将这个序列按照次低位的大小进入相应的桶中,一直排到最高位为止,数组排序完成。

思路:

(1)遍历序列找出最大的数(为的是确定最大的数是几位数);

(2)开辟一个与数组大小相同的临时数组tmp;

(3)用一个count数组统计原数组中某一位(从低位向高位统计)相同的数据出现的次数;

(4)用一个start数组计算原数组中某一位(从最低位向最高位计算)相同数据出现的位置;

(5)将桶中数据从小到大用tmp数组收集起来;

(6)重复(3)(4)(5)直到所有位都被统计并计算过,用tmp收集起来;

(7)将tmp数组拷回到原数组中;

代码:

import math

def radix_sort(arr):
    radix = 10 #基数
    # k可以表示任意整数
    k = int(math.ceil(math.log(max(arr),radix)))
    #math.log对arr中最大的数取对数,log(max(arr),10),并对其取整得到最大值的位数
    bucket =[[] for i in range(radix)]
    for i in range(1, k+1):
        for  value in arr:
            # 析取整数第k位数字(从低到高)10**2位10的二次方
            bucket[int(value%(radix**i)/(radix**(i-1)))].append(value) 
        del arr[:]
        for each in bucket:
            arr.extend(each) #桶合并
        bucket = [[]for i in range(radix)]

本文分享自微信公众号 - Python乱炖(Cooking_python),作者:我被狗咬了

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python基础知识点

    前一段时间一直有人私信我(我的文章还不支持评论),说有没有完整一点的教程,想要系统的过一下,我说有啊,我下次就发。

    我被狗咬了
  • Gevent----非官方的python协程库

    gevent是一个基于libev的并发库。它为各种并发和网络相关的任务提供了整洁的API。 嗯,确实很简洁,很易使用。待会我们就见识到了。 同步IO 我们知道对...

    我被狗咬了
  • Python代码覆盖率分析工具----Coverage

    在测试中,为了度量产品质量,代码覆盖率被作为一种测试结果的评判依据,在Python代码中用来分析代码覆盖率的工具当属Coverage。代码覆盖率是由特定的测试套...

    我被狗咬了
  • 八大排序算法总结与java实现

    概述 因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法: ? 请点...

    企鹅号小编
  • 零基础python教程—python数组

    在学习Python过程中数组是个逃不过去的一个关,既然逃不过去咱就勇敢面对它,学习一下python中数组如何使用。

    小小科
  • PHP算法——四大基础算法

    对于大多数业务开发来说,平时很少需要自己实现数据结构与算法,都是利用已经封装好的现成接口,类库来推测、翻译业务逻辑,但是,不需要自己实现,并不代表什么都不需要了...

    猿哥
  • 我不知道你知不知道但前端NEXT知道的伪元素小技巧

    腾讯NEXT学位
  • CSS基础布局

    lesM10
  • 程序员那些必须掌握的排序算法(上)

    现在的IT行业并不像以前那么好混了,从业人员过多,导致初级程序员过剩,这也间接导致了公司的招聘门槛越来越高,要求程序员掌握的知识也越来越多。 算法也是一个争论...

    wangweijun
  • 怀英漫谈9 - JS 数组

    所谓的数组,就是一些数据的集合,JS中没有集合的概念,所以集合也是数组的一种。如果你Java用的多,那么这个概念就有点儿难以理解,毕竟从Java的文意来说,集合...

    用户1335799

扫码关注云+社区

领取腾讯云代金券