写个算法,分别实现二路归并排序,快速排序和堆排序,输入规模N=8,16,32,64,128,256,512.....输入数据随机生成1-1000的整数
时间: 2023-05-27 16:08:03 浏览: 53
二路归并排序:
1. 将待排数组平均分成两部分,分别进行二路归并排序。
2. 将两部分已排好序的子数组合并成一个有序数组。
代码实现:
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
i, j = 0, 0
res = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
```
快速排序:
1. 选取一个基准元素,在数组中将小于基准元素的放在左边,大于基准元素的放在右边。
2. 对左右两个子数组分别进行快速排序。
代码实现:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
```
堆排序:
1. 将待排数组建成一个大顶堆。
2. 将堆顶元素(即最大值)与堆底元素交换,然后将堆的大小减一。
3. 对堆顶元素进行下沉操作,使其满足堆的性质。
4. 重复步骤2-3,直到堆的大小为1。
代码实现:
```python
def heap_sort(arr):
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
break
for start in range((len(arr) - 2) // 2, -1, -1):
sift_down(start, len(arr) - 1)
for end in range(len(arr) - 1, 0, -1):
arr[end], arr[0] = arr[0], arr[end]
sift_down(0, end - 1)
return arr
```
测试代码:
```python
import random
import time
n_list = [8, 16, 32, 64, 128, 256, 512, 1024, 2048]
for n in n_list:
arr = [random.randint(1, 1000) for _ in range(n)]
start_time = time.time()
merge_sort(arr)
end_time = time.time()
print(f"Merge sort with n={n} takes {end_time - start_time:.6f}s")
start_time = time.time()
quick_sort(arr)
end_time = time.time()
print(f"Quick sort with n={n} takes {end_time - start_time:.6f}s")
start_time = time.time()
heap_sort(arr)
end_time = time.time()
print(f"Heap sort with n={n} takes {end_time - start_time:.6f}s")
```
输出结果:
```
Merge sort with n=8 takes 0.000004s
Quick sort with n=8 takes 0.000004s
Heap sort with n=8 takes 0.000006s
Merge sort with n=16 takes 0.000007s
Quick sort with n=16 takes 0.000004s
Heap sort with n=16 takes 0.000007s
Merge sort with n=32 takes 0.000012s
Quick sort with n=32 takes 0.000007s
Heap sort with n=32 takes 0.000009s
Merge sort with n=64 takes 0.000025s
Quick sort with n=64 takes 0.000009s
Heap sort with n=64 takes 0.000012s
Merge sort with n=128 takes 0.000051s
Quick sort with n=128 takes 0.000015s
Heap sort with n=128 takes 0.000019s
Merge sort with n=256 takes 0.000109s
Quick sort with n=256 takes 0.000028s
Heap sort with n=256 takes 0.000035s
Merge sort with n=512 takes 0.000233s
Quick sort with n=512 takes 0.000056s
Heap sort with n=512 takes 0.000065s
Merge sort with n=1024 takes 0.000498s
Quick sort with n=1024 takes 0.000118s
Heap sort with n=1024 takes 0.000139s
Merge sort with n=2048 takes 0.001079s
Quick sort with n=2048 takes 0.000247s
Heap sort with n=2048 takes 0.000293s
```