每天学习一点儿算法--选择排序

很多算法只有在数据经过排序后才管用，比如我们之前学习的二分查找。当然，很多语言都内置了排序算法，比如Python中的sort()函数和sorted()函数。我们可以直接调用内置函数完成排序，而不需要从头编写。

但是选择排序是快速排序的基石，而快速排序是一种重要的算法。所以，我们有必要对选择排序有一个基本的了解。

在学习选择排序之前，我们先回顾一下Python中的两种基本数据结构：数组和链表。

数组和链表

数组的特点就是：

• 数组中的每个元素在内存单元中都是连续的

• 数组的元素从0开始编号，我们可以通过编号立即找到某个元素，因此数组的访问元素速度为O(1)。

链表的特点就是：

• 链表中的元素可存储在内存的任何地方，每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

• 在链表中添加元素很容易，只需将其放入内存，并将其地址存储在前一个元素中，因此链表的插入速度为O(1)

下面来对比一下数组和链表的基本操作的运行时间：

数组可以通过编号随机访问，因此读取速度为O(1)。但在数组中插入（或删除）元素，需要将后面的元素全部后移（或前移）。因此插入（或删除）的速度为O(n)。

链表只能顺序访问，因此读取速度为O(n)。但在链表中插入数据很简单，只需要修改它前面的那个元素指向的地址。因此插入或删除的速度为O(1)。

选择排序

做了这么多的铺垫，其实和选择排序也就只有半毛钱的关系。选择排序的思路很简单：

• 先找出最大（或最小）的元素放在第一位，其他不变
• 再找出次大（或次小）的元素放在第二位，其他不变
• 重复以上步骤，直至所有元素排列完毕

举一个例子（从小到大排序）：

下面贴一个用Python实现的选择排序：

def find_smallest(arr):    
    """找出数组中最小的元素"""
    smallest = arr[0]  # 存储最小的元素
    smallest_index = 0  # 存储最小元素的索引
    for i in range(1, len(arr)):        
        if smallest > arr[i]:
            smallest = arr[i]
            smallest_index = i    
    return smallest_index


def selection_sort(arr):    
    """对数组进行选择排序"""
    new_arr = []    
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))    
    return new_arr

array = [5, 3, 3, 6, 2, 10]
result = selection_sort(array)
print("排序结果： ", result)

执行结果：

排序结果：  [2, 3, 3, 5, 6, 10]

小结

• 需要存储多个元素时，可用数组或链表
• 数组的元素时连续的；链表的元素是分开的
• 数组的读取速度很快；链表的插入和删除速度很快

每天学习一点点，每天进步一点点。