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

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

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

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

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

1. //swaptwonumber
2. void swap( int &i, int &j)
3. {
4. int temp=i;
5. i=j;
6. j=temp;
7. }
8. //findapositiontopartitionthearray
9. int partition( int start, int end)
10. {
11. return end/2+start/2;
12. }
14. //quicksort
15. int QuickSort( int a[], int start, int end)
16. {
17. if (start>end)
18. {
19. throw "error" ;
20. }
21. if (start==end)
22. {
23. return end;
24. }
25. int p=partition(start,end);
26. int i=0;
28. swap(a[p],a[end]);
29. int j=end-1;
30. while (j>=i)
31. {
32. while (a[i]<a[end])
33. {
34. i++;
35. }
37. while (j>=0&&a[j]>a[end])
38. {
39. j--;
40. }
41. swap(a[i],a[j]);
42. }
43. swap(a[i],a[j]);
44. swap(a[i],a[end]);
45. return i;
46. }
48. //findthek-thsmallernumber
49. int FindK( int a[], int num, int kth)
50. {
51. if (kth>num||kth<=0)
52. {
53. throw "error:nosuchk-thnumber" ;
54. }
55. int k=kth-1; //becausethearrayindexstartswith0,not1;
56. int position=-1;
57. int start=0;
58. int end=num-1;
59. while (position!=k)
60. {
61. position=QuickSort(a,start,end);
63. if (position<k)
64. {
65. start=position+1;
66. }
67. else
68. {
69. end=position-1;
70. }
72. }
73. return a[position];
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个数可是无序的..如果想有序..再排序一下就可以了.