选择排序
#O(n**2)
#找到列表元素的最小值，以及索引值
def findSmallest(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 selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)#找到最小值
# pop()函数用法，移除列表中的一个元素（根据传入的索引值删除），并返回该元素的值，
# 默认不传参的话删除最后一个元素
newArr.append(arr.pop(smallest))
return newArr
#测试样例
print(selectionSort([2,878,45,1123,13763,134,1245]))
print(selectionSort([755.45,455,2457,15334,12,242,424,4527,24,24,5242.3,52]))
快速排序是一个重要D&C算法
D&C算法（divide and conquer）—— 一种著名的递归式问题解决方案
归并排序
这是一个比较清新的思路，是一张动图，但是我不知道如何放一张动图，所以你们就自己点进去看吧
https://www.runoob.com/wp-content/uploads/2019/03/mergeSort.gif
快速排序
#O(n*(log n))
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0] #找到一个基准值
#遍历整个列表，将小于这个基准值的元素放到一个子列表中
less = [i for i in array[1:] if i < pivot]
#遍历整个列表，将大于这个基准值的元素放到一个子列表中
greater = [i for i in array[1:] if i>pivot]
#首先，明确我们对元素为0个/1个的列表无需要排序
#使用函数递归
#目标：让我们在一个基准值的一侧变为有序，然后依次返回，让我们的每个基准值的两侧都变得有序
return quicksort(less)+[pivot]+quicksort(greater)
#这是一些测试样例
print(quicksort([2,5,3,9,7,11]))
print(quicksort([152,134,38796,7438415,1,2272,34345,24,127]))
快速排序的引用之一就是：C语言标准库中的函数sqort就是用快速排序实现
大O
大O表示法O（n）：一种特殊的表示法明知除了算法的速度有多快
实际上O(n)中的n指的是c(固定的时间量，一个常量)*n
如果两个算法的大O运行时间不同，这个常量就可以省略，但是如果时间相同，这个常量就比较重要了，这也就是为什么快排和归并排序运行时间差不多，但是快排效率更高
