算法图解 (二)

第二章 选择排序

本节内容数组、链表和选择排序

链表

• 链表中的元素可以存储在内存的任何地方
• 链表的每个元素都存储了下一个元素的地址

数组

• 数组与链表不同，你知道其中每个元素的地址
• 数组的读取效率很高

常见数组和链表操作的运行时间

1.png

选择排序

选择排序是一种简单直观的排序算法。它的工作原理如下，首先在未排序序列中找到最小 (大) 元素，存放到排序序列的起始位置，然后，再从剩余未排序元素继续寻找最小 (大) 元素，然后放到已排序序列的末尾。以次类推，直到所有元素均排序完毕

例子

# coding: utf-8

# 选择排序
def find_smallest(arr):
    small_index = 0
    small = arr[0]
    for i in range(1, len(arr)):
        if arr[i] < small:
            small_index = i
            small = arr[i]
    return small_index


if __name__ == '__main__':
    li = [42, 43, 64, 7, 5]
    print(find_smallest(li))

小结

• 数组的元素都连在一起，读取速度很快。同一个数组中，所有元素类型必须相同
• 链表的元素是分开的，其中每个元素都存储了下一个元素的地址，插入和删除速度很快