[Python] 选择排序

上一篇文章我们写了一个二分查找的算法实现代码。虽然查找的效率是相当的高，但是却有一个比较重要的前提条件就是针对有序队列的才可以使用二分查找。

那么应该怎么使它们整整齐齐的排好队等着你找呢？这里我们首先选择选择排序进行讲解。眼花了没，是 选择排序。

虽然说“天下武功，唯快不破”，都在追求速度最快的算法。尽管选择排序不是综合性能最优的查找算法，但我们也要“知己知彼，方能百战不殆”。选择排序名副其实，主要分为两个步骤：

1. 选择
2. 排序

废话一箩筐，举个例子就是先从N个人站的队列中找到一个最高的，然后让他站到队列的一端。接着就是再从余下的N-1个人中选择一个最高的，让他挨着第一次选出来的人。依次选择，最终就会形成一个按高矮个排列的队伍。

我们首先利用 python 的语言优势来实现一个选择排序算法：

def find_min_num(arr): # 从队列中找到个子最小的同学
    min_num = arr[0]
    min_index = 0
    for i in range(1, len(arr)):
        if arr[i] < min_num:
            min_num = arr[i]
            min_index = i
    return min_index

def select_sort(arr): # 从小到大 选择排序
    sorted_arr = [] # 在操场为这个队伍开辟一块用于站队的新地方
    for i in range(len(arr)): 
        min_num = find_min_num(arr) # 从队伍中找到个子最小的同学
        sorted_arr.append(arr.pop(min_num)) # 让小个子同学站到新地方
    return sorted_arr

if __name__ == "__main__":
    arr = [14,5,2,6,8,5,2,90,45]
    print(select_sort(arr))

上面的代码结构很容易看懂，当然代价也是很大的！由于空列表（[]） 也会占中内存空间所以我们应该去换个思路去实现算法。

选择排序进阶版：

def select_sort_pro(arr): # 从大到小 选择排序
    for i in range(len(arr)):
        max_index = i # 将第一个元素标记为最大的
        for j in range(i+1, len(arr)): # 遍历一遍查找最大值的下标
            if arr[max_index] < arr[j]:
                max_index = j
        if i != max_index: # 如果在后面的数值中有比当前大的就交换值
            temp = arr[i]
            arr[i] = arr[max_index]
            arr[max_index] = temp
    return arr

if __name__ == "__main__":
    arr = [14,5,2,6,8,5,2,90,45]
    print(select_sort_pro(arr))

在进阶版本中，我们首先没有使用列表的 pop() 函数，然后也没有申请新的地方来进行存储。所以进阶版实验算法性能一定好于第一个版本。当然凡事讲证据，毛爷爷说过“没有调查，就没有发言权”。在这里就是没有实验就没有发言权。

从图中可以看到：

• 方法一运行时长 ：0.0006749999999999812
• 方法二运行时长 ：0.00039500000000014523

方法二比方法一快将近两倍。