級別： ★☆☆☆☆
標簽：「算法」「選擇排序」「Selection Sort」
作者： MrLiuQ
審校： QiShare團隊

本篇將重點介紹選擇排序，在講解選擇排序之前，我們先復習一下數(shù)組和鏈表等知識。

一、數(shù)組 or 鏈表?

數(shù)組和鏈表作為常用的存儲數(shù)據結構，有各自的優(yōu)勢與劣勢。

• 數(shù)組的優(yōu)勢在于查詢速度快。
• 鏈表的優(yōu)勢在于插入與刪除速度快。

下面是兩者的時間復雜度：

為什么呢？
這與數(shù)組與鏈表的存儲方式有關。

數(shù)組是順序存儲，而鏈表是鏈式存儲。

• 順序存儲：所存儲的內存區(qū)域是連續(xù)的。
• 鏈式存儲：所存儲的內存區(qū)域是非連續(xù)的。

舉個例子：圖解一下

因此，當我們所存儲的數(shù)據經常查詢，則選擇數(shù)組好一些。
如果我們的數(shù)據經常被操作，并且數(shù)據長度經常發(fā)生變化，則選擇鏈表好一些。

關于數(shù)組的內存存儲還有幾個小知識點：

1. 對于不可變數(shù)組來說，每一次重新賦值都是一次內存整體遷移，相當于開辟了一塊新內存存儲數(shù)據。

2. 對于可變數(shù)組來說，系統(tǒng)會預留內存位置，當可變數(shù)組的大小超過這個預留內存大小時，會做整體數(shù)據遷移，會遷移到一塊更大的預留內存位置。

二、選擇排序

我們先來看一下選擇排序的算法流程：

解釋：
1.每一次循環(huán) 找到 未排序隊列中的最小值的index。（n次）
2.再與前置位交換，未排序隊列元素數(shù)-1
3.重復n次，得出最終排序隊列。
故時間復雜度 = O(n²)

下面是基于python的實現(xiàn)代碼：

• 每一次循環(huán) 找到 未排序隊列中的最小值的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

• 再與前置位交換，未排序隊列元素數(shù)-1。(也可以加入新數(shù)組)

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

推薦文章：
iOS Runloop（一）
iOS 常用調試方法：LLDB命令
iOS 常用調試方法：斷點
iOS 常用調試方法：靜態(tài)分析
iOS消息轉發(fā)
iOS 自定義拖拽式控件：QiDragView
iOS 自定義卡片式控件：QiCardView
iOS Wireshark抓包
iOS Charles抓包