首页 > > 网络编程 > 其它 >

算法学习笔记（五）：快速排序和简单选择排序

2018-06-27 09:46:11来源：博客园阅读 ()

(一) 快速排序

按照快速排序的思想，对数组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))