我正在尝试在Python中实现自然合并排序，我的get_sorted_run_length工作正常，但是我的natural_merge_sort正确地对列表的大部分进行了排序，但由于某种原因，没有对列表中的最后两个整数进行排序。我不知道为什么它不起作用，这是代码。
主.py
import sys
from NaturalMergeSorter import NaturalMergeSorter
from RunLengthTestCase import RunLengthTestCase
def main():
# Test case list: A completely sorted lst
list1 = [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
# Test case list: Sorted run of 3 followed by sorted run of 6
list2 = [64, 88, 91, 12, 21, 34, 43, 56, 65]
# Test case list: 5 elements in descending order, so 5 runs of length 1
list3 = [-10, -20, -30, -40, -50]
# Test case list: 8 equal elements, so 1 run of 8
list4 = [-99, -99, -99, -99, -99, -99, -99, -99]
test_cases = [
# First test case uses an out-of-bounds starting index. remaining test
# cases do not.
RunLengthTestCase(list1, len(list1), 0),
RunLengthTestCase(list1, 0, len(list1)),
RunLengthTestCase(list1, 3, len(list1) - 3),
RunLengthTestCase(list2, 0, 3),
RunLengthTestCase(list2, 2, 1),
RunLengthTestCase(list2, 3, 6),
RunLengthTestCase(list3, 0, 1),
RunLengthTestCase(list3, 3, 1),
RunLengthTestCase(list4, 0, len(list4)),
RunLengthTestCase(list4, 4, len(list4) - 4),
RunLengthTestCase(list4, 5, len(list4) - 5),
]
for test in (test_cases):
# Execute the test case, printing messages to sys.stdout
test.execute(sys.stdout)
# Test case lst for sorting
list5 = [92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22]
list5_copy = list(list5)
sorter = NaturalMergeSorter()
sorter.natural_merge_sort(list5_copy)
print(f"""
{'PASS' if list5_copy == sorted(list5) else 'FAIL'}: NaturalMergeSort()
List before calling natural_merge_sort(): {list5}
List after calling natural_merge_sort(): {list5_copy}""")
if __name__ == '__main__':
main()
运行长度测试用例.py
from NaturalMergeSorter import NaturalMergeSorter
class RunLengthTestCase:
def __init__(self, lst, start, expected_return):
self.lst = lst
self.start = start
self.expected_return = expected_return
# Executes the test case. If the test case passes, a message that starts
# with "PASS" is printed and true is returned. Otherwise a message that
# starts with "FAIL" is printed and false is returned.
def execute(self, test_feedback):
user_sorter = NaturalMergeSorter()
# Call the get_sorted_run_length() function with the test case parameters
user_ret_val = user_sorter.get_sorted_run_length(self.lst, self.start)
# The test passed only if the actual return value equals the
# expected return value
passed = user_ret_val == self.expected_return
if user_ret_val == self.expected_return:
print(f"""PASS: get_sorted_run_length()\n List: {self.lst}""", file=test_feedback)
print(f""" Start index: {self.start}""", file=test_feedback)
print(f""" Expected return value: {self.expected_return}""", file=test_feedback)
print(f""" Actual return value: {user_ret_val}""", file=test_feedback)
return True
else:
print(f"""FAIL: get_sorted_run_length()\n List: {self.lst}""", file=test_feedback)
print(f""" Start index: {self.start}""", file=test_feedback)
print(f""" Expected return value: {self.expected_return}""", file=test_feedback)
print(f""" Actual return value: {user_ret_val}""", file=test_feedback)
return False
class NaturalMergeSorter:
def __init__(self):
return
def get_sorted_run_length(self, integer_list, start_index):
if start_index < 0 or start_index >= len(integer_list):
return 0
r_length = 1
cur_index = start_index
while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
r_length += 1
cur_index += 1
return r_length
def get_sorted_run_length(self, integer_list, start_index):
if start_index < 0 or start_index >= len(integer_list):
return 0
r_length = 1
cur_index = start_index
while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
r_length += 1
cur_index += 1
return r_length
def natural_merge_sort(self, integer_list):
i = 0
while i < len(integer_list):
r1 = self.get_sorted_run_length(integer_list, i)
if i + r1 == len(integer_list):
break
r2 = self.get_sorted_run_length(integer_list, i + r1)
self.merge(integer_list, i, i + r1 - 1, i + r1 + r2 - 1)
if i + r1 + r2 == len(integer_list):
i = 0
else:
i = i + r1 + r2
def merge(self, numbers, left_first, left_last, right_last):
merged_size = right_last - left_first + 1
merged_numbers = [None] * merged_size
merge_pos = 0
left_pos = left_first
right_pos = left_last + 1
while left_pos <= left_last and right_pos <= right_last:
if numbers[left_pos] <= numbers[right_pos]:
merged_numbers[merge_pos] = numbers[left_pos]
left_pos += 1
else:
merged_numbers[merge_pos] = numbers[right_pos]
right_pos += 1
merge_pos += 1
while left_pos <= left_last:
merged_numbers[merge_pos] = numbers[left_pos]
left_pos += 1
merge_pos += 1
# If right partition isn't empty, add remaining elements to merged_numbers
while right_pos <= right_last:
merged_numbers[merge_pos] = numbers[right_pos]
right_pos += 1
merge_pos += 1
# Copy merged numbers back to numbers
for merge_pos in range(merged_size):
numbers[left_first + merge_pos] = merged_numbers[merge_pos]
自然合并排序器.py
class NaturalMergeSorter:
def __init__(self):
return
def get_sorted_run_length(self, integer_list, start_index):
if start_index < 0 or start_index >= len(integer_list):
return 0
r_length = 1
cur_index = start_index
while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
r_length += 1
cur_index += 1
return r_length
def get_sorted_run_length(self, integer_list, start_index):
if start_index < 0 or start_index >= len(integer_list):
return 0
r_length = 1
cur_index = start_index
while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
r_length += 1
cur_index += 1
return r_length
def natural_merge_sort(self, integer_list):
i = 0
while i < len(integer_list):
r1 = self.get_sorted_run_length(integer_list, i)
if i + r1 == len(integer_list):
break
r2 = self.get_sorted_run_length(integer_list, i + r1)
self.merge(integer_list, i, i + r1 - 1, i + r1 + r2 - 1)
if i + r1 + r2 == len(integer_list):
i = 0
else:
i = i + r1 + r2
def merge(self, numbers, left_first, left_last, right_last):
merged_size = right_last - left_first + 1
merged_numbers = [None] * merged_size
merge_pos = 0
left_pos = left_first
right_pos = left_last + 1
while left_pos <= left_last and right_pos <= right_last:
if numbers[left_pos] <= numbers[right_pos]:
merged_numbers[merge_pos] = numbers[left_pos]
left_pos += 1
else:
merged_numbers[merge_pos] = numbers[right_pos]
right_pos += 1
merge_pos += 1
while left_pos <= left_last:
merged_numbers[merge_pos] = numbers[left_pos]
left_pos += 1
merge_pos += 1
# If right partition isn't empty, add remaining elements to merged_numbers
while right_pos <= right_last:
merged_numbers[merge_pos] = numbers[right_pos]
right_pos += 1
merge_pos += 1
# Copy merged numbers back to numbers
for merge_pos in range(merged_size):
numbers[left_first + merge_pos] = merged_numbers[merge_pos]
这就是我得到的结果
PASS: get_sorted_run_length()
List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
Start index: 10
Expected return value: 0
Actual return value: 0
PASS: get_sorted_run_length()
List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
Start index: 0
Expected return value: 10
Actual return value: 10
PASS: get_sorted_run_length()
List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
Start index: 3
Expected return value: 7
Actual return value: 7
PASS: get_sorted_run_length()
List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
Start index: 0
Expected return value: 3
Actual return value: 3
PASS: get_sorted_run_length()
List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
Start index: 2
Expected return value: 1
Actual return value: 1
PASS: get_sorted_run_length()
List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
Start index: 3
Expected return value: 6
Actual return value: 6
PASS: get_sorted_run_length()
List: [-10, -20, -30, -40, -50]
Start index: 0
Expected return value: 1
Actual return value: 1
PASS: get_sorted_run_length()
List: [-10, -20, -30, -40, -50]
Start index: 3
Expected return value: 1
Actual return value: 1
PASS: get_sorted_run_length()
List: [-99, -99, -99, -99, -99, -99, -99, -99]
Start index: 0
Expected return value: 8
Actual return value: 8
PASS: get_sorted_run_length()
List: [-99, -99, -99, -99, -99, -99, -99, -99]
Start index: 4
Expected return value: 4
Actual return value: 4
PASS: get_sorted_run_length()
List: [-99, -99, -99, -99, -99, -99, -99, -99]
Start index: 5
Expected return value: 3
Actual return value: 3
FAIL: NaturalMergeSort()
List before calling natural_merge_sort(): [92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22]
List after calling natural_merge_sort(): [10, 18, 26, 39, 54, 71, 73, 89, 92, 99, 22, 64]
谢谢你
我认为这与这一行有关...如果列表中的最后两个元素在合并操作后没有完全排序，那么它仍然将 i 重置为 0。
if i + r1 + r2 == len(integer_list):
i = 0