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

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”用于列表。在 Python 中 Array是比 list 更具体的东西。