快速排序的思想：以某一个元素key作为基准轴，将原序列划分成左右两部分，左边部分都不大于key，右边部分都不小于key，然后进行上行和下行遍历，下行遍历的时候找到比key小的，然后交换，上行遍历的时候找到比key大的然后交换，一直到上行下行遍历相遇为止，然后此时的位置就是key最终所在的位置，然后分别对左右部分的子序列进行相同的操作，递归进行，最终实现对数组的排序。
1 /*
2 * QuickSort.cpp
3 * author : freejohn
4 * time : 2012-07-13
5 */
6
7 #include <cstdio>
8 #include <cstring>
9 #include <iostream>
10 #include <iterator>
11 #include <string>
12 #include <cstdlib>
13 #include <cassert>
14 using namespace std;
15
16 template <typename T>
17 int partion(T* array, int l, int r)
18 {
19 int low, high;
20 low = l;
21 high = r;
22 T key = array[low];
23 while(high != low)
24 {
25 while(low < high && array[high] >= key) --high;
26 if(low < high)
27 {
28 array[low] = array[high];
29 ++low;
30 }
31 while(low < high && array[low] <= key) ++low;
32 if(low < high)
33 {
34 array[high] = array[low];
35 --high;
36 }
37 }
38 array[high] = key;
39 return high;
40 }
41
42 template <typename T>
43 void QuickSort(T* array, int l, int r)
44 {
45 if(l >= r)
46 return ;
47 int index = partion(array, l, r);
48 //cout << index << endl;
49 QuickSort(array, l, index-1);
50 QuickSort(array, index+1, r);
51 }
52
53 //test
54 int a[10005];
55 int main()
56 {
57 /*int a[10] = {3, 2, 1, 6, 5, 4, 0, 7, 9, 8};
58 QuickSort(a, 0, 9);
59 for(int i=0;i<10;++i)
60 cout << a[i] << " ";
61 cout << endl;*/
62 int n;
63 while(cin>>n)
64 {
65 for(int i=0;i<n;++i)
66 cin >> a[i];
67 QuickSort(a, 0, n-1);
68 cout << a[n/2] << endl;
69 }
70 return 0;
71 }
72