基于Partition函数实现查找数组中第K小的数+第K大的数

我们都知道经典的快速排序就是首先用 partition 将数组分为两部分，然后分别对左右两部分递归进行快速排序，过程如下：

public void quickSort(int arr[],int left ,int right) 
	{
		if (left>=right)//递归终止的条件 
		{
			return;
		}	
		int mid = partition2(arr, left, right);	
		quickSort(arr, left, mid);
		quickSort(arr, mid+1, right);
		
	}

 

虽然快排用到了经典的分而治之的思想，但是快排实现的前提还是在于 partition 函数。正是有了 partition 的存在，才使得可以将整个大问题进行划分，进而分别进行处理。

除了用来进行快速排序，partition 还可以用 O(N) 的平均时间复杂度从无序数组中寻找第K小的值。和快排一样，这里也用到了分而治之的思想。首先用 partition 将数组分为两部分，得到分界点下标 pos，然后分三种情况：

• index== k-1，则找到第 K 小的值，arr[pos]；
• index> k-1，则第 K 小的值在左边部分的数组。
• index< k-1，则第 K 小的值在右边部分的数组。

 下面给出基于递归的实现（用来寻找第 K 小的数）：

 

public int Kthsmall(int arr[],int k)
	{
		int left =0;
		int right = arr.length-1;
		int res=0;		
		while (left < right)
		{
			int index =partition2(arr, left, right);	
			if (index == k-1) 
			{
				res = arr[index];
				break;
			}
			if (index > k-1) 
			{
				right = index;
			}else {
				left =index+1;
			}
		}
		return res;
	}

 该算法的时间复杂度是多少呢？考虑最坏情况下，每次 partition 将数组分为长度为 N-1 和 1 的两部分，然后在长的一边继续寻找第 K 小，此时时间复杂度为 O(N^2 )。不过如果在开始之前将数组进行随机打乱，那么可以尽量避免最坏情况的出现。而在最好情况下，每次将数组均分为长度相同的两半，运行时间 T(N) = N + T(N/2)，时间复杂度是 O(N)。

 同理在寻找数组中第K大的值时候，同理也是可以利用partition函数的，附上Java实现的完整代码：

package Findwork;

/**
 * @author hadoop
 关于partition函数的应用  用来查找一个数组中第K大和第K小的数字；
 其中找第K小的数据比较直观，即找进行排序后的index为K-1的数字    （其实这里没有排序  可以再体会一下）
 找K大的数据，则需要做出相应的调整，找索引为Index是arr.length-k的项即可
 */
public class KthSmallNumPart {

	public static void main(String[] args) {
		int arr[]= {5,9,2,1,4,7,5,8,3,6};
		
		KthSmallNumPart k =new KthSmallNumPart();
		
		System.out.println(k.KthBig(arr, 5));
		System.out.println(k.Kthsmall(arr,2));
	}
	
	public int Kthsmall(int arr[],int k)
	{
		int left =0;
		int right = arr.length-1;
		int res=0;	
		
		while (left < right)
		{
			int index =partition2(arr, left, right);
			
			if (index == k-1) 
			{
				res = arr[index];
				break;
			}
			if (index > k-1) 
			{
				right = index;
			}else {
				left =index+1;
			}
		}
		
		return res;
	}
	
	public int KthBig(int arr[],int k)
	{
		int left =0;
		int right = arr.length-1;
		int res=0;	
		
		while (left < right)
		{
			int index =partition2(arr, left, right);
			
			if (index ==arr.length-k) 
			{
				res = arr[index];
				break;
			}
			if (index<arr.length-k ) 
			{
				left = index+1;
			}else {
				right=index;
			}
		}
		
		return res;
	}

	public int  partition2(int arr[],int left ,int right) //采用两个指针在寻找
	{
		int pivot =  arr[left];
		int pivotIndex = left;
		
		while(left<right) 
		{
			while(left<right && arr[right]>=pivot)
				right--;
				arr[left] = arr[right];
			while(left<right && arr[left]<pivot)
				left++;
				arr[right] = arr[left];
		}
		 arr[left] = pivot;
		 pivotIndex =left;
		 
		 return pivotIndex;
	}
}