我要疯了。我有 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
更具体的东西。
关于python - 插入排序对于逆序数组来说快得离谱,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59117897/