编程练习——求无序数组第K小的数

为同寝的家伙写了一个求一个无序数组中第k小数的程序。思想就是快排的思想。找一个点，然后放到末尾，然后将小于这个数的值放在数组前面，大于这个值的放在数组后面，
然后在将这个末尾的数放回。这个末尾数放入的位置i代表已经找到第i小的数。下面你应该明白了吧，放入的位置如果是k，恭喜你找到了第k小的数。

同样找到第k大的数类似的解法，找到前k个最大数也一样。找一个数组的中位数也一样做。求n个数组的中位数也一样的做。求n个数组的前k个大数或小数也类似可以做。

这个程序的算法复杂度是O（n）

另外这个程序是交换了这个数组元素中的顺序的。现在考虑一下如果不交换过去数组中的元素顺序，并且不开辟一个O(n)空间。那么这个算法的平均复杂度是多少？考虑一下
，写在评论中。谢谢。

1. // swap two number
2. void swap( int &i, int &j)
3. {
4. int temp = i;
5. i = j;
6. j = temp;
7. }
8. // find a position to partition the array
9. int partition( int start, int end)
10. {
11. return end/2+start/2;
12. }
13. 14. // quick sort
14. int QuickSort( int a[], int start, int end)
15. {
16. if (start > end)
17. {
18. throw “error” ;
19. }
20. if (start == end)
21. {
22. return end;
23. }
24. int p = partition(start,end);
25. int i =0;
26. 28. swap(a[p],a[end]);
27. int j = end-1;
28. while (j>=i)
29. {
30. while (a[i]<a[end])
31. {
32. i++;
33. }
34. 37. while (j >= 0 && a[j]>a[end])
35. {
36. j–;
37. }
38. swap(a[i],a[j]);
39. }
40. swap(a[i],a[j]);
41. swap(a[i],a[end]);
42. return i;
43. }
44. 48. // find the k-th smaller number
45. int FindK( int a[], int num, int kth)
46. {
47. if (kth > num || kth <= 0)
48. {
49. throw “error: no such k-th number” ;
50. }
51. int k = kth-1; // because the array index starts with 0, not 1;
52. int position= -1;
53. int start = 0;
54. int end = num-1;
55. while (position != k)
56. {
57. position = QuickSort(a,start,end);
58. 63. if (position < k)
59. {
60. start = position+1;
61. }
62. else
63. {
64. end = position-1;
65. }
66. 72. }
67. return a[position];
68. 75. }
        public class Sort{ public int Partition(SortTag[] al,int start, int end){
        SortTag p = al[start]; SortTag tmp; while(start<end){ while(start<end &&
        al[end].compare(p)<=0) end–; tmp = al[start]; al[start] = al[end]; al[end] =
        tmp; while(start<end && al[start].compare(p)>=0) start++; tmp = al[start];
        al[start] = al[end]; al[end] = tmp; } return start; } public void
        FindTopK(SortTag [] al,int k){ if(al.length < k){ return; } int mid = 0; int
        low = 0; int high = al.length-1; while(low <= high){ mid =
        Partition(al,low,high); if(mid < k){ low = mid+1; } else if(mid > k){ high =
        mid-1; } else{ return ; } } } } class SortTag{ public Integer n; public Double
        score; public SortTag(Integer n, Double score){ this.n = n; this.score =
        score; } public int compare(Object o){ Double d = this.score -
        ((SortTag)o).score; if ( d > 0 + 1E-12) return 1; else if( d < 0-1E-12) return
        -1; else return 0; } }

注意这k个数可是无序的…如果想有序…再排序一下就可以了.