算法学习笔记（五）：快速排序和简单选择排序
(一) 快速排序
按照快速排序的思想，对数组A[p…r]进行排序。
1、 选择一个基准A[q]，调整数组，确保满足下面2个条件。
a) A[p…q-1] 的数据都小于等于 A[q]
b) A[q+1…r] 的数据都大于A[q]
2、 对A[p…q-1] 和 A[q+1…r]重复1步骤
例如：对列表[12,7,9,8,10,16,17,15]进行排序
1、 选择基准A[q] = 12，小于等于12的都插入到12前面，最后[7,9,8,10,12,16,17,15] ,返回基准A[q]的索引=4
2、 分别对A[p…q-1](即[7,9,8,10])和A[q+1…r]（即[16,17,15]）重复1过程。
实现：
1 #快速排序
2 def quickSort(A,p,r):
3 #当p等于r的时候，代表只有一个元素，这个时候就没必要调用partition(A,p,r)了
4 if p != r:
5 q = partition(A,p,r)
6 #递归
7 quickSort(A,p,q)
8 quickSort(A,q+1,r)
9 return A
10 #调整列表
11 def partition(A,p,r):
12 x = A[p] #选择A[p]作为基准
13 #迭代列表其他元素（A[p]之外的元素）
14 for i in range(p+1,r):
15 #小于基准的数据，都插入到A[p]前面
16 if A[i] <= x:
17 A.insert(p,A.pop(i))
18 p += 1 #获取基准元素最新的索引
19 #返回基准元素的索引
20 return p
21
22 A = [12,5,7,8,10,15,88,77,55,66,12,88,99,66,999,12]
23
24 print(quickSort(A,0,len(A)))(二) 简单选择排序
简单选择排序的思路是,假设列表有N个元素，对前N-1个元素执行下面的过程
1、从第一个元素开始查找，找出列表中的最小元素和A[0]交换
2、从第二个元素开始查找，找出列表中的最小元素和A[1]交换
3、从第三个元素开始查找，找出列表中的最小元素和A[2]交换
......
实现：
1 def selectSort(A):
2 #迭代列表的前n-1个元素
3 for i in range(len(A)-1):
4 k = i
5 for j in range(i+1,len(A)):
6 if A[k] > A[j]:
7 k = j #更新最小值的索引
8 #如果A[i]不是最小值，交换A[i],A[k]的值
9 if k != i:
10 A[k],A[i] = A[i],A[k]
11
12 return A
13
14
15 A = [12,5,7,8,10,15,88,77,55,66,12,88,99,66,999,12]
16
17 print(selectSort(A))举报
腾讯云开发者
