对于反序数组，插入排序的速度快得离谱

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”用于list。在Python语言中，Array不仅仅是一个list，它是更具体的东西。