}
cout << "The average time of searching a date in the array size of " << num << " is " << acc / 10
<< endl;
}
return 0;
}
测试:
当数组元素是随机的,那么取数组中第一个元素为枢纽元的话,即是相当于保证在固定数
组中枢纽元元素的选取是随机的。所以,上述程序有下面的线性复杂度的运行结果(当然,
多次的运行结果,具体得到的测试时间的数值是不同的,但基本上,是保证线性增长的。):
The average time of searching a date in the array size of 5000 is 0
The average time of searching a date in the array size of 50000 is 1
The average time of searching a date in the array size of 500000 is 12
The average time of searching a date in the array size of 5000000 is 114
The average time of searching a date in the array size of 50000000 is 1159
Press any key to continue
updated:
非常感谢飞羽等人的工作,将上述三个版本综合到了一起(待进一步测试):view plaincopy
to clipboardprint?///下面的代码对 July 博客中的三个版本代码进行重新改写。欢迎指出错误。
/// 先 把 它 们 贴 在 这 里 , 还 要 进 行 随 机 化 数 据 测 试 。 待 发 ...//modified by 飞 羽 at
2011.5.11/////Top_K_test// 修 改 了 下 命 名 规 范 , July 、 updated , 2011.05.12 。 #include
<iostream>#include <stdlib.h>using namespace std;
inline int my_rand(int low, int high)
{
int size = high - low + 1;
return low + rand() % size;
}
int partition(int array[], int left, int right)
{
int pivot = array[right];
int pos = left-1;
for(int index = left; index < right; index++)
{
if(array[index] <= pivot)
swap(array[++pos], array[index]);
}
swap(array[++pos], array[right]);
return pos;//返回 pivot 所在位置}
bool median_select(int array[], int left, int right, int k)
{
//第 k 小元素,实际上应该在数组中下标为 k-1 if (k-1 > right || k-1 < left)