专栏首页python编程军火库AI_第一部分 数据结构与算法(11.排序算法实战上)

AI_第一部分 数据结构与算法(11.排序算法实战上)

第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

1.对开发中常见的算法能应用自如,让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮,我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

hello,大家好,今天开始我们一起聊聊排序算法中比较基础的三种排序算法:冒泡排序,插入排序,选择排序。

为何要把这三个排序放在一起来说呢?主要是基于其时间复杂度都是一致的O(n^2).

第一、冒泡排序

冒泡排序是在大学的时候或者你去看排序算法的时候最早接触的一种排序方法,其思路是怎么样的呢?

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

通过以上的描述,不知各位是否能get到一些点,1.需要做n的轮询2.每次都是比较两个元素,3.每轮询一次就会有一个元素到达最终的位置。

好的,没有代码我们只是这样说还是比较理论的,我现在给出大家python版本的冒泡排序:

# 冒泡排序
def bubble_sort(a):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):  # 循环的次数
        made_swap = False
        for j in range(length - i - 1):  # 每次循环比较的次数
            if a[j] > a[j + 1]:  # 前一个比后一个大交换位置(升序的方式【排列)
                a[j], a[j + 1] = a[j + 1], a[j]
                made_swap = True  # 交换成功标志位
        if not made_swap:  # 若交换标志位为False时候表示序列已经是升序
            break

第二、插入排序

开始插入排序之前我们可以先来思考一个问题:对于一个有序的数组,我们往里面添加一个新数据之后,如何保持这个数组是有序的呢?我们一般的思路就是:遍历数组找到其该插入的位置,把数据插入不就完了吗。

这是一个动态排序的过程,即动态地往有序集合中添加数据,我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据,我们也可以借鉴上面讲的插入方法,来进行排序,于是就有了插入排序算法。

如何借鉴此思路来实现插入排序的呢?我们来看一下插入排序的整个过程:

首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。

插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

好的,我们还是通过代码来看看插入排序是如何实现的。

# 插入排序(分已排序区和未排序区域)
def insertion_sort(a):
    length = len(a)
    if length <= 1:
        return
    # 为何从下标1开始?插入排序会把数据分成已近排序部分和未排序部分(下标为0的认为是已排序的部分,其余是未排序的部分)
    for i in range(1, length):
        value = a[i]
        j = i - 1
        while j >= 0 and a[j] > value:  # (是一种从有序数据部分最后开始向前比较的过程) 已经排序的数据部分与目前要排序的value进行循环大小比较
            a[j + 1] = a[j]  # 有序的最后一位向后移动一位
            j -= 1  # 下标向前在此比较
        a[j + 1] = value  # 已经排序部分的值

第三、选择排序

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

好的,介绍完思想我们就先看一下其代码实现:

# 选择排序(分已排序区域和未排序区域)
def selection_sort(a):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        min_index = i  # 最小值索引下标
        min_val = a[i]  # 最小值
        for j in range(i, length):  # 从剩余的数据中找最小数据
            if a[j] < min_val:
                min_val = a[j]  # 找到未排序中最小的元素
                min_index = j  # 找到未排序中最小元素对应的下标

        a[i], a[min_index] = a[min_index], a[i]  # 每经过一次i 就会有一个元素已经排序完成

好的,本期我们就说完了排序算法中最基础的三种排序,下期中我们会聊到比较烧脑的归并排序和快排。本期的完整代码请访问我的github自行获取。地址

https://github.com/haishiniu/Data-Structure-and-Algorithms/tree/master/sorted

本文分享自微信公众号 - python编程军火库(PythonCoder1024),作者:还是牛

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

原始发表时间:2019-04-15

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AI_第一部分 数据结构与算法(10.排序简介)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • 5分钟面试指南(第十二篇 面向对象相关)

    本部分我们会为大家提供一些python初级工程师在面试过程中遇到的常见的面试题目,期望达到的效果:

    还是牛6504957
  • 5分钟面试指南(第三篇 编码让我头大)

    本部分我们会为大家提供一些python初级工程师在面试过程中遇到的常见的面试题目,期望达到的效果:

    还是牛6504957
  • 视觉直观感受 7 种常用的排序算法

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

    后端技术探索
  • 视觉直观感受 7 种常用的排序算法

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

    慕白
  • 视觉直观感受 7 种常用排序算法

    大数据文摘
  • 不稳定的原地排序算法:选择排序

    在之前的文章中,我们说了两个原地排序算法:插入排序和冒泡排序。分析两个算法的原理,也用代码实现了两个算法。最后,我们也从两个算法入手,引出了评价算法性能的两个重...

    飞翔的竹蜻蜓
  • 排序算法(九):桶排序

    桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

    zhipingChen
  • 经典排序算法详细介绍

    渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    IT茂茂
  • 涨姿势,图文带你了解 8 大排序算法

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    Java技术栈

扫码关注云+社区

领取腾讯云代金券