基于中位数选择获取数值数组A的第i个数据统计量 快速排序(随机化版本) 期望时间为线性的选择算法
时间复杂度
最坏运行时间为O(n)
伪算法
'''
1,将输入数组的n个元素划分为⌊n/5⌋组，每组5个元素，且至多只有一组由剩下的n mod 5个元素组成
2,寻找这⌈n/5⌉组中每一组的中位数：首先对每组元素进行插入排序，然后确定每组有序元素的中位数
3，对第2步中找出的⌈n/5⌉个中位数，递归调用SELECT以找出其中位数x（如果有偶数个中位数，约定x是较小的中位数）
4，利用修改过的PARTITION版本，按中位数的中位数x对输入数据进行划分。
让k比划分的低区间的元素书目多1,因此x是第k小元素，并且有n-k个袁术在划分的高区
5，如果i=k，则返回x。如果i<k，则在地区递归调用SELECT以找出第i小的元素。
如果i>k，则在高区递归查找i-k小的元素
'''
Python算法
def selectNumber(A
,p
,r
,i
):
'''递归获取数组A的第i统计量'''
if p
==r
:
return A
[p
]
c
=centerNumber
(A
,p
,r
)
k
=partition
(A
, p
, r
, c
)+1
if k
==i
:
return c
elif k
>i
:
return selectNumber
(A
,p
,k
-1,i
)
else:
return selectNumber
(A
,k
,r
,i
)
def centerNumber(A
,p
,r
):
'''递归选择数组A[p:r]的中位数'''
if r
-p
<5:
return insertionSortAsc
(A
, p
, r
)
B
=[]
for i
in range((r
+1-p
)//5):
B
.append
(insertionSortAsc
(A
, p
+5*i
, p
+5*i
+4))
if (r
+1-p
)%5 != 0:
B
.append
(insertionSortAsc
(A
, r
-(r
-p
)%5, r
))
return centerNumber
(B
,0,len(B
)-1)
def insertionSortAsc(A
,p
,r
):
'''
原址排序算法的输入A的[p,r]元素
返回已区间正序排序的A
'''
for j
in range(p
, r
+ 1):
key
= A
[j
]
i
= j
- 1
while i
>= p
and A
[i
] > key
:
A
[i
+ 1] = A
[i
]
i
-= 1
A
[i
+ 1] = key
return A
[(p
+ r
) // 2]
def partition(A
,p
,r
,x
):
'''
partition为快速排序的关键函数，用来对数组进行原址重拍
partition选择x作为主元，并围绕x把数组划分成4个(可能为空)区域
'''
i
= p
- 1
for j
in range(p
, r
):
if A
[j
] <= x
:
i
= i
+ 1
A
[i
], A
[j
] = A
[j
], A
[i
]
return i
运行结果
import numpy
a
=list(numpy
.random
.randint
(1,100,25,int))
print(a
)
print(selectNumber
(a
, 0, len(a
)-1, 8))
a
.sort
()
print(a
)
[74, 96, 45, 10, 96, 87, 38, 23, 43, 46, 44, 67, 5, 77, 45, 53, 75, 92, 96, 35, 9, 20, 75, 85, 76, 8, 57, 84, 54, 62, 98, 10, 38, 94, 16, 62, 36, 1]
20
[1, 5, 8, 9, 10, 10, 16, 20, 23, 35, 36, 38, 38, 43, 44, 45, 45, 46, 53, 54, 57, 62, 62, 67, 74, 75, 75, 76, 77, 84, 85, 87, 92, 94, 96, 96, 96, 98]
