级别: ★☆☆☆☆
作者: MrLiuQ https://www.jianshu.com/u/6663b66c3df3
审校: QiShare 团队 https://www.jianshu.com/c/b3bd94559163
本篇将重点介绍选择排序, 在讲解选择排序之前, 我们先复习一下数组和链表等知识.
一, 数组 or 链表?
数组和链表作为常用的存储数据结构, 有各自的优势与劣势.
数组的优势在于查询速度快.
链表的优势在于插入与删除速度快.
下面是两者的时间复杂度:
/ | 数组 | 链表 |
---|---|---|
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |
为什么呢? 这与数组与链表的存储方式有关.
数组是顺序存储, 而链表是链式存储.
顺序存储: 所存储的内存区域是连续的.
链式存储: 所存储的内存区域是非连续的.
举个例子: 图解一下
因此, 当我们所存储的数据经常查询, 则选择数组好一些. 如果我们的数据经常被操作, 并且数据长度经常发生变化, 则选择链表好一些.
关于数组的内存存储还有几个小知识点:
对于不可变数组来说, 每一次重新赋值都是一次内存整体迁移, 相当于开辟了一块新内存存储数据.
对于可变数组来说, 系统会预留内存位置, 当可变数组的大小超过这个预留内存大小时, 会做整体数据迁移, 会迁移到一块更大的预留内存位置.
二, 选择排序
我们先来看一下选择排序的算法流程:
解释:
1. 每一次循环 找到 未排序队列中的最小值的 index.(n 次)
2. 再与前置位交换, 未排序队列元素数 - 1
3. 重复 n 次, 得出最终排序队列, 故时间复杂度 = O(n2)
下面是基于 python 的实现代码:
每一次循环 找到 未排序队列中的最小值的 index.(n 次)
- def findSmallest(arr):
- smallest = arr[0]
- smallest_index = 0
- for i in range(1, len(arr)):
- if arr[i] < smallest:
- smallest = arr[i]
- smallest_index = i
- return smallest_index
再与前置位交换, 未排序队列元素数 - 1.(也可以加入新数组)
- def selectionSort(arr):
- newArr = []
- for i in range(len(arr)):
- smallest = findSmallest(arr)
- newArr.append(arr.pop(smallest))
- return newArr
完整示例代码:
- def findSmallest(arr):
- smallest = arr[0]
- smallest_index = 0
- for i in range(1, len(arr)):
- if arr[i] < smallest:
- smallest = arr[i]
- smallest_index = i
- return smallest_index
- def selectionSort(arr):
- newArr = []
- for i in range(len(arr)):
- smallest = findSmallest(arr)
- newArr.append(arr.pop(smallest))
- return newArr
- print selectionSort([5, 3, 2, 10, 6, 4, 7])
工程源码: QiAlgorithms 的 2-2demo https://github.com/QiShare/QiAlgorithms
小编微信: 可加并拉入《QiShare 技术交流群》, 二维码链接.
关注我们的途径有:
- QiShare(简书) https://www.jianshu.com/u/3db23baa08c7
- QiShare(掘金)
- QiShare(知乎) https://www.zhihu.com/people/edit
- QiShare(GitHub) https://github.com/QiShare
- QiShare(CocoaChina) http://www.cocoachina.com/bbs/u.php?tid=658244
- QiShare(Stack Overflow) https://stackoverflow.com/users/10118400/qishare
- QiShare(微信公众号)
来源: https://juejin.im/post/5c98ac16e51d451512498b19