系列文章目录
第二章：选择排序
文章目录
前言
积累算法，记录学习
一、数组和链表
1、链表
链表中的元素可以储存在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
插入元素是链表的优势，因为它不需要进行元素的移动，只需要变动插入位置前后的地址索引即可。但是缺点也很明显，无法快速获取某个元素的位置，都需要从头进行索引查询。
2、数组
数组储存了一系列的数，而且你可以轻松get每个元素的位置和每个位置的元素，但它的缺点就是插入元素时需要移动后面所有元素的位置，从而造成时间的消耗。
下面给出了常见的数组和链表的操作时间：
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
既然数组列表各有好坏，因此选择的时候我们看具体的需求是什么，从而去选择用什么来存储数据
小知识：Facebook存储数据时使用了一种混合数据：链表数组。感兴趣的小伙伴可以去了解一下。
二、选择排序
假设我们有一组无序的数，需要将其进行从小到大排列，简单的做法是进行一次遍历选出最大值，然后pop出最大值，再进行下一遍遍历，以此类推直到选完，这样的简单排序算法复杂度是O(n2)：
>>> def Sort(arr):
new_arr = []
for i in range(len(arr)):
min_arr = arr[0]
arr_index = 0
for j in range(len(arr)):
if arr[j] < min_arr:
min_arr = arr[j]
arr_index = j
new_arr.append(min_arr)
arr.pop(arr_index)
return new_arr
>>> Sort([9,4,1,3,6,2])
[1, 2, 3, 4, 6, 9]
采用选择排序：
>>> 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
>>> selectionSort([9,4,1,3,6,2])
[1, 2, 3, 4, 6, 9]
3、总结
- 数组元素都在一起
- 链表元素可以分散存储，但其中每个元素都存储了下一个元素的地址
- 数组的读取速度很快
- 列表的插入和删除速度很快
- 在同一个数组中，所有的元素类型必须相同。