先排序
  • 如果是 quicksort, mergesort, 那么时间复杂度O(n logn),排序完成之后直接选择第k个即可
  • 如果k比较小,那么其实可以用插入排序,插入排序因为每次都需要选最小的出来,时间复杂度是O(n^2),但是如果选第k个,时间复杂度是O(kn)
  • quick select: 实际上就是用quick sort的思想(http://wdxtub.com/interview/14520606002197.html)
quicksort思想

先选一个pivot,然后将小于pivot的放在左,大于pivort的放在右(需要首尾两个指针完成这件事情),pivot在的位置即可将整个partation成两个部分,再quicksort左边,quicksort右边.

  • pivot如果是用(left+right)/2计算出来的话,那么实际上挪动left, right,他们一直向左向右,这样就完成了partation的工作
  • pivot如果是用最右边计算出来的话,那么完成left,right指针相遇之后,还需要再和pivot交换一下
quickselect
  • 实际上就是在quicksort的过程中,pivot确定好index之后,确定下index和k的大小关系(这个时候要注意index的下标是从0开始,k有可能是从1开始),确定好之后只sort特定的边就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 这个稍微有点浪费空间,虽然用了quicksort的思想
# 但是这是简单版本。用了O(n)的存储空间
def quickSort(arr):
less = []
pivotList = []
more = []
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
for i in arr:
if i< pivot:
less.append(i)
elif i>pivot:
more.append(i)
else:
pivotList.append(i)
less = quickSort(less)
more = quickSort(more)
return less + pivotList + more


# 不浪费空间

def quick(arr):
def q_sort(arr, start, end):
if start >= end:
return
left, right = start, end
# pivot 是一个数,不是index
pivot = arr[(start + end) / 2]
while left <= right:
while (left <= right and arr[left]< pivot):
left +=1
while (left <= right and arr[right] > pivot):
right -=1
if left <= right:
tmp = arr[left]
arr[left] = arr[right]
arr[right] = tmp
left +=1
right -=1
q_sort(arr, start, right)
q_sort(arr, left, end)
q_sort(arr, 0, len(arr)-1)
return arr
return arr