反向排序数组的插入排序非常快

Question

我要疯了。我有4种排序算法的测试用例（气泡排序，选择排序，插入排序和合并排序）

我测试了有序数组，反向有序数组和随机数组。在每种情况下，插入排序都非常快。我测试了1k，5k和25k的数字。插入排序一定不能比合并排序快吗？对？（顺便说一句，在随机数数组的情况下，插入排序仍然更快，对于我的代码，插入排序始终是最快的算法。这肯定是错误的，但是哪里错了。。（我共享了所有代码）

Test Case for 1k Reversed Ordered Array: (in milis)

Bubble Sort run time: 512
Selection Sort run time: 154
Insertion Sort Run time: 1
Merge Sort run time: 19


test case for 5k reversed ordered number (in milis):

Bubble Sort run time: 11768
Selection Sort run time: 3613
Insertion Sort Run time: 4
Merge Sort run time: 100

Test Case for 25 k reversed ordered array

Bubble Sort run time: 303249
Selection Sort run time: 90469
Insertion Sort Run time: 20
Merge Sort run Zaman: 644

这是我的主要代码；

def CreateOrdered(Quantity):
    Array = []
    for i in range(Quantity):
        Array.append(i)
    return Array

def ReversedOrdered(Quantity):
    Array = []
    for i in range(Quantity):
        Array.append(Quantity-i)
    return Array

def RandomNumbers(Quantity):
    Array = []
    for i in range(Quantity):
        Array.append(randint(0,Quantity))
    return Array

Array = ReversedOrdered(1000)
ArrayCopyForSelection = Array
ArrayCopyForInsertion = Array
ArrayCopyForMerge = Array

BubbleSortStartTime = int(round(time.time() * 1000))
BubbleSort(Array)
BubbleSortStopTime = int(round(time.time() * 1000))

print("Bubble Sort run time: " + str(BubbleSortStopTime-BubbleSortStartTime))
print(" ")

SelectionStartTime = int(round(time.time() * 1000))
SelectionSort(ArrayCopyForSelection)
SelectionStopTime = int(round(time.time() * 1000))

print("Selection Sort run time: " + str(SelectionStopTime-SelectionStartTime))
print(" ")

InsertionStartTime = int(round(time.time() * 1000))
InsertionSort(ArrayCopyForInsertion)
InsertionStopTime = int(round(time.time() * 1000))

print("Insertion Sort Run time: " + str(InsertionStopTime-InsertionStartTime))
print(" ")


MergeStartTime = int(round(time.time() * 1000))
Merge(ArrayCopyForMerge)
MergeStopTime = int(round(time.time() * 1000))

print("Merge Sort run time: " + str(MergeStopTime-MergeStartTime))

这是我的排序算法：

from random import seed
from random import randint
import time

def BubbleSort(Array):
    for i in range(len(Array)):
        flag = False
        for j in range(len(Array) - 1 - i):
            if Array[j] >  Array[j+1]:
                Array[j], Array[j+1] = Array[j+1], Array[j]
                flag = True
        if flag == False:
            break
    return Array

def SelectionSort(Array):
    for i in range(len(Array)):
        MinimumIndex = i
        for j in range(i+1,len(Array)):
            if Array[j] < Array[MinimumIndex]:
                MinimumIndex = j

        temp = Array[i]
        Array[i] = Array[MinimumIndex]
        Array[MinimumIndex] = temp
    return Array

def InsertionSort(Array):

    for i in range(1,len(Array)):
        key = Array[i]
        j = i - 1

        while key < Array[j] and j >= 0:
            Array[j+1] = Array[j]
            j = j - 1
        Array[j+1] = key
    return Array

def Merge(Array):
    if len(Array) > 1:
        mid = len(Array) // 2
        leftHalf = Array[:mid]
        rightHalf = Array[mid:]

        Merge(leftHalf)
        Merge(rightHalf)
        MergeSort(Array, leftHalf, rightHalf)

def MergeSort(Array, leftHalf, rightHalf):

    i = 0
    j = 0
    k = 0

    while i < len(leftHalf) and j < len(rightHalf):
        if leftHalf[i] < rightHalf[j]:
            Array[k] = leftHalf[i]
            i = i + 1
        else:
            Array[k] = rightHalf[j]
            j = j + 1
        k = k + 1

    while i < len(leftHalf):
        Array[k] = leftHalf[i]
        i = i + 1
        k = k + 1

    while j < len(rightHalf):
        Array[k] = rightHalf[j]
        j = j + 1
        k = k + 1

Answer 1

您的测试是错误的，因为除了您进行的第一个排序（使用BubbleSort）外，所有其他排序函数都将获取已排序的数组。发生这种情况是因为您没有使用以下代码真正复制列表：

Array = ReversedOrdered(1000)
ArrayCopyForSelection = Array
ArrayCopyForInsertion = Array
ArrayCopyForMerge = Array

这些都引用相同的列表。因此，如果BubbleSort对列表进行排序，则使用哪个变量都没有关系：您将获得排序后的列表。

你应该做：

Array = ReversedOrdered(1000)
ArrayCopyForSelection = Array[:]
ArrayCopyForInsertion = Array[:]
ArrayCopyForMerge = Array[:]

注意：请考虑以小写字母开头您的变量和函数名称。最初的大写字母通常用于类名。

NB2：请勿使用名称“ Array”作为list。在Python中，数组比数组更具体list。