题目：一个长度为L (L>=1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= (2, 4，6，8, 20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：

1. 给出算法的基本设计思想。
2. 根据设计思想，釆用C或C++或Java语言描述算法，关键之处给出注释。
3. 说明你所设计算法的时间复杂度和空间复杂度。

该题为2011年研究生考试计算机联考真题。

第一种方法

算法思想：1.先将两个升序序列归并排序成一个升序序列，找中位数（最先想到且简单）
时间复杂度：O(n)，空间复杂度：O(n)

#include"head.h"
bool findmid1(SeqList A, SeqList B, SeqList& C) {
	if (A.length + B.length > C.Maxsize) {
		//return false;//若两表长度之和大于新表最大长度，则返回。
		//为了更有效的执行算法，此处我们不这样写，如果两表长度之和大于新表最大长度，则新表动态增加空间
		IncreaseSize(C, 10);//C表自动增加10个长度
	}
	int i = 0, j = 0, k = 0;
	while (i < A.length && j < B.length)
	{
		if (A.data[i] < B.data[j])
		{
			C.data[k++] = A.data[i++];
		}
		else
		{
			C.data[k++] = B.data[j++];
		}
	}
	while (i < A.length)
	{
		C.data[k++] = A.data[i++];
	}
	while (j < B.length)
	{
		C.data[k++] = B.data[j++];
	}
	C.length = k;
	int mid = C.length / 2;
	printf("C表中位数为：%d\n", C.data[mid-1]);//中位数，数组长度一般下标-1
	return true;
}

第二种方法

算法思想：类比归并排序的思想但并不实现归并，仅按顺序进行访问
时间复杂度：O(n)，空间复杂度：O(1)

int findmid2 ( int* a, int* b, int len ) {
	int i = 0, j = 0, k = 0;

	for ( ; k < len-1; k++ ) {
		if ( a[i] < b[j] ) {
			i++;
		}
		else {
			j++;
		}
	}

	return (a[i] < b[j])? a[i]: b[j];
}
//就是从头到尾一共数 len 个数，这个时候两个指针指向的数字较小者即为所求。

第三种方法

**王道考研参考书中给出的该题的最优方法

时间复杂度：O(log2n)，空间复杂度：O(1)

分别求两个升序序列A、B的中位数，设为a和b, 求序列A、B的中位数过程如下：

1. 若a = b，则a或b即为所求中位数，算法结束。

2. 若a < b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。

3. 若a > b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。**

int findmid3(int A[], int B[], int n)
{
	int start1 = 0, end1 = n - 1, m1, start2 = 0, end2 = n - 1, m2;
	//分别表示序列A和B的首位数、末位数和中位数

	while (start1 != end1 || start2 != end2)
	{
		m1 = (start1 + end1) / 2;
		m2 = (start2 + end2) / 2;
		if (A[m1] == B[m2])
			return A[m1];   //满足条件 1)

		if (A[m1] < B[m2]) // 满足条件 2)
		{
			if ((start1 + end1) % 2 == 0)  //若元素个数为奇数
			{
				start1 = m1;  //舍弃A中间点以前的部分且保留中间点
				end2 = m2;  //舍弃B中间点以后的部分且保留中间点
			}
			else				//元素个数为偶数
			{
				start1 = m1 + 1;  //舍弃A中间点及中间点以前部分
				end2 = m2;  //舍弃B中间点以后部分且保留中间点
			}
		}
		else
		{  //满足条件3)
			if ((start2 + end2) % 2 == 0)   //若元素个数为奇数
			{
				end1 = m1;    //舍弃A中间点以后的部分且保留中间点
				start2 = m2;    //舍弃B中间点以前的部分且保留中间点
			}
			else     //元素个数为偶数
			{
				end1 = m1;    //舍弃A中间点以后部分且保留中间点
				start2 = m2 + 1;    //舍弃B中间点及中间点以前部分
			}
		}
	}
	return  A[start1] < B[start2] ? A[start1] : B[start2];
}

总结

1. 当在练习的时候可以对三种方法慢慢调试，仔细理解。

2. 若无法理解第三种最优解的方法建议就不要再看了，考试时第三种方法为满分答案，第二种方法减1分，第一种方法减2分。

3. 小编在写第一种和第二种方法时一共用了10分钟，第三种方法依然没有理解并成功运行，给诸位大佬程序员丢人了…

给一列无序数组，求出中位数并给出算法的时间复杂度。

/*
File name:求中位数.cpp
Author:杨柳
Date:2017/5/25
IDE:DEV-c++ 
思想：把无序数组排好序，取出中间的元素
*/

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100
int array[MAX],arr[MAX];
int result=0;//保存中位数 

//简单选择排序 
int selectsort(int array[],int n){
	int temp,j,k;	//设置临时变量 
	for(int i=0;i<n;i++){  //n-1趟 
		j=i;	//记录最小元素的位置 
		for(k=i+1;k<n;k++){
			if(array[j]>array[k])
				j=k;
				temp=array[i];
				array[i]=array[j];
				array[j]=temp;
		}
	}
	if(n%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
		result=((array[n/2-1]+array[n/2])/2);
		return result;
	}
	else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
		result=array[(n-1)/2];
		return result;
	}
}

//直接插入排序
int insertsort(int array[],int n){
	for(int i=1;i<n;i++){
			int temp;//设置临时变量存放待插入的记录
		 	temp=array[i];		
		 	for(int k=i-1;k>=0&&temp<array[k];k--){	//待插入一次与前面数据一次 
		 		array[k+1]=array[k]; 
				 array[k+1]=temp;
			 } 
		 	
	}
	if(n%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
		result=((array[n/2-1]+array[n/2])/2);
		return result;
	}
	else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
		result=array[(n-1)/2];
		return result;
	}
} 
//希尔排序求中位数
int  shellsort(int array[],int arr[],int n,int m) {
	int h,k,j,v;
	for(int i=0;i<m;i++){
		h=arr[i];//选取增量
		for(k=h;k<n;k++){
			j=array[k];
			for(v=k-h;v>=0&&j<array[v];v=v-h){
				array[v+h]=array[v];
				array[v+h]=j;
			}
		} 
	}


	if(n%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
		result=((array[n/2-1]+array[n/2])/2);
		return result;
	}
	else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
		result=array[(n-1)/2];
		return result;
	}
}

//冒泡排序求中位数
int bubblesort(int array[],int n){
	int temp,change=true;  //设置标志以便进入循环 
	for(int i=1;i<n&&change;i++){   //n-1趟 
		change=false;//第i趟设置交换标志false，这时没有交换记录，已经有序，结束 
		for(int j=0;j<n-i;j++){
			if(array[j]>array[j+1]){  //若逆序交换 
				temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
				change=true;
			}
		}
		
	}
	
	if(n%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
		result=((array[n/2-1]+array[n/2])/2);
		return result;
	}
	else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
		result=array[(n-1)/2];
		return result;
	}
} 

//快速排序求中位数
int  quicksort(int array[],int min,int max){
	int high,low;
	if(min<max){
		low=min;
		high=max;
		int temp=array[low];  
		while(low!=high){
			while(low<high&&array[high]>temp){ //从右向左 
				high--;
			}
			if(low<high)
				array[low++]=array[high];  //比 array[low]小，交换 
			while(low<high&&array[low]<=temp){ //从左向右 
				low++;
			}
			if(low<high){
				array[high--]=array[low];  //交换 
			}
			}
	array[low]=temp;		
	quicksort(array,min,low-1);
	quicksort(array,high+1,max);
		}
	if((max+1)%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
		result=((array[(max+1)/2-1]+array[(max+1)/2])/2);
		return result;
	}
	else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
		result=array[(max)/2];
		return result;
	}	
		
}

//调整为堆
void shift(int array[],int s,int n){
	int q,t;
	t=array[s];
	while((q=2*s+1)<n){ //有左孩子 
		if(q<n-1&&array[q]<array[q+1])
			q++;
		if(t<array[q]){
			array[(q-1)/2]=array[q];
			s=q;
		} 
		else
			break;
	}
	array[(q-1)/2]=t;  //t放在最后一个位置 
} 

//堆排序求中位数
int heapsort(int array[],int n){
	int s,t;
	s=(n-1)/2;
	while(s>=0){
		shift(array,s,n);
		s--;
	}
	s=n-1;
	while(s>0){  //交换结点 
		t=array[0];
		array[0]=array[s];
		array[s]=t;
		shift(array,0,s);
		s--;
	}
	if(n%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
		result=((array[n/2-1]+array[n/2])/2);
		return result;
	}
	else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
		result=array[(n-1)/2];
		return result;
	}
} 

//合并两个有序序列 
void merge(int array[],int p,int q,int r){
	int n1,n2;
	n1=q-p+1;
	n2=r-q+1; 
	int arr1[n1+1],arr2[n2];
    for(int i=0;i!=n1;++i){
    	arr1[i]=array[i+p];
    
	}
		arr1[n1]=2000000;
	for(int j=0;j!=n2-1;++j){
		arr2[j]=array[q+j+1];
	}
		arr2[n2-1]=200000;
		int i=0,j=0;
	for( int k=p;k!=r+1;++k){
		if(arr1[i]>arr2[j]){
			array[k]=arr2[j];
		    ++j;
		}
		else{
			array[k]=arr1[i];
			++i;
		}
	}
}
//归并排序求中位数
void mergesort(int array[],int p,int r){
	if(p<r){
		int q=(p+r)/2;
		mergesort(array,p,q);
		mergesort(array,q+1,r);
		merge(array,p,q,r);
	}
			
} 
 
int midiumnumber(int array[],int n){
		cout<<endl<<endl<<"1----------简单选择排序求中位数(O(n^2))"<<endl;
		cout<<"2----------直接插入排序求中位数(O(n^2))---------"<<endl;
		cout<<"3----------希尔排序求中位数(O(nlog2^n))---------"<<endl;
		cout<<"4----------冒泡排序求中位数(O(n^2))-------------"<<endl;
		cout<<"5----------快速排序求中位数(O(nlog2^n))---------"<<endl;
		cout<<"6----------堆排序求中位数(O(nlog2^n))-----------"<<endl;
		cout<<"7----------归并求中位数(O(nlog2^n))-----------"<<endl;
		cout<<"请选择1-7："<<endl; 
		int select;
		cin>>select;
		switch(select){
			case 7:
				cout<<"这列无序数组的中位数为："<<endl;
			    mergesort(array,0,n-1);
			    	if(n%2==0){		//	若数组有奇数个元素，中位数是array[(n-1)/2]
						result=((array[n/2-1]+array[n/2])/2);
						return result;
					}
					else{			//若数组有偶数个元素，中位数为array[n/2-1]和array[n/2]两个数的平均值
						result=array[(n-1)/2];
						return result;
					}
				break;
			case 6:
				cout<<"这列无序数组的中位数为："<<endl;
				return heapsort(array,n);
				break;	
			case 5:
				cout<<"这列无序数组的中位数为："<<endl;
				return quicksort(array,0,n-1);
				break;	
			case 4:
				cout<<"这列无序数组的中位数为："<<endl;
				return bubblesort(array,n);
				break;
			case 1:
				cout<<"这列无序数组的中位数为："<<endl;
				return selectsort(array,n);
				break;	
			case 2:
				cout<<"这列无序数组的中位数为："<<endl;
				return insertsort(array,n);
				break;
			case 3:
				//初始化一个增量数组 
				int n1=n;
				int m=0;
				while(n1>1){
					arr[m++]=n1/2;
					n1=n1/2;
				}
				cout<<"这列无序数组的中位数为："<<endl;
				return 	shellsort(array,arr,n,m);
				break;			

			}
}

int main(){

	int n,i;
	cout<<"输入一列无序数组数的个数："<<endl;
	cin>>n;
	cout<<"请输入一列无序数组："<<endl;
	for(i=0;i<n;i++){
		cin>>array[i];
	}

   int flag=1;
   while(flag==1){
	cout<<midiumnumber(array,n)<<endl;
}
//	cout<<selectsort(array,n);
   
	return 0;
} 

归并排序

思想

排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序采用的是分治思想。
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

注：x >> 1 是位运算中的右移运算，表示右移一位，等同于 x 除以 2 再取整，即 x >> 1 === Math.floor(x / 2) 。

代码

const mergeSort = arr => {
	//采用自上而下的递归方法
	const len = arr.length;
	if (len < 2) {
		return arr;
	}
	// length >> 1 和 Math.floor(len / 2) 等价
	let middle = Math.floor(len / 2),
		left = arr.slice(0, middle),
		right = arr.slice(middle); // 拆分为两个子数组
	return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
	const result = [];

	while (left.length && right.length) {
		// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
		if (left[0] <= right[0]) {
			result.push(left.shift());
		} else {
			result.push(right.shift());
		}
	}

	while (left.length) result.push(left.shift());

	while (right.length) result.push(right.shift());

	return result;
};

测试

// 测试
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time('归并排序耗时');
console.log('arr :', mergeSort(arr));
console.timeEnd('归并排序耗时');
// arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
// 归并排序耗时: 0.739990234375ms

分析

第一，归并排序是原地排序算法吗 ？
这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。
所以，归并排序不是原地排序算法。

第二，归并排序是稳定的排序算法吗 ？
merge 方法里面的 left[0] <= right[0] ，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是一种稳定的排序方法。

第三，归并排序的时间复杂度是多少 ？
从效率上看，归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步, 又每步都是一个普通的合并子数组的过程，时间复杂度为 O(n)，故其综合时间复杂度为 O(nlogn)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(nlogn)。
平均情况：T(n) = O(nlogn)。

堆排序（Heap Sort）

堆的定义

堆其实是一种特殊的树。只要满足这两点，它就是一个堆。

堆是一个完全二叉树。
完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。
对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。

其中图 1 和 图 2 是大顶堆，图 3 是小顶堆，图 4 不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。

思想

1.将初始待排序关键字序列 (R1, R2 … Rn) 构建成大顶堆，此堆为初始的无序区；

2.将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, … Rn-1) 和新的有序区 (Rn) ，且满足 R[1, 2 … n-1] <= R[n]。

3.由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2 … Rn-1) 调整为新堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区 (R1, R2 … Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程，直到有序区的元素个数为 n - 1，则整个排序过程完成。

实现

// 堆排序
const heapSort = array => {
	console.time('堆排序耗时');
	// 初始化大顶堆，从第一个非叶子结点开始
	for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {
		heapify(array, i, array.length);
	}
	// 排序，每一次 for 循环找出一个当前最大值，数组长度减一
	for (let i = Math.floor(array.length - 1); i > 0; i--) {
		// 根节点与最后一个节点交换
		swap(array, 0, i);
		// 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可
		heapify(array, 0, i);
	}
	console.timeEnd('堆排序耗时');
	return array;
};

// 交换两个节点
const swap = (array, i, j) => {
	let temp = array[i];
	array[i] = array[j];
	array[j] = temp;
};

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设结点 i 以下的子堆已经是一个大顶堆，heapify 函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。
// 后面将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 heapify 操作，所以就满足了结点 i 以下的子堆已经是一大顶堆
const heapify = (array, i, length) => {
	let temp = array[i]; // 当前父节点
	// j < length 的目的是对结点 i 以下的结点全部做顺序调整
	for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
		temp = array[i]; // 将 array[i] 取出，整个过程相当于找到 array[i] 应处于的位置
		if (j + 1 < length && array[j] < array[j + 1]) {
			j++; // 找到两个孩子中较大的一个，再与父节点比较
		}
		if (temp < array[j]) {
			swap(array, i, j); // 如果父节点小于子节点:交换；否则跳出
			i = j; // 交换后，temp 的下标变为 j
		} else {
			break;
		}
	}
};

测试

const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log('原始array:', array);
const newArr = heapSort(array);
console.log('newArr:', newArr);
// 原始 array:  [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// 堆排序耗时: 0.15087890625ms
// newArr:     [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]

分析

第一，堆排序是原地排序算法吗 ？
整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是原地排序算法。

第二，堆排序是稳定的排序算法吗 ？
因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
所以，堆排序是不稳定的排序算法。

第三，堆排序的时间复杂度是多少 ？
堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(nlogn)。
平均情况：T(n) = O(nlogn)。