将插入排序实现为快速排序时出错

Question

我目前面临将插入排序实现为快速排序的问题。我这样做是为了当子列表小于某个值时，在子列表上调用插入排序而不是快速排序。我设法通过传递完整列表以及子列表的索引来使其工作，但是当我通过将子列表作为主列表的一部分传递来尝试它时，它不起作用。

有效的代码（传入子列表的索引）

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if (last - first +1) < 5:
       insertionSort(alist, first, last)
   else:
       splitpoint = partition(alist,first,last)
       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
   pivotvalue = alist[first]
   leftmark = first+1
   rightmark = last
   done = False
   while not done:
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1
       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1
       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp
   return rightmark

def insertionSort(alist, first, last):
   for index in range(1,last +1):
     currentvalue = alist[index]
     position = index
     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1
     alist[position]=currentvalue


alist = [54,26,93,17,77,31,44,55,20,1,3,5]
quickSort(alist)

print(alist)

不起作用的代码（将子列表作为主列表的一部分传入）

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if (last - first +1) < 5:
       insertionSort(alist[first:last +1])
   else:
       splitpoint = partition(alist,first,last)
       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
   pivotvalue = alist[first]
   leftmark = first+1
   rightmark = last
   done = False
   while not done:
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1
       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1
       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp
   return rightmark

def insertionSort(alist):
   for index in range(1, len(alist)):
     currentvalue = alist[index]
     position = index
     while position>0 and alist[position-1]>currentvalue:
         alist[position]=alist[position-1]
         position = position-1
     alist[position]=currentvalue


alist = [54,26,93,17,77,31,44,55,20,1,3,5]
quickSort(alist)

print(alist)

我试过调试它，基本上发生的事情是一旦插入排序完成对子数组的排序并且它 returns 到以前的递归函数，数组返回到它以前的 'unsorted' self .非常感谢任何建议，谢谢大家。

Answer 1

在您的第一个片段中，当您调用

insertionSort(alist, first, last)

然后使用

for index in range(1, last+1):

您正在迭代 last 次。
您正在对原始 alist 进行操作（任何更改都会反映在 alist 上）。

在你的第二个片段中，当你调用

insertionSort(alist[first:last +1])

然后使用

for index in range(1, len(alist)):

您正在迭代 last - first + 1 次。
您正在对原始 alist 的（切片）副本进行操作（任何更改都不会反映在 alist 上）。

Answer 2

根据中所说的内容，您需要 return 来自 insertionSort 的排序列表，并在原始列表中分配排序值。您可以使用与函数调用中使用的相同的切片来分配：

alist[first:last +1] = insertionSort(alist[first:last +1])

将插入排序实现为快速排序时出错

Error implementing insertion sort into quicksort

python

quicksort

insertion-sort