我要疯了。我有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
我要疯了。我测试了4种排序算法(气泡排序,选择排序,插入排序和合并排序)的测试用例,有序数组,反向有序数组和随机数组。在...