寻找数组中第K个大小的数的快速排序变种解法

    有一个数组，其大小已知，现在要找出其中第K个大小的数。作为最基本的算法，我们可以先对整个数组进行排序，然后直接找出第K个最小的数即可，但这种解法必须要有一个排序的过程，且排序的结果对于所要求的结果没有直接关系。现在我们通过一个快速排序的变种算法来解决这个问题。
    同样是采取分治法，我们将整个数组一分为二，将小的放到左边，将大的放到右边，并判断K和这两边的子数组长度的大小。如果K的left数组小，则K所在的数必定在left数组之中，否则则在right数组当中。这样就直接去掉接近于一半的数组。然后使用递归再在剩余的left数组中来查找。
    整个过程可以描述成以下过程：

1. 使用快速排序的pivot分割过程，将数组分割成left数组和right数组以及pivot三个部分
2. 如果left数组长度大于K，则继续在left数组中查找，否则在right数组中查找

    在上述的描述过程中，有几个特殊点是我们需要考虑的:

1.     如果K=1,则表示要找的数即整个数组中最小的数，那么直接查找最小的数即可
2.     如果K=数组长度，则表示要找的数即整个数组中最大的数，那么直接查找最大的数即可
3.     在数组分割之后，如果K=left数组长度+1,即pivot即是我们所要找的数，直接返回即可

    有了以上的描述，那么整个实现过程就不再复杂了。整个实现过程如下所示

 private static int find(int[] ints, int k) {
//转向子方法进行查找，将相应起始点和结束点传递之
		return find(ints, k, 0, ints.length - 1);
	}

    以上方法为起始方法，直接转向子方法

private static int find(int[] ints, int k, int start, int end) {
//第1步，有效值判断
		if(k < 1)
			throw new IllegalArgumentException("不能<1");
		if(k > (end - start) + 1)
			throw new IllegalArgumentException("超出范围");
//第2步，找最小的数
		//寻找最小
		if(k == 1) {
			int min = ints[start];
			for(int i = start + 1;i <= end;i++) {
				if(ints[i] < min)
					min = ints[i];
			}
			return min;
		}
//第3步，找最大的数
		//寻找最大数
		if(k == (end - start) + 1) {
			int max = ints[start];
			for(int i = start + 1;i <= end;i++) {
				if(ints[i] > max)
					max = ints[i];
			}
			return max;
		}
//第4步，数组分割
		//简单取最后一项
		int i = start, j = end - 1;
		while(true) {
			while(ints[i] < ints[end])
				i++;
			while(ints[j] > ints[end] && j > i)
				j--;
			if(i < j)
				swap(ints, i++, j--);
			else
				break;
		}
		swap(ints, i, end);
//第5步，判断k是否为left数组长度+1上
		int alreadyCount = i - start + 1;
		if(alreadyCount == k)
			return ints[i];
//第6步，转向left数组或right数组
		if(alreadyCount > k)
			return find(ints, k, start, i - 1);
		return find(ints, (k - alreadyCount), i + 1, end);
	}

    整个解决方法如上所示，简单明了，就不需要解释了。
    像这类解法，其实解决的就是一个算法思想，如果数据结构和算法没学好，是怎么也想不到这种解法了。
    以上的解法思想来自于《数据结构和算法 Java语言描述》，具体问题和实现与原解法有部分区别。

转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201108240001.html

相关文章：