开发者社区> 白头雁> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

线性排序算法(1)

简介: 排序 选择排序(适用于线性排序) 思路,2层遍历 第一步:选择最小的元素,与第一个元素交换。 第二步:从第二个元素到最后一个元素,选择最小元素,与第二元素交换 完成前两步,第1第2元素已经排好序。
+关注继续查看
排序

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

思路,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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序:选择排序(算法)
排序就是算法。   选择排序(Selection sort)是一种简单直观的排序算法。 选择排序是不稳定的排序方法。   eg:序列[9,9, 1]第一次就将第一个[9]与[1]交换,导致第一个9挪动到第二个9后面 Note:一般面试的时候才会用到选择、冒泡排序。
85 0
【算法】选择排序
【算法】选择排序
25 0
排序算法
排序之PHP实现
666 0
排序算法
因为一直在做应用开发的缘故,自大学学习了数据结构和算法后,就较少使用到算法的知识,大多使用编程语言自带的排序方法。最近项目时间相对宽裕,就想再次拾起那遗落在角落的排序算法知识。 冒泡排序是我最先接触的排序算法,记得大一老师开始讲解这个算法的时候,通过循序渐进的讲解,在最后还特地带我们对这个算法进行了简单的优化,那时感觉,原来算法是这么好玩。
1639 0
排序算法
https://en.wikipedia.org/wiki/Sorting_algorithm http://www.cnblogs.com/eniac12/p/5329396.html   Theory Computational complexity theory Big O nota...
1049 0
排序算法:选择排序
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
702 0
+关注
文章
问答
文章排行榜
最热
最新
相关电子书
更多
面试常考算法
立即下载
低代码开发师(初级)实战教程
立即下载