http://mindlee.net/2011/08/03/median-and-order-statistics/
四种快速排序
http://www.wutianqi.com/http:/www.wutianqi.com/?p=2395
第i个顺序统计量:在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中第i小的元素。
四种快速排序
http://www.wutianqi.com/http:/www.wutianqi.com/?p=2395
第i个顺序统计量:在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中第i小的元素。
最小值是第1个顺序统计量(i=1)
最大值是第n个顺序统计量(i=n)
中位数：一个中位数(median)是它所在集合的“中点元素”，当n为奇数时，i=(n+1)/2，当n为偶数是，中位数总是出现在
（下中位数）和
（上中位数）。
（下中位数）和
（上中位数）。
如果要同时找出最大值和最小值，则比较次数最少并不是2*n-2，而是
，我们可以将一对元素比较，然后把较大者于max比较，较小者与min比较，这样就只需要
。
，我们可以将一对元素比较，然后把较大者于max比较，较小者与min比较，这样就只需要
。
如果是一般的选择问题，即找出一段序列第i小的数，看起来要比找最大值或最小值要麻烦，其实两种问题的渐进时间都是
。
。
该算法的平均情况性能较好，并且又是随机化的，所有没有哪一种特别的输入会导致最坏情况发生。
这种算法，利用“快排的或者类似二分”的思想，每次以枢纽为界，分两边，每次只需处理一边即可（抛弃另一边），平均情况下的运行时间界为O(n)，这种算法以期望时间做选择。《算法都论》里是，在分治时用随机数来选取枢纽（算法导论中伪代码见图），好吧，这是理论上的算法，它没有考虑实际产生随机数的开销，事实上，效率一点也不高，已经测试过，产生随机数花费的开销真的很大，后边我用更快的三数中值又实现了一遍，思想是一样的，只是效率提高了。
3、 第三种算法以最坏情况线性时间做选择，最坏运行时间为O(n)，这种算法基本思想是保证每个数组的划分都是一个好的划分，以5为基，五数取分，这个算法，算法导论没有提供伪代码，额，利用它的思想，可以快速返回和最终中位数相差不超过2的数，这样的划分接近最优，基本每次都二分了（算法导论中步骤见图)
int Partition(int kp[], int low, int high) { int pivotkey = kp[high]; int i = low - 1; for (int j = low; j < high; j++) { if (kp[j] <= pivotkey) { i++; swap(kp[j], kp[i]); } } swap(kp[i + 1], kp[high]); return i + 1;}//Partitioninline int Random(int low, int high) { return (rand() % (high - low + 1)) + low;}int Randomized_Partition(int kp[], int low, int high) { int i = Random(low, high); swap(kp[low], kp[i]); return Partition(kp, low, high);} int Randomized_Select(int kp[], int low, int high, int k) { if (low == high) { return kp[low]; } int pivotloc = Randomized_Partition(kp, low, high) ; int num = pivotloc - low + 1;//小于等于枢纽，数的个数 if (num == k) return kp[pivotloc]; if (k < num) { return Randomized_Select(kp, low, pivotloc - 1, k); } else { return Randomized_Select(kp, pivotloc + 1, high, k - num); }}
第二种：以期望线性时间做选择，三数中值选取枢纽元
int Median(int kp[], int low, int high) { int center = (low + high) >> 1; if (kp[low] > kp[center]) swap(kp[low], kp[center]); if (kp[low] > kp[high]) swap(kp[low], kp[high]); if (kp[center] > kp[high]) swap(kp[center], kp[high]); swap(kp[center], kp[high - 1]);//枢纽放到了kp[high - 1] return kp[high - 1];}//下边是我的解法：三数取中求第k小数 int Qselect1(int kp[], int low, int high, int k) { if (low + 2 <= high) { int pivotloc = Median(kp, low, high); int i = low, j = high - 1; for (; ;) { while (kp[++i] < pivotloc) {} while (kp[--j] > pivotloc) {} if (i < j) swap(kp[i], kp[j]); else break; } swap(kp[i], kp[high - 1]); int num = i - low + 1; if (k == num) return kp[i]; if (k < num) { return Qselect1(kp, low, i - 1, k); } else { return Qselect1(kp, i + 1, high, k - num); } } else {//上边的三数取中不能处理两个元素的情况，下边单独处理 if (high == low) {//一个元素情况 return kp[low]; } if (high - low == 1) {//两个元素情况 if (kp[low] > kp[high]) swap(kp[low], kp[high]); if (k == 1) return kp[low]; return kp[high]; } }}//Qselect1 //插入排序 void InsertionSort(int kp[], int n) { for (int j, i = 1; i < n; i++) { int tmp = kp[i]; for (j = i; j > 0 && kp[j - 1] > tmp; j--) { kp[j] = kp[j - 1]; } kp[j] = tmp; }}//后来才发现《数据结构与算法分析》理有三数取中求第k小的代码//不过我写的和它还是有些不一样…… 下边是它的版本 （后来加） void Qselect2(int kp[], int low, int high, int k) { if (low + 3 <= high) { int pivotloc = Median(kp, low, high); int i = low, j = high - 1; for (; ;) { while (kp[++i] < pivotloc) {} while (kp[--j] > pivotloc) {} if (i < j) swap(kp[i], kp[j]); else break; } swap(kp[i], kp[high - 1]); if (k <= i) { return Qselect2(kp, low, i - 1, k); } else if (k > i + 1) { return Qselect2(kp, i + 1, high, k); } } else { InsertionSort(kp + low, high - low + 1); }}//Qselect2/*利用中位数来选取枢纽元,这种方法最坏情况下运行时间是O(n) 这里求的中位数是下中位数 算法导论里没有伪代码，写起来很麻烦注意这里的查找到的中位数，并不是真正意义上的中位数而是和真正中位数相差不超过2的一个数开始以为我写错了，又看了算法导论，应该就是这个意思 返回的是[x - 1, x + 2]的一个数，中位数是x从下边的输出中也可以看出： */const int maxn = 14;//kp -> size const int maxm = maxn / 5 + 1;//mid -> size int kp[maxn];int mid[maxm];//插入排序 void InsertionSort(int kp[], int n) { for (int j, i = 1; i < n; i++) { int tmp = kp[i]; for (j = i; j > 0 && kp[j - 1] > tmp; j--) { kp[j] = kp[j - 1]; } kp[j] = tmp; }}//查找中位数, 保证每一个划分都是好的划分 int FindMedian(int kp[], int low, int high) { if (low == high) { return kp[low]; } int index = low;//index初始化为low //如果本身小于5个元素，这一步就跳过 if (high - low + 1 >= 5) { //储存中位数到mid[] for (index = low; index <= high - 4; index += 5) { InsertionSort(kp + index, 5); int num = index - low; mid[num / 5] = kp[index + 2]; } } //处理剩下不足5个的元素 int remain = high - index + 1; if (remain > 0) { InsertionSort(kp + index, remain); int num = index - low; mid[num / 5] = kp[index + (remain >> 1)];//下中位数 } int cnt = (high - low + 1) / 5; if ((high - low + 1) % 5 == 0) { cnt--;//下标是从0开始，所以需要-1 }//存放在[0…tmp] if (cnt == 0) { return mid[0]; } else { return FindMedian(mid, 0, cnt); } } int Qselect(int kp[], int low, int high, int k) { int pivotloc = FindMedian(kp, low, high); //这里有点不一样，因为不知道pivotloc下标，所以全部都要比较 int i = low - 1, j = high + 1; for (; ;) { while (kp[++i] < pivotloc) {} while (kp[--j] > pivotloc) {} if (i < j) swap(kp[i], kp[j]); else break; } int num = i - low + 1; if (k == num) return kp[i]; if (k < num) { return Qselect(kp, low, i - 1, k); } else { return Qselect(kp, i + 1, high, k - num); }}快速排序优化
2、由于N <= 20时，插入排序效率高于快速排序，于是就可以想在快排到递归时，当n <= 20，采用插入排序
当n > 20时，采用快排，这种方法效率可以提高很多.
