代码小工蚁的#《算法图解》#学习笔记-C2
C2 选择排序selection sort

一、内存的工作原理

在执行程序时，计算机须先将程序和相关数据读入内存中。
整个内存被分成若干个存储单元，每个存储单元一般可存放8位二进制数（字节编址）。
每个单元都有一个唯一的编号来标识（即地址）。^[1]
我们可以将内存想象成一个个连续的抽屉，我们可以存入或取出抽屉中的物品。

二、数组array和链表linked list

需要存储多个元素时，可使用数组或链表。
数组：元素存放在连续的内存空间中。
链表：元素存放在任意位置的内存空间中，每个元素都存储了下一个元素的地址。

访问方式：随机访问和顺序访问
数组支持随机访问。
链表只能顺序访问。

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

----	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

O(n) 线性时间
O(1) 常量时间
结论：数组读取快，链表插入、删除快。

三、选择排序

选择排序的思路：
1、n个数据存于列表中
2、遍历找到一个“最小值”，存到“新列表”中
3、遍历操作2，直到完成列表中所有元素
4、新列表即是排序结果（升序）

选择排序代码片断

# coding=utf-8

# 选择排序
def find_smallest(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 selection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest = find_smallest(arr)
        new_arr.append(arr.pop(smallest))
    return new_arr
if __name__ == '__main__':
    demo_arr = [3, 2, 5, 17, 9, 15, 12]
    print(demo_arr)
    print(selection_sort(demo_arr))

选择排序的时间复杂度为：O(n*n)，即O(n²)
选择排序是一个不稳定的排序算法。^[2]

代码分析：
arr.pop(smallest)
返回指定索引smallest的元素，并在列表arr中删除此元素。
new_arr.append()
将数据追加到列表new_arr末尾

扩展：python的list.sort()方法与sorted()函数
list.sort()：只适用list排序；返回：无（None），但原列表数据已被排序。
sorted()：适合所有可迭代对象的排序；返回结果是一个新列表，不是在原来的可迭代对象上进行操作。
简单的示例：

demo1 = [999, 3, 5, 7, 9]
demo1.sort()  # 此时无任何显示
print(demo1)  # 返回：[3, 5, 7, 9, 999] 数据已默认升序排列
demo1.sort(reverse=True)
print(demo1)  # 返回：[999, 9, 7, 5, 3] 数据已降序排列

demo2 = {'z':999, 'b':2, 'c':3, 'd':4, 'e':5}
print(sorted(demo2))  # 返回列表：['b', 'c', 'd', 'e', 'z'] 返回的是字典的键，默认升序
print(sorted(demo2.items()))  # 返回列表：[('b', 2), ('c', 3), ('d', 4), ('e', 5), ('z', 999)]
print(sorted(demo2.values(),reverse=True))  # 返回列表：[999, 5, 4, 3, 2] 返回字典的值，降序排列

sorted()还有更复杂的用法，此处先预留位置，以后再补充。

---

[1]百度百科：计算机工作原理
https://baike.baidu.com/item/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86/7681289?fr=aladdin

[2]百度百科：选择排序
https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F