本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考，具体如下：
从一个无序的整型数组中选出第k小的数，如k=1为最小数，k=n为最大数。这里数组可以是有重复的值！
下面是自己写的一个函数，记在此处来记忆我留下的痕迹！
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
//选择无序数组中第k小的数#include <iostream>using namespace std ;bool failed = false ;//这里只考虑数组是int型的int findnumber(int *array,int start , int end, int k){ if(array == NULL || start > end || k < start || k > end+1 || k <= 0 ) { failed = true ; return 0; } if(start == end) { return array[start] ; } int len = end - start + 1 ; int tmp = 0 ; int ps = rand()%len +start ; int tk = k ; while(true) { //分割两数组 int f = start ; int t = array[ps] ; int equalnum = 0 ; for(int i = start ; i <= end ; i ++ ) { if(array[i]< t ) { tmp = array[f]; array[f] = array[i]; array[i] = tmp ; f ++ ; }else if(array[i] == t) { tmp = array[f]; array[f] = array[i]; array[i] = tmp ; f ++ ; equalnum ++ ; } } //end f--; if(equalnum > tk && (f - start + 1) == equalnum) { return t ;//这里是记录数据相等的数目，当我们从开始start处到最后处end都被这个值给充斥了，那么肯定是这里面的值了，再进行下去就会陷入死循环了。 } if(tk == (f - start + 1) ) { return t ; } if((f - start + 1 ) > tk ) { end = f ; }else { start = f + 1 ; tk = k - start ; //这个地方犯过错误，就是写成了k=k-start，在调试的时候老发现无限的循环。后来打印k的值的时候发现k的值都***为负了。这个bug，这个过错使得在一次运行可能会得到正确的数据，但是多次运行后程序就崩溃。 } len = end - start + 1 ; ps = rand()%len +start ; }}int main(){ int array[10] = {1,1,1,2,2,1,4,1,1,1}; for(int i = 0 ; i < 10 ; i ++ ) { cout<<findnumber(array,0,9,i+1)<<endl; } system("pause"); return 0 ;} |
先想好，分析好问题，自己脑中构思好了编写的思路，且想好了程序出错的地方再编程，这样会快的很多，而不是一看到问题就框框的在电脑上敲。
希望本文所述对大家C++程序设计有所帮助。
