程序员数据结构和算法分析

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

2018-01-09  本文已影响58人  爱吃西瓜的番茄酱

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

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

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

数组和链表

数组的特点就是

链表的特点就是

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

数组可以通过编号随机访问,因此读取速度为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]

小结

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

上一篇 下一篇

猜你喜欢

热点阅读