我想写一个 "快速排序 "算法的python脚本。
这是我的代码。
def quick_sort(sequence):
pivot = sequence.pop()
greater =[]
lower = []
for i in sequence:
if sequence[i] > pivot :
greater.append(sequence[i])
else:
lower.append(sequence[i])
return lower + pivot + greater
sequence = [1,6,3,5,9,6,0,9,3,5,12,37,33,65,55,454,45,len("good")]
quick_sort(sequence)
但我得到一个错误。
Traceback (most recent call last):
File "<string>", line 14, in <module>
File "<string>", line 7, in quick_sort
IndexError: list index out of range
谁能帮我解决这个错误？
根据注释，这个问题只想对一个列表进行排序。这很简单。要么这样做。
lst = sorted(lst)
或者，如果你不想使用等价操作符，
lst.sort()
就会自动排序
问题就出在这两行。
for i in sequence:
if sequence[i] > pivot :
在Python中 for x in _list 将在 价值观 的 _list，而不是指数。在你的例子中，这意味着在某些时候 i == 37 和 if 条件试图访问 sequence[37]，这就超出了范围。有两种方法可以解决这个问题。
for i in range(len(sequence)): 会给你指数。i 而不是用它作为索引（也是在您追加的行中）。就我个人而言，这是我的偏好--总体来说，它看起来更整洁。另外，请注意 lower 和 greater 是列表，而 pivot 是一个整数，所以你不能做的是 lower + pivot + greater - 你得包 pivot 在一个列表中，首先(lower + [pivot] + greater).
下面是我前段时间对Quick Sort的实现，也许对你设计和测试自己的Quick Sort算法有帮助。
import random
from typing import TypeVar, List
from scipy import stats
T = TypeVar('T')
def quick_sort(input_list: List[T]) -> List[T]:
""""
Returns an ascending sorted list;
Input variable is an integer or float array;
Theoretical Complexity: O(N*Log N) Time and O(N) Memory
"""
sort(input_list, 0, len(input_list) - 1)
return input_list
def sort(input_list: List[T], start_index: int, end_index: int) -> None:
"""Recursively sorts the two pivot-divided sublists;"""
if start_index >= end_index:
return
pivot_index = partition(input_list, start_index, end_index)
sort(input_list, start_index, pivot_index - 1)
sort(input_list, pivot_index + 1, end_index)
def partition(input_list: List[T], start_index: int, end_index: int) -> int:
"""
Returns the end index; Partitions a list into two sublists;
"""
pivot = input_list[start_index]
i, j = start_index + 1, end_index
while i <= j:
while input_list[i] < pivot and i < end_index:
i += 1
while input_list[j] > pivot:
j -= 1
if i < j:
temp = input_list[i]
input_list[i] = input_list[j]
input_list[j] = temp
i += 1
j -= 1
else:
break
input_list[start_index] = input_list[j]
input_list[j] = pivot
return j
if __name__ == "__main__":
# Creates a dash line string and a new line for in between the tests.
delimiter = "-" * 70 + "\n"
# Generates a random integer list.
test_list_integer = random.sample(range(-100, 100), 15) * 3
print(f"""The unsorted integer array is:
{test_list_integer}""")
print(delimiter)
# Generates a random float list.
test_list_float = stats.uniform(0, 100).rvs(45)
print(f"""The unsorted float array is:
{test_list_float}""")
print(delimiter)
# Sample float/integer test list for input.
integer_float_input = list(test_list_integer + test_list_float)
# Sample float/integer test list for output.
integer_float_output = sorted(integer_float_input)
sorting_algorithms = [
("Quick Sort", quick_sort)
]
# Testing
for description, func in sorting_algorithms:
if (func(integer_float_input.copy()) == integer_float_output):
print(f"{description} Test was Successful.")
else:
print(f"{description} Test was not Successful.")
print(f"""{description} (Integer):
{func(test_list_integer.copy())}""")
print(f"""{description} (Float):
{func(test_list_float.copy())}""")
print(delimiter)
The unsorted integer array is:
[-37, 74, -9, 58, 96, 82, 32, 94, -77, -54, -13, -10, -82, 57, 6, -37, 74, -9, 58, 96, 82, 32, 94, -77, -54, -13, -10, -82, 57, 6, -37, 74, -9, 58, 96, 82, 32, 94, -77, -54, -13, -10, -82, 57, 6]
----------------------------------------------------------------------
The unsorted float array is:
[ 4.46747765 21.96382498 21.00086463 49.15870339 95.19971828 94.5108942
1.88156027 49.1355604 78.5032007 32.4662292 15.0415828 75.04492651
29.491373 4.02412264 22.34068707 97.39317437 27.64026964 85.52244153
0.53119133 16.63664738 86.79522363 33.07979585 88.50108333 57.40225507
72.25826399 99.82793291 99.84493522 15.96858729 33.58735178 1.70611819
68.07308792 46.09522364 21.42563941 5.55154387 10.60707898 92.78939519
77.01866529 14.12783987 87.17625745 52.8310454 19.39884535 94.30883322
96.14062517 45.56022192 24.39705178]
----------------------------------------------------------------------
Quick Sort Test was Successful.
Quick Sort (Integer):
[-82, -82, -82, -77, -77, -77, -54, -54, -54, -37, -37, -37, -13, -13, -13, -10, -10, -10, -9, -9, -9, 6, 6, 6, 32, 32, 32, 57, 57, 57, 58, 58, 58, 74, 74, 74, 82, 82, 82, 94, 94, 94, 96, 96, 96]
Quick Sort (Float):
[ 0.53119133 1.70611819 1.88156027 4.02412264 4.46747765 5.55154387
10.60707898 14.12783987 15.0415828 15.96858729 16.63664738 19.39884535
21.00086463 21.42563941 21.96382498 22.34068707 24.39705178 27.64026964
29.491373 32.4662292 33.07979585 33.58735178 45.56022192 46.09522364
49.1355604 49.15870339 52.8310454 57.40225507 68.07308792 72.25826399
75.04492651 77.01866529 78.5032007 85.52244153 86.79522363 87.17625745
88.50108333 92.78939519 94.30883322 94.5108942 95.19971828 96.14062517
97.39317437 99.82793291 99.84493522]
----------------------------------------------------------------------
这里有一个很好的 执行情况的守则审查.