下面是使用快速排序和中位数划分方案来实现原地排序的 Python 代码:def median_quicksort(arr, reverse=False): def partition(arr, low, high): pivot_index = find_median(arr, low, high) pivot = arr[pivot_index] # Move pivot to the end arr[pivot_index], arr[high] = arr[high], arr[pivot_index] i = low for j in range(low, high): if arr[j] < pivot: arr[i], arr[j] = arr[j], arr[i] i += 1 # Move pivot to its final position arr[i], arr[high] = arr[high], arr[i] return i def find_median(arr, low, high): mid = (low + high) // 2 if arr[low] > arr[mid]: arr[low], arr[mid] = arr[mid], arr[low] if arr[low] > arr[high]: arr[low], arr[high] = arr[high], arr[low] if arr[mid] > arr[high]: arr[mid], arr[high] = arr[high], arr[mid] return mid def quicksort(arr, low, high): if low < high: pivot_index = partition(arr, low, high) quicksort(arr, low, pivot_index - 1) quicksort(arr, pivot_index + 1, high) n = len(arr) quicksort(arr, 0, n - 1) if reverse: arr.reverse()
这段代码定义了一个名为median_quicksort()的函数,它使用快速排序算法和中位数划分方案对给定的浮点数列表进行原地排序。参数reverse用于选择排序的方向,如果reverse为True,则按降序排序。
在函数内部,有三个辅助函数:partition()、find_median()和quicksort()。partition()函数用于执行中位数划分,find_median()函数用于找到一个近似的中位数索引,quicksort()函数用于递归地排序子数组。
代码通过调用quicksort()函数来对整个数组进行排序。如果reverse参数为True,则使用arr.reverse()反转数组以实现降序排序。
这样,你可以调用median_quicksort()函数来对浮点数列表进行排序,例如:my_list = [3.14, 2.71, 1.0, 4.5, 2.0]median_quicksort(my_list)print(my_list) # 输出: [1.0, 2.0, 2.71, 3.14, 4.5]my_list = [3.14, 2.71, 1.0, 4.5, 2.0]median_quicksort(my_list, reverse=True)print(my_list) # 输出: [4.5, 3.14, 2.71, 2.0, 1.0]
希望这个回答对你有所帮助!
球一个最佳答案谢谢啦!这对我非常重要! |