- 《算法图解》学习笔记
选择排序
假设你记录了你的听歌次数，你想要排序，看看自己最喜欢哪个乐队
选择排序的方法，就是遍历你的列表。找出次数最多的那条记录，然后添加到新列表中。
最终你得到了有序列表
看看需要多长时间：O(n)时间意味着查看列表中的每个元素一次，例如，对乐队列表进行简单查找时，意味着每个乐队都要查看一次。
要找出播放次数最多的乐队，必须检查列表中的每个元素。正如你刚才看到的，这需要的时间为O(n)。因此对于这种时间为O(n)的操作，你需要执行n次。
需要的总时间为O(n × n)，即O(n²)。
- 示例代码
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
print(selectionSort([5,3,6,2,7]))
快速排序
快速排序是一种常用的排序算法，比选择排序快得多。例如，C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了D&C。
- 对于排序算法来说，最简单的数组是什么呢？就是根本不需要排序的数组，比如空数组，或者只有一个元素的数组。那么基线条件便产生了——数组为空或者只有一个元素，这样子只需要返回原样的数组，不需要排序了。
- 更长一点的数组，拥有两个元素的数组，排序时也非常容易，两个元素比较大小即可。
- 再长一点的呢？三个元素的数组，别忘了我们要使用D&C，因此我们要分解数组，直到满足基线条件。
下面介绍快速排序的工作原理
首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。接下来，找出比基准值小的元素以及比基准值大的元素。
于是，我们现在有
- 一个由所有小于基准值的数字组成的子数组；
- 基准值；
- 一个由所有大于基准值的数组组成的子数组。
再将子数组进行快速排序，最终可以得到结果。
快速排序的独特之处在于，其速度取决于选择的基准值。（不同的基准值会有不同的排序过程，选择合适的基准值也很重要）
- 示例代码
def quickSort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0] # 示例以数组第一个元素为基准值
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quickSort(less) + [pivot] + quickSort(greater)
print(quickSort([10,5,2,3]))
