这学期学习算法分析与设计课程，今天看了看中位数，总结了总结算法，实现代码一会儿再贴

Description：

从一组输入数据中找出第k小的数，要求在线性时间内作出选择。

Solution：

传统的方法是对这组数据 进行排序（插入冒泡等），然后从排序后的序列中比较找出第k小的数，但是这种方法复杂度是O(nlogn)(采用快速排序)

为了在线性时间内得到结果，又如下方法,假设输入数组为a[]：

方法一： 类似于二分排序

Select(int[] a, int start, int end, int k)

{

//利用快速排序方法，将数组以pivot值分成两部分，下标为j

j = Partition(a,start,end);

//利用pivot值的下标j与k进行比较：

If( k = j)

    Return a[j]

If( k < j )

      //表示第k小的数在前半部分，则对前部分递归调用此方法

    Select(a,start,j-1,k);

If( k > j )

//表示第k小的数在后半部分，则对后部分递归调用此方法

Select(a,j+1,end,k-j);

}

分析：此种方法的平均时间复杂度是O(n);但是在最坏情况下，可能总是按剩下的元素中最大的进行划分，则复杂度为O(n*n)，因此如果能在线性的时间内找到划分的基准，则可以在最坏情况下复杂度为O(n)时找到第k小的数。具体看下面的方法。

方法二： 在O(n)下找到划分基准。

1.       找基准

(a)    将数组a五个数为一组，分成[n/5]个组

(b)    对[n/5]个组的数进行组内排序，采用冒泡就行

(c)    选择b中每组的中位数，将这些中位数交换到数组的最前面，此时a[0-(end-start)/5 -1]中存的就是这些中位数

(d)    对c中的0-(end-start)/5 -1个中位数进行排序，取出排序后这些中位数的中位数x。

X就是需要的基准。

2.       以x为基准进行划分，剩下的方法同方法一，即划分，比较，递归寻找。

分析：此种方法的最坏情况下复杂度也是O(n)