python之插入排序对于逆序数组来说快得离谱

我要疯了。我有 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 

请您参考如下方法:

您的测试是错误的，因为除了您进行的第一次排序(使用 BubbleSort)之外，所有其他排序函数都将获得已经排序的数组。发生这种情况是因为您并没有真正复制具有以下代码的列表:

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

这些都引用了相同的列表。因此，如果 BubbleSort 对该列表进行排序，那么使用这些变量中的哪一个都没有关系:您得到的是已排序列表。

你应该这样做:

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

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

NB2:不要将名称“Array”用于列表。在 Python 中 Array是比 list 更具体的东西。