已知待排序序列为56[1],34,67,89,56[2],23,45,78,48,存放在一个一维数组Data[]中,请使用快速排序算法完成该序列的排序, python
时间: 2024-09-26 07:02:12 浏览: 5
快速排序是一种高效的排序算法,通过分治策略来实现。在这个例子中,我会演示如何使用Python实现快速排序来对给定的一维数组进行排序。
首先,我们需要定义一个辅助函数`partition()`来划分数组,并选择第一个元素作为基准值(pivot)。然后,快速排序函数`quick_sort()`递归地对左右两部分进行排序。
```python
def partition(Data, low, high):
pivot = Data[low] # 基准值
i = low + 1
j = high
while True:
# 寻找比基准值小的数
while i <= j and Data[i] < pivot:
i += 1
# 寻找比基准值大的数
while i <= j and Data[j] > pivot:
j -= 1
if i <= j:
# 交换元素
Data[i], Data[j] = Data[j], Data[i]
else:
break
# 将基准值放回正确位置
Data[low], Data[j] = Data[j], Data[low]
return j
def quick_sort(Data, low, high):
if low < high:
# 找到分区点并进行分割
pi = partition(Data, low, high)
# 对左右子数组分别递归调用快速排序
quick_sort(Data, low, pi - 1)
quick_sort(Data, pi + 1, high)
# 示例输入数据
Data = [56[1], 34, 67, 89, 56[2], 23, 45, 78, 48]
size = len(Data)
# 调用快速排序函数
quick_sort(Data, 0, size - 1)
print("排序后的数组: ", Data)