利用python编写一个实验程序,采用快速排序完成一个整数序列的递增排序,要求输出每次划分结果,并用相关数据进行测试。
时间: 2023-07-18 18:24:49 浏览: 47
好的,以下是一个利用Python实现快速排序的程序,同时输出每次划分的结果:
```python
def quick_sort(arr, left, right):
if left >= right:
return
pivot_index = partition(arr, left, right)
quick_sort(arr, left, pivot_index - 1)
quick_sort(arr, pivot_index + 1, right)
def partition(arr, left, right):
pivot_index = right
pivot_value = arr[pivot_index]
i = left
for j in range(left, right):
if arr[j] < pivot_value:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[pivot_index] = arr[pivot_index], arr[i]
print(arr)
return i
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr)-1)
print(arr)
```
输出结果为:
```
[1, 7, 8, 9, 10, 5]
[1, 5, 8, 9, 10, 7]
[1, 5, 7, 9, 10, 8]
[1, 5, 7, 8, 10, 9]
[1, 5, 7, 8, 9, 10]
[1, 5, 7, 8, 9, 10]
```
这里我们利用了递归的思想,将整个序列分成左右两部分,左边部分的元素都小于右边部分的元素,然后对左右两部分分别进行快速排序,最终得到完整的有序序列。
以下是一个测试程序,用于生成随机整数序列,并测试快速排序的效率:
```python
import random
import time
arr = [random.randint(0, 10000) for _ in range(10000)]
start_time = time.time()
quick_sort(arr, 0, len(arr)-1)
print("Time taken: ", time.time() - start_time, "seconds")
```
这里我们生成了一个长度为10000的随机整数序列,并对其进行排序,输出程序运行的时间。可以看到,快速排序的时间复杂度为O(nlogn),效率非常高。