算法小专栏:选择排序

avatar
奇舞团移动端团队 @奇舞团

级别: ★☆☆☆☆
标签:「算法」「选择排序」「Selection Sort」
作者: MrLiuQ
审校: QiShare团队


本篇将重点介绍选择排序,在讲解选择排序之前,我们先复习一下数组和链表等知识。

一、数组 or 链表?

数组和链表作为常用的存储数据结构,有各自的优势与劣势。

  • 数组的优势在于查询速度快。
  • 链表的优势在于插入删除速度快。

下面是两者的时间复杂度:

/ 数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

为什么呢? 这与数组与链表的存储方式有关。

数组是顺序存储,而链表是链式存储

  • 顺序存储:所存储的内存区域是连续的。
  • 链式存储:所存储的内存区域是非连续的。

举个例子:图解一下

因此,当我们所存储的数据经常查询,则选择数组好一些。 如果我们的数据经常被操作,并且数据长度经常发生变化,则选择链表好一些。

关于数组的内存存储还有几个小知识点:

  1. 对于不可变数组来说,每一次重新赋值都是一次内存整体迁移,相当于开辟了一块新内存存储数据。

  2. 对于可变数组来说,系统会预留内存位置,当可变数组的大小超过这个预留内存大小时,会做整体数据迁移,会迁移到一块更大的预留内存位置。

二、选择排序

我们先来看一下选择排序的算法流程:

解释:
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


小编微信:可加并拉入《QiShare技术交流群》,二维码链接

关注我们的途径有:
QiShare(简书)
QiShare(掘金)
QiShare(知乎)
QiShare(GitHub)
QiShare(CocoaChina)
QiShare(StackOverflow)
QiShare(微信公众号)

推荐文章:
iOS Runloop(一)
iOS 常用调试方法:LLDB命令
iOS 常用调试方法:断点
iOS 常用调试方法:静态分析
iOS消息转发
iOS 自定义拖拽式控件:QiDragView
iOS 自定义卡片式控件:QiCardView
iOS Wireshark抓包
iOS Charles抓包
奇舞周刊