2.7 寻找第K最小数

2.7.1 算法思路

整体思路：结合2.6节的快速排序

  • 如果基准位就是第k位，就直接返回
  • 如果基准位在k的左端，就从基准位到尾部找
  • 如果基准位在k的右端，就从首部到基准位找

2.7.2 代码实现

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
48
49
50
51
52
53
54
public static int getKthSmallByDivideConquer(int[] originalData, int k) {
		int[] sortedData=originalData.clone();
		return sortedData[getKthSmallByDivideConquer(sortedData,0,sortedData.length-1,k)];
	}
	private static int getKthSmallByDivideConquer(int[] data, int head, int tail, int k) {
		if(head==tail) {//只有一个数的情况
			return head;
		}else {
			int partitionIndex=head+new java.util.Random().nextInt(tail-head+1);
			partitionIndex=partition(data,head,tail,partitionIndex);//调用快速排序
			/*核心代码*/
			if(partitionIndex<k-1) {//注意：第k最小数代表0，1，2，...k，即包括0
				return getKthSmallByDivideConquer(data,partitionIndex+1,tail,k);
			}else if(partitionIndex>k-1) {
				return getKthSmallByDivideConquer(data,head,partitionIndex-1,k);
			}else {
				return partitionIndex;
			}
		}
	}
////////////////////////
//给基准位排序
private static int partition(int[] sortedData, int head, int tail, int partitionIndex) {
		swap(sortedData,head,partitionIndex);//将首元素和基准元素对换位置
		int left=head+1;
		int right=tail;
		while(left<right) {
			while(sortedData[left]<=sortedData[head]&left<right) {
				left++;
			}
			while(sortedData[right]>=sortedData[head]&left<right) {
				right--;
			}
			if(left<right) {
				swap(sortedData,right,left);//对换位置,保证左小右大
			}
		}
		/*核心代码，易错点*/
		if(sortedData[right]>sortedData[head]) {
			swap(sortedData,right-1,head);
			partitionIndex=right-1;
		}else {
			swap(sortedData,tail,head);
			partitionIndex=tail;
		}
		return partitionIndex;
	}
///////////////////////////////	
//交换元素位置
	private static void swap(int[] sortedData, int a, int b) {
		int temp=sortedData[a];
		sortedData[a]=sortedData[b];
		sortedData[b]=temp;
	}

2.7.3 时间复杂度

时间复杂度：O(nlog2n)
分析：因为其原理实质为快速排序，所以时间复杂度和快速排序一样。