结合了插入排序和快速排序的混合算法

Question

我正在尝试实现一种结合了插入排序和快速排序的混合算法，以便以这种方式获得两者所需的功能，以便当快速排序步骤中的元素少于 50 个时，使用插入排序对于大于 50 的元素，将使用快速排序算法合并。我尝试通过将原始列表的切片实例作为参数传递给 pivot_index 左侧的元素和 pivot_index 右侧的元素，如果它们小于 50，则使用插入排序我的 insertionSort 函数，但我的列表保持不变，分区但未排序。任何解决此问题的指示器将不胜感激。

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)

Answer 1

切片列表会生成原始子列表的浅表副本，因此不会通过将切片实例传递给 insertionSort 来修改原始列表。这就是为什么在您的代码中分区后列表没有排序的原因。

要应用插入排序 in-place，您可以将 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 大得多才能正确测试函数，否则你只是在测试插入排序。

结合了插入排序和快速排序的混合算法

Hybrid algorithm that combines Insertion Sort and Quick Sort

python

sorting

data-structures

python-3.x