中位数
对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，则中位数不唯一，通常取最中间的两个数值的平均数作为中位数。

中位数寻找的快速算法
一般寻找中位数可以先将数组排序，按照次序将中间的数据作为中位数即可，其时间复杂度主要取决于排序算法的时间复杂度，利用快速排序可以将其控制为线性对数量级。 

但是能否打破线性对数的限制呢？其中最关键的问题是，寻找中位数并不需要整个数组完全有序，如果把多余的元素排序省略掉，那么就可以超越线性对数的限制实现最快的算法。 

启发来源于快速排序算法中的切分法，比如我们需要找到数组中第 k小的元素，首先将数组a[lo,hi]切分返回整数j，使得 a[lo,j-1]都小于等于a[j]，而a[j+1,hi]都大于等于a[j]，如果j==k，那么j位置的元素就是我们要找的第k小的元素，而如果j>k，就要切分左子数组，如果j<k，就要切分右子数组，不断缩小选定的子数组的规模直到只剩下一个元素，则它就是最终我们要找的第k小的元素。 

经过数学推导，这种快速切分法寻找中位数仅仅为线性量级，是寻找中位数最为快速的算法。

算法实现
public class Select {
    // 寻找中位数
    public static <T> Comparable<T> findMedium(Comparable<T>[] a) {
        return select1(a, a.length / 2);
    }

    // 找出数组中第k小的元素，非递归实现
    public static <T> Comparable<T> select1(Comparable<T>[] a, int k) {
        int lo = 0, hi = a.length - 1;
        while (hi > lo) {
            int j = partition(a, lo, hi);
            if (j == k) {
                return a[k];
            } else if (j > k) {
                hi = j - 1;
            } else if (j < k) {
                lo = j + 1;
            }
        }
        return a[k];
    }

    // 找出数组中第k小的元素，递归实现
    public static <T> Comparable<T> select2(Comparable<T>[] a, int k, int lo, int hi) {
        int j = partition(a, lo, hi);
        if (j == k) {
            return a[k];
        } else if (j > k) {
            return select2(a, k, lo, j - 1);
        } else {
            return select2(a, k, j + 1, hi);
        }
    }

    public static <T> int partition(Comparable<T>[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable<T> v = a[lo];// 切分元素选为首元素
        while (true) {
            while (less(a[++i], v)) {// 向右扫描
                if (i == hi) {
                    break;
                }
            }
            while (less(v, a[--j])) {// 向左扫描
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {// 指针相遇，切分位置确定
                break;
            }
            exch(a, i, j);// 交换左右逆序元素
        }
        exch(a, lo, j);// 将切分元素放在切分位置
        return j;
    }

    @SuppressWarnings("unchecked")
    public static <T> boolean less(Comparable<T> v, Comparable<T> w) {
        return v.compareTo((T) w) < 0;
    }

    private static <T> void exch(Comparable<T>[] a, int i, int j) {
        Comparable<T> t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        String[] a = "qwertyuiopasdfghjklzxcvbnm".split("");
        System.out.println("Max: "+select1(a, 0));
        System.out.println("Min: "+select2(a, 25, 0, a.length - 1));
        System.out.println("Medium: "+findMedium(a));
    }
}

前言

这一篇文章就上上一篇博文算法的进一步优化了！ 

这里我们就利用中位数来进行线性时间的选择算法！


  
中位数就是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据就是中位数。


算法思路

（1）将输入的n个数划分成 ⌈n5⌉ 个组，当然最后一组的数目可能是小于5的！ 

（2）用任意的排序方法对他们进行排序，并取出一共 ⌈n5⌉ 个中位数。 

（3）找出该 ⌈n5⌉ 个中位数中的中位数。（如果 ⌈n5⌉ 是偶数则取相对大的那个数） 

（4）将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。

我们用小圆点表示元素，得到如下图： 



  
说明：  

  图中中间白色圈表示各组数据的中位数，最中间灰色表示中位数的中位数！ 箭头是从较小的数指向较大的数！


故我们可以使用该数作为划分的基准（比上一个随机基准的方法会好很多）！



图中 
3∗A1=3∗(n−5)10


当n≥75时，3A1大于等于14n。所以按此基准划分所得的左右2个子数组的长度都至少缩短14。



代码描述

int Select(int a[],int p,int r,int k)   
{  
    if(r-p<75)  
    {  
        //这里对数组 a[p->r] 进行排序 
        return a[p+k-1];  
    }  
    //(r-p-4)/5相当于n-5  
    for(int i=0; i<=(r-p-4)/5; i++)  
    {  
        //这里将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置  
        //使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数  
    }  

    int x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);  //找中位数的中位数  
    int i = Partition(a,p,r,x); //以x为基准对数组a进行划分 

    int j = i-p+1;  
    if(k<=j)  
    {  
        return Select(a,p,i,k);  
    }  
    else  
    {  
        return Select(a,i+1,r,k-j);  
    }  
}  

题目描述：
  输入数字n,按顺序呢打印从1到最大的n 位十进制数，比如输入3，打印1 2 3 。。999
思路：构造一个二维数组，假如n=3,就构造一个3行的二维数组list 

 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } 

我们要做的是每次都从第一行，第二行，第三行分别选一个数字打印。  用一个数组 answer来选择 list中 第 i 行选第几列的数字。如answer[2]=3,则表示选择打印 list[2][3]

代码：
     解法1：

import java.util.ArrayList;

public class Print1ToMaxN {
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 2;        

		ArrayList<int[]> list = new ArrayList<>(); // 实质是一个二维数组
		int answer[] = new int[n]; // answer[i] 表示 二维数组中 第 i 行所选的 列 值。 假如
									// answer[1]=6,
		// 那么就表示取二维数组 list[1][6]

		int num[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		for (int i = 0; i < n; i++) {
			list.add(num); // 生成二维数组
		}

		recursive(0, n, answer, list);

	}

	private static void recursive(int index, int n, int[] answer, ArrayList<int[]> list) {
		// TODO Auto-generated method stub
		if (index == n) { // 递归结束条件
			boolean beginWith0 = true; // 是否是0 开头
			for (int i = 0; i < n; i++) {

				if (list.get(i)[answer[i]] != 0) {
					beginWith0 = false;
				}
				if (!beginWith0) {
					System.out.printf("%d", list.get(i)[answer[i]]); // list.get(i)[answer[i]] 表示 list[i][j]
				}

			}
			if (!beginWith0) {
				System.out.println();

			}
			return;
		}

		for (answer[index] = 0; answer[index] < 10; answer[index]++) {
			recursive(index + 1, n, answer, list); // 递归
		}

	}

}

解法2：  此非递归解法的思想有点类似加法器。

代码：

import java.util.ArrayList;

public class numberToPhone1 {

	public static void main(String[] args) {
		// int num[] = { 0, 1 };
		int num[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		int n = 3;
		ArrayList<int[]> list = new ArrayList<>(); // 实质是一个二维数组
		int answer[] = new int[n]; // answer[i] 表示 二维数组list 中 第 i 行所选的 列 值。
		
        
		for (int i = 0; i < n; i++) {
			list.add(num); // 生成二维数组
		}

		while (true) {
			// n为电话号码的长度
			boolean beginWith0 = true; // 是否是0 开头
			for (int i = 0; i < n; i++) {
				if (list.get(i)[answer[i]] != 0) {
					beginWith0 = false;
				}
				if (!beginWith0) {
					System.out.printf("%d", list.get(i)[answer[i]]);  // list.get(i)[answer[i] 表示 list[i][j]
				}

			}
			if (!beginWith0) {
				System.out.printf("\n");
			}

			int k = n - 1;
			while (k >= 0) {
				if (answer[k] < num.length - 1) {
					answer[k]++;
					break;
				} else {                   // 进位
					answer[k] = 0;
					k--;
				}
			}
			if (k < 0)
				break;
		}

	}

}

解法3：此解法是剑指offer提供的解法

代码：

public class Print1ToMaxN {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 3;
		print1ToMaxN(n);
	}

	private static void print1ToMaxN(int n) {
		// TODO Auto-generated method stub
		char number[] = new char[n];
		recursivePrint(0, number, n);
	}

	private static void recursivePrint(int index, char[] number, int n) {
		// TODO Auto-generated method stub
		if (index == n) {
			boolean beginWith0 = true;

			for (int i = 0; i < n; i++) {

				if (number[i] != '0') {
					beginWith0 = false;
				}
				if (!beginWith0) {
					System.out.print(number[i]);

				}
			}

			if (!beginWith0) {
				System.out.println();

			}

			return;
		}

		for (int i = 0; i < 10; i++) {
			number[index] = (char) ('0' + i);
			recursivePrint(index + 1, number, n);
		}

	}

}








测试结果：

上机内容：C++程序的编写和运行

上机目的：掌握简单C++程序的编辑、编译、连接和运行的一般过程

我的程序：
/* 
Copyright (c) 2013, 烟台大学计算机学院  
* All rights reserved.  
* 作    者：赵玲玲   
* 完成日期：2013 年 11 月 22 日  
* 版 本 号：v1.0  
* 输入描述： 无 
* 问题描述：设计递归函数，并求出fibnacci序列的第20个数 
* 程序输出： fibnacci序列中的第20个数
* 问题分析：采用递归的方法
* 算法设计：略 
*/  

#include <iostream>
using namespace std;
int fib(int);                            //声明函数
int main()
{
    cout<<fib(20)<<endl;                 //调用
    return 0;
}
int fib(int n)                           //定义
{
    int sum=0;
    //序列前面四个数比较特殊，单独拿出来
    if(n==1)                             
    {
        return 0;
    }else if(n==2)
    {
        return 1;
    }else if(n==3)
    {
        return 1;
    }else if(n==4)
    {
        return 2;
    }
    //从第5项开始有规律的进行
    else                                 
    {
        sum=fib(n-1)+fib(n-2);            //找规律得到的式子
        return sum;                       //返回
    }
}



运行结果： 

心得体会：还是不太熟悉递归的调用步骤，这个fib数列的规律也是好歹才找到，后来综合了老师的答案才写出来 

知识点总结：递归的常规运用