大家好，我是连人，本期分享线性时间选择问题。
线性时间选择是基于快速排序的一种延申，本质上和快排具有类似的地方。它的目的是找出这个数组中第k小的值。
既然只需找出1个值，我们就不必将整个数组排序。通过分治法和分区(partition)可以只将k所在范围内的值进行查找即可。
当然可以使用二分法去确立k的范围，但是我的课本上没有所以我们今天不讨论。
下面介绍两种算法：随机选择和中位数选择。
随机选择
随机选择是在当前处理的数组中随机挑选一个数，以这个数对数组进行partition操作，判断k与这个数的位置p的关系，如果k<=p，则再将左边进行当前操作，反之则对右边操作，体现了分治的思想。
举个例子。
查找第三小的数字
1，5，7，2，4，8，6
选择了7作为基准
partition后：
1，5，6，2，4，7，8
7的位置是6，3<6，所以将
1，5，6，2，4，7
再进行这次操作，直到数组只剩下一个数，即为所求
可以得知，随机选择在最坏情况下(例如找最大值时总是在最小值处划分)需要将所有元素都遍历一遍，需要O(n2)的时间。尽管如此，该算法的平均性能还是很好。可以证明，随机选择算法可以在O(n)的平均时间内找出n个输入元素中第k小的元素。
他说是，辣就是，反正我也不会证。
下面贴代码：
import random
def partition(a, left, right):
i = left
j = right
key = a[left]
while i < j:
while a[j] >= key and i < j:
j -= 1
a[i] = a[j]
while a[i] <= key and i < j:
i += 1
a[j] = a[i]
a[i] = key
return i
def randomized_partition(a, left, right):
if left > right: # 为了保护randint函数的
i = random.randint(left, right)
a[i], a[left] = a[left], a[i]
return partition(a, left, right)
def randomized_select(a, left, right, k):
if left == right:
return a[left]
i = randomized_partition(a, left, right)
j = i - left + 1
if k <= j:
return randomized_select(a, left, i, k)
else:
return randomized_select(a, i + 1, right, k)
number = random.randint(60, 80)
array = []
for i in range(0, number):
array.append(random.randint(0, 2*number))
print("一共生成了" + str(number) + "个数")
print("他们是：")
print(array)
k = input("你要查找第几小的数字？")
print(randomized_select(array, 0, number - 1, int(k)))
中位数选择
这种算法可以在最坏情况下用O(n)时间就完成选择任务。
这个算法由如下步骤完成：
①将数组分为若干组，每5个一组，最后一组可能会不满5个。
②将各个组排序，取出中位数。
③找出这些中位数的中位数，以这个结果为标准进行划分。
我在第三步对中位数数组还在75位以上的再次进行了取中位数操作。
针对这个算法，我们再举一个例子。
1，4，2，5，10，7，3，11，6，14，18，8，9，13
就先举14个数，方便理解。
首先，将这14个数按5个一组进行分组。最后一组只有四个单独列出来。
{1，4，2，5，10}，{7，3，11，6，14}，{18，8，9，13}
将每个组进行排序操作，得
{1，2，4，5，10}，{3，6，7，11，14}，{8，9，13，18}
将每个组的中位数取出来(为了节省空间通常会使用交换把中位数交换到最前面)，得
4，7，9
再将中位数进行排序(虽然这个例子自动排好了)
将中位数7取出，按7为基准对原数组进行partition。
判断k与7的位置关系，k在左边就对左边继续选择，反之对右边选择，体现了分治思想。
在集中中位数时，我没有使用“将中位数换到最前方”，而是新开的一个数组，这样做可以使代码更易懂，但缺点是增加了空间的消耗。
import random
def sort(a, l, r): # 冒泡排序
for i in range(l, r + 1):
for j in reversed(range(i, r + 1)):
if a[i] >= a[j]:
a[i], a[j] = a[j], a[i]
def partition(a, left, right, x): # 分区，这里不解释了
i = left
j = right
while i < j:
while a[j] > x and i < j:
j -= 1
while a[i] < x and i < j:
i += 1
a[i], a[j] = a[j], a[i]
return i
def find_mid(a, l, r):
if r - l < 75:
sort(a, l, r)
return a[(l + r) // 2]
else:
b = [] # 存储中位数的数组
i = l
while True:
if 5 * i + 4 <= r: # 判断是否为最后一组
sort(a, 5 * i, 5 * i + 4)
b.append(a[5 * i + 2])
else:
sort(a, 5 * i, r)
b.append(a[(5 * i + r) // 2])
break
i += 1
return find_mid(b, 0, len(b) - 1)
def select(a, l, r, k):
if r - l < 75:
sort(a, l, r)
return a[l + k - 1]
else:
mid_number = find_mid(a, l, r)
mid_position = partition(a, l, r, mid_number)
if k > mid_position:
return select(a, mid_position + 1, r, k)
else:
return select(a, l, mid_position, k)
number = random.randint(150, 200)
array = []
for i in range(0, number):
array.append(random.randint(0, number * 2))
print(array)
print("生成了" + str(number) + "个数")
k = input('输入想要第几小的数字')
print(select(array, 0, number - 1, int(k)))
转载注明出处。
