亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦，于是他提出了这样一个办法：
由于楼层并不算太高，那么在繁忙的上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。 问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？
分析:如果只有两个人到不同的楼层,A到4楼,B到9楼,那么电梯停在[4,9]区间之间，他们爬楼梯的总和都是一样的，共爬5个楼层。
如果有三个人：A到4楼，B到6楼，C到9楼，那么停在6楼的时候爬的楼层最少。
如果有四个人：A到4楼，B到5楼，C到7楼，D到11楼,那么停在[5,7]区间之间时，爬的楼层总和最少。
由上可得，就是找中位数的问题。本文用快速排序查找。
(Quicksort)是对冒泡排序的一种改进.
它的基本思路是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另外一部分的所有数据都要小,然后再按此方法对这两部分分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
时间复杂度: T(n)=θ（nlogn）
样例演示：
代码主体：
View Code 1 using System.Collections.Generic; 2 3 namespace QuickSortArithmetic 4 { 5 /// 6 /// 用快速排序查找第K大的数 7 /// 8 public class QuickSortOfKMaxNum 9 {10 //最后返回的第K大的数11 private int? _theKmaxNum = null;12 //第K大的数的顺序，也就是K13 public int K;//改为小写k试试14 15 public int? TheKmaxNum { get; set; }16 17 public int? GetKmaxNum(List list, int k)18 {19 K = k - 1;20 QuickSort(list, 0, list.Count - 1);21 return TheKmaxNum;22 }23 24 public void QuickSort(List list, int _left, int _right)25 {26 if (_left > _right)27 return;28 29 //把数据集的最左边和最右边标量保存下来30 int left = _left, right = _right;31 32 //选取数据集的第一个数为基准数，并保存在变量x上33 int x = list[left];34 while (left < right)35 {36 //从数据集的最右边开始找，在找到比x小的数之前，不断的从右边向左边查找，37 //直到找到比x小的数，每次比较都向左边移动一个距离right--38 while (x < list[right] && left < right)39 right--;40 41 //如果找到比x小的数，那么就就和left位置的数交换数值，42 //第一次运行时是第一个位置，交换之后，第一个位置就是比x小的数值，第right位置的数值就是x的数值43 //同时left++，即向右边移动一个距离，因为left位置的数值就是刚刚交换过来比x小的数，不需要比较了44 if (list[right] < x && left < right)45 {46 Swap(list, left, right);47 left++;48 }49 50 //右边查找到一个符合的数之后，反过来开始从左边标量left向右边right查找比x大的数51 //直到找到符合的数，每次比较都想右边移动一个距离left++52 while (list[left] < x && left < right)53 left++;54 55 //如果找到比x大的数，那么就和right位置的数交换56 if (x < list[left] && left < right)57 {58 Swap(list, left, right);59 right--;60 }61 }62 list[left] = x;63 64 //因为经过上面排序之后，已经知道在K之前的数都比K小，在K之后的数都比K大，65 //如果刚好left（此时left和right相等）等于K，那么left位置的值就是第K大的数66 if (left == K)67 TheKmaxNum = list[left];68 69 //如果left大于K，那么就是说第K大的数至少比left位置的数大，70 //而比left位置大的数都在它的右边，所以只需要从右边开始找71 else if (left > K)72 {73 QuickSort(list, left + 1, _right);74 }75 else76 {77 QuickSort(list, _left, left - 1);78 }79 }80 81 private void Swap(List s, int i, int j)82 {83 int temp = s[j];84 s[j] = s[i];85 s[i] = temp;86 }87 }88 }
执行代码：
View Code 1 using System; 2 using System.Collections.Generic; 3 4 namespace QuickSortArithmetic 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 {10 List s = new List ();11 Random rd = new Random();12 for (int i = 0; i < 10; i++)13 {14 s.Add(rd.Next(0, 50));15 }16 17 //第K大的数18 QuickSortOfKMaxNum quick = new QuickSortOfKMaxNum();19 int? kmax = quick.GetKmaxNum(s, 4);20 }21 }22 }