选择排序和快速排序
给出一个数组，[1,5,3,9,4,2],对其排序。
下面介绍两种排序算法。
一，选择排序
选择排序：找出一个数组最小的数，然后在原数组中删除这个数，并加入到一个新的数组，持续遍历。
def selectSmallest(arr): #找出最小的数 samllest = arr[0] smallestIndex = 0 #一定要设一个初始值，不然后面arr只剩两个数的时候进入不了if语句，会报错。 for i in range(1,len(arr)): if arr[i] < samllest: samllest = arr[i] smallestIndex = i return smallestIndex #返回索引 def selectionSort(arr): #选择排序 newarr = [] for i in range(len(arr)): smallindex = selectSmallest(arr) newarr.append(arr.pop(smallindex)) print(arr) return newarr
print(selectionSort([7,4,6,2,9]))
结果如下：
[7, 4, 6, 9] [7, 6, 9] [7, 9] [9] [] [2, 4, 6, 7, 9]
从结果可以看到，选择排序正如前面所说，先找出最小值，然后删除。
从代码中，我们知道包含了两个for循环，它的循环时间为O(n**2),速度很慢。
二，快速排序
快速排序，一看这个名字就知道速度毕竟快，快速排序的代码非常精简，因为它运用了递归。
快速排序原理：先在列表中任意找一个数a,大于等于a的数加入一个列表，我们取名为high列表，比a小的数我们加入到一个列表，取名为low，现在我们有三个数据，low,a,high,然后对low和high继续前面的操作，一直到low,high列表为空或者只有一个数时结束。
代码如下
def quickSort(alist): low = [] #定义两个列表，待会来存储数据 high = [] if len(alist) > 1: #如果列表为空或者只有一个数据，直接返回列表，递归结束条件 for i in alist[1:]: #进入循环，大于等于列表第一个数的数加入到high列表，比它小的数加入到low列表 if i >= alist[0]: high.append(i) else: low.append(i) return quickSort(low)+[alist[0]]+quickSort(high) #递归，调用自身 else: return alist print(quickSort([3,6,5,4,87]))
结果：
[3, 4, 5, 6, 87]
