我正在嘗試實作一種混合演算法，該演算法結合了插入排序和快速排序，以便以這樣的方式獲得兩者的所需功能，以便在快速排序步驟中元素少于 50 時，使用插入排序并且大于 50使用快速排序演算法合并元素。我嘗試通過將原始串列的切片實體作為引數傳遞給我的 insertSort 函式，使用插入排序對 pivot_index 左側的元素和 pivot_index 右側的元素進行排序，如果它們小于 50，但我的串列仍然是相同，已磁區但未排序。任何解決此問題的指標將不勝感激。
from random import randint
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j 1] = arr[j]
j = j - 1
arr[j 1] = key
def partition(a, low, high): #lomuto partition scheme
i = low - 1 #directly to the left of our specified low-high range
pivot = a[high] #pivot is the last value in our range, the index equal to high parameter
for j in range(low, high):
if a[j] <= pivot:
i = 1
a[i], a[j] = a[j], a[i]
a[i 1], a[high] = a[high], a[i 1]
return i 1
def quicksort_inplace(a, low=0, high=None):
if high == None:
high = len(a) - 1
if low < high:
pivot_index = partition(a, low, high) #partition around pivot
print("The pivot_index is:", pivot_index)
print("Low is:", low)
print("High is:", high)
if pivot_index - low <= 50:
insertionSort(a[low:pivot_index])
elif high - pivot_index <= 50:
insertionSort(a[pivot_index 1:high])
else:
quicksort_inplace(a, low, pivot_index - 1) #sort lower half
quicksort_inplace(a, pivot_index 1, high) #sort upper half
def create_arr(size=10):
return [randint(0,50) for _ in range(size)]
arr = create_arr()
print(arr)
quicksort_inplace(arr)
print()
print("The sorted array is:", arr)
uj5u.com熱心網友回復：
對串列進行切片會導致原始子串列的淺拷貝，因此不會通過將切片實體傳遞給來修改原始子串列insertionSort。這就是為什么在您的代碼中磁區后串列沒有排序的原因。
要就地應用插入排序，您可以傳遞low和high作為引數：
def insertion_sort(arr, low, high):
for i in range(low 1, high 1):
j = i
while j > low and arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1
在磁區之前檢查大小是否低于閾值也會更有效。然后可以將quicksort_inplace函式重寫如下（THRESHOLD = 50在本例中為）：
def quicksort_inplace(a, low=0, high=None):
if high is None:
high = len(a) - 1
if low < high:
if high - low 1 < THRESHOLD:
# Size of the subarray is less than the threshold, insertion sort
insertion_sort(a, low, high)
return
# Size of the subarray is greater than the threshold, quicksort
pivot_index = partition(a, low, high)
print("The pivot_index is:", pivot_index)
print("Low is:", low)
print("High is:", high)
quicksort_inplace(a, low, pivot_index - 1)
quicksort_inplace(a, pivot_index 1, high)
如果閾值為 50，則測驗陣列顯然應該遠大于 10 才能正確測驗函式，否則您只是在測驗插入排序。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/427535.html
標籤：Python python-3.x 排序 数据结构
上一篇：最小增量數