searchmedian.cpp

寻找无序数组的中位数

// SearchMedian.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include <iostream>

using namespace std;

// 快排中的划分
int Partition (int L[], int low, int high)
{
	int pivotkey = L[low];
	while (low < high)
	{
		while (low<high && L[high]>=pivotkey)
		{
			high--;
		}
		if(low < high) L[low++]=L[high];
		//L[low]=L[high];
		while (low < high && L[low] <= pivotkey)
		{
			low++;
		}
		if(low < high) L[high--] = L[low];
		//L[high] = L[low];

		/*for (int i=low; i<=high; i++)
		{
		cout<<L[i] << " ";
		}
		cout << endl;*/
	}
	L[low] = pivotkey;
	return low;
}

// 寻找第x大的数
int Searchxth(int A[], int low, int high, int xth)
{
	if (xth+low > high) return -1;
	int pivotLoc = Partition(A, low, high);
	int ith = pivotLoc-low;
	if (ith == xth)
	{
		return A[pivotLoc];
	}
	else if (ith < xth)
	{
		return Searchxth(A, pivotLoc+1, high, xth-ith-1);
	}
	else // ith > xth
	{
		return Searchxth(A, low, pivotLoc-1, xth);
	}

}

// 寻找无序数组的中位数
void TestSearchMedian()
{
	int A[] = {7,6, 12, 15, 9, 19,3, 22,51, 30,1,14};
	int N = sizeof(A)/sizeof(int);
	int V = 5;
	int low = 0;
	int high = N-1;
	int mid = (low+high)/2;
	cout<<Searchxth(A, low, high, mid);
}

int _tmain(int argc, _TCHAR* argv[])
{
	TestSearchMedian();
	return 0;
}