线性排序算法(1)

排序

选择排序(适用于线性排序)

思路,2层遍历

  1. 第一步:选择最小的元素,与第一个元素交换。
  2. 第二步:从第二个元素到最后一个元素,选择最小元素,与第二元素交换
  3. 完成前两步,第1第2元素已经排好序。继续遍历。

算法复杂度 O(n^2)

def SelectionSort(a):
    for i in range(len(a)):
        tmp_min = a[i]
        index = i
        for j in range(i,len(a)):
            if a[j]<tmp_min:
                index = j
                tmp_min = a[j]
        tmp = a[i]
        a[i] = a[index]
        a[index] = tmp

插入排序(适用于线性排序)

思路,2层遍历

  1. 第一步:第二元素向前遍历,如果第一个元素比自己大,与第一个元素交换位置
  2. 第二步:从第三个元素到最后一个元素,向前遍历,如果前一个元素比自己大,就交换位置;
  3. 遍历过程中,如果发现前一个元素比自己小,结束遍历。

由于在遍历过程中,当出现前一个元素小于当前元素,提前结束比对,比选择排序算法的比对次数少。

算法复杂度 O(n^2)

def swap(a,i,j):
    tmp  = a[i]
    a[i] = a[j]
    a[j] = tmp
def InsertionSort(a):
    for i in range(1,len(a)):
        for j in range(i,0,-1):
            if(a[j-1]>a[j]):
                swap(a,j-1,j)
            else:
                break

用赋值替换swap,对InsertionSort优化

def InsertionSortCopy(a):
    for i in range(1,len(a)):
        for j in range(i,0,-1):
            tmp = a[j]
            if(a[j-1]>tmp):
                a[j] = a[j-1]
            else:
                a[j] = tmp

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吾爱乐享

java学习之数组元素排序,冒泡排序和选择排序

12140
来自专栏java 成神之路

JAVA对象在JVM中内存分配

369120
来自专栏用户2442861的专栏

Java基础之String中equals,声明方式,等大总结

    转载请注明出处:http://blog.csdn.net/dmk877/article/details/49420141 

9020
来自专栏nnngu

018 final 关键字的用途

final关键字的含义 final在Java中是一个保留的关键字,可以声明成员变量、方法、类以及本地变量。一旦你将引用声明作final,你将不能改变这个引用了,...

36060
来自专栏IT可乐

深入理解计算机系统(3.8)------数组分配和访问

  上一篇博客我们讲解了汇编语言中过程(函数)的调用实现。理解数据如何在调用者和被调用者之间传递,以及在被调用者当中局部变量内存的分配以及释放是最重要的。那么这...

224100
来自专栏梧雨北辰的开发录

Swift学习:构造器(下)

本篇主要介绍Swift中构造器的一些特殊用法 一、可失败的构造器 顾名思义,这是用于我们构造过程可能失败情况的构造器。失败的原因可能是给构造器传入无效的参数值,...

28070
来自专栏Java技术栈

Java中的宏变量,宏替换详解。

群友在微信群讨论的一个话题,有点意思,特拿出来分享一下。 ? 输出true false 来看下面这段程序,和群友分享的大致一样。 public static ...

45450
来自专栏Hongten

python开发_python中str.format()

20420
来自专栏C/C++基础

CC++变参函数

C语言中,有时需要变参函数来完成特殊的功能,比如C标准库函数printf()和scanf()。C中提供了省略符“…”能够帮主programmer完成变参函数的书...

9710
来自专栏AI研习社

最常见的 35 个 Python 面试题及答案(2018 版)

作为一个 Python 新手,你必须熟悉基础知识。在本文中我们将讨论一些 Python 面试的基础问题和高级问题以及答案,以帮助你完成面试。包括 Python ...

86530

扫码关注云+社区

领取腾讯云代金券