代码生成(用一门高级编程语言生成0~999 999(均包含,或者更大范围)之间的随机整数20 000个,要求随机数都不相同(如相同,则需要去重复并重新生成当前随机数),即,得到20 000个两两不同的随机数。用“查找”这一章的各种查找算法(顺序查找、折半查找、Hash查找[自己建立装填因子尽可能大的Hash表])实现上述已排序的20 000个数据中第12345个数据的查找(如果是C语言,则数组形式的数组下标为12344;即把已排序数据的第12345个数据作为key值,然后再把已排序序列当作未知具体数值的序列按相应算法进行查找,返回查找到的位置,并计算该过程耗费的时间或实际关键字的比较次数),比较不同算法的实际运行时间或经过的比较次数(请同时给出测试程序所在机器的硬件配置情况:CPU物理核心数、单核频数,内存容量)。)
时间: 2024-02-21 10:59:33 浏览: 77
以下是Python实现代码,用了快速排序和二分查找算法:
```python
import random
import time
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
def generate_random_numbers(n):
arr = []
while len(arr) < n:
x = random.randint(0, 999999)
if x not in arr:
arr.append(x)
return arr
arr = generate_random_numbers(20000)
arr = quick_sort(arr)
key = arr[12344]
start_time = time.time()
index = binary_search(arr, key)
end_time = time.time()
if index == -1:
print("Key not found.")
else:
print("Key found at index:", index)
print("Time elapsed:", end_time - start_time, "seconds.")
```
对于测试程序所在机器的硬件配置情况,需要您提供。
阅读全文