使用快速排序就地排序 - 适用于包含整数的列表但不适用于包含元组的列表。为什么？
In place sorting using Quicksort - works for list containing integers but not for list containing tuples. Why?
当列表包含单个项目时，我的快速排序算法可以很好地对列表进行就地排序。例如
'''
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0]
lower,upper = 1,1
#all elements from 1 to lower-1 is lower than or equal to the pivot
#all elements from lower to upper-1 is greater than pivot
for i in range(1,len(l)):
if l[i] > pivot:
upper += 1
else:
l[i],l[lower] = l[lower],l[i]
upper += 1
lower += 1
l[0],l[lower-1] = l[lower-1],l[0]
#pivot is now at index lower-1
#recursive calls to left of the pivot and to the right of the pivot
quicksort(l[:lower-1])
quicksort(l[lower:])
q = [4,5,8,9,4,12]
quicksort(q)
print(q)
结果输出符合预期：
[4, 4, 8, 9, 5, 12]
但是，当我尝试根据元组的特定索引对包含元组的列表进行排序时，列表未就地排序。例如：
我有清单：
L = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
并且我根据每个元组的索引号 2 对其进行排序，也就是说，我希望所有在第二个索引处具有 'F' 的元组都排在具有 'M' 的元组之前.
我写了下面的代码，稍微修改了原来的快速排序：
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0][2]
lower,upper = 1,1
#all elements from 1 to lower-1 is lower than or equal to the pivot
#all elements from lower to upper-1 is greater than pivot
for i in range(1,len(l)):
if l[i][2] > pivot:
upper += 1
else:
l[i],l[lower] = l[lower],l[i]
upper += 1
lower += 1
l[0],l[lower-1] = l[lower-1],l[0]
#pivot is now at index lower-1
quicksort(l[:lower-1])
quicksort(l[lower:])
L = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
quicksort(L)
print(L)
但我得到的输出是
[('Rani', 10, 'F'), ('Ishan', 4, 'M'), ('Priya', 4, 'F'), ('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'), ('Neha', 3, 'F'), ('Akash', 8, 'M'), ('Gauri', 6, 'F'), ('Hema', 0, 'F'), ('Ajay', 1, 'M')]
我不明白为什么它在一种情况下有效而在另一种情况下无效。
这条线并没有像你想象的那样做：
quicksort(l[:lower-1])
该语句实际上创建了一个 new sub-list 然后对其进行排序，它没有触及 original 列表。同上 sub-lists 等等。
它在您的整数列表上起作用的唯一原因是因为 那个 列表在 first 遍（修改原始列表）在 任何递归发生之前。如果您将原始列表更改为更无序的内容，您会看到 它 也失败了：
[5, 9, 2, 8, 3, 7, 4, 6, 5] ->
[5, 2, 3, 4, 5, 7, 8, 6, 9]
您最好在每个递归级别传递整个（原始）列表，并仅指定要排序的部分的上限和下限。例如，像这样：
def quicksort(coll, start=None, end=None):
# Allow simpler call.
if start is None:
start, end = 0, len(coll)
# Recursion terminator - one-element range is sorted by definition.
if end - start <= 1:
return
# Pivot on first element in range, prepare new pivot position.
pivot = coll[start]
new_pos = start + 1
# Process every element in range (other than pivot).
for i in range(start + 1, end):
# Correctly allocate to below/above-pivot sections.
if coll[i] < pivot:
if i != new_pos:
coll[i], coll[new_pos] = coll[new_pos], coll[i]
new_pos += 1
# Make order below-pivot, pivot, above-pivot.
coll[start], coll[new_pos-1] = coll[new_pos-1], coll[start]
# Recursively sort areas below and above that pivot point.
quicksort(coll, start, new_pos)
quicksort(coll, new_pos, end)
test_data = [24, 21, 22, 23, 20, 25, 5, 9, 2, 8, 3, 37, 34, 6, 5]
print(test_data)
quicksort(test_data)
print(test_data)
您可以在那里看到一些变化，例如：
- 已经提到的整个列表的传递以及限制排序区域的边界（针对您的特定问题的修复）。
- 删除不必要的
upper 变量，因为您只需要枢轴的新位置来进行交换和递归。
- 更具描述性的变量名称。
- 其他各种小事，因为，好吧，...强迫症 :-)
而且，为了完整起见，您可以为 元组 列表使用以下（非常相似）代码：
def quicksort(coll, start=None, end=None):
# Allow simpler call.
if start is None:
start, end = 0, len(coll)
# Recursion terminator - one-element range is sorted by definition.
if end - start <= 1:
return
# Pivot on first element in range, prepare new pivot position.
pivot = coll[start][2]
#SPEC: pivot = (coll[start][2], coll[start][0], coll[start][1])
new_pos = start + 1
# Process every element in range (other than pivot).
for i in range(start + 1, end):
# Correctly allocate to below/above-pivot sections.
if coll[i][2] < pivot:
#SPEC: if (coll[i][2], coll[i][0], coll[i][1]) < pivot:
if i != new_pos:
coll[i], coll[new_pos] = coll[new_pos], coll[i]
new_pos += 1
# Make order below-pivot, pivot, above-pivot.
coll[start], coll[new_pos-1] = coll[new_pos-1], coll[start]
# Recursively sort areas below and above that pivot point.
quicksort(coll, start, new_pos)
quicksort(coll, new_pos, end)
test_data = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
print(test_data)
quicksort(test_data)
print(test_data)
结果符合预期：
[('Ajay', 1, 'M'), ('Ishan', 4, 'M'), ('Priya', 4, 'F'),
('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'), ('Neha', 3, 'F'),
('Akash', 8, 'M'), ('Gauri', 6, 'F'), ('Hema', 0, 'F'),
('Rani', 10, 'F')]
[('Rani', 10, 'F'), ('Priya', 4, 'F'), ('Neha', 3, 'F'),
('Gauri', 6, 'F'), ('Hema', 0, 'F'), ('Ajay', 1, 'M'),
('Akash', 8, 'M'), ('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'),
('Ishan', 4, 'M')]
如果您想使用 multi-field 键排序（在给定的示例中，性别，然后是姓名，然后是值），请参阅标有 #SPEC: 注释的行。
当列表包含单个项目时，我的快速排序算法可以很好地对列表进行就地排序。例如 '''
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0]
lower,upper = 1,1
#all elements from 1 to lower-1 is lower than or equal to the pivot
#all elements from lower to upper-1 is greater than pivot
for i in range(1,len(l)):
if l[i] > pivot:
upper += 1
else:
l[i],l[lower] = l[lower],l[i]
upper += 1
lower += 1
l[0],l[lower-1] = l[lower-1],l[0]
#pivot is now at index lower-1
#recursive calls to left of the pivot and to the right of the pivot
quicksort(l[:lower-1])
quicksort(l[lower:])
q = [4,5,8,9,4,12]
quicksort(q)
print(q)
结果输出符合预期：
[4, 4, 8, 9, 5, 12]
但是，当我尝试根据元组的特定索引对包含元组的列表进行排序时，列表未就地排序。例如：
我有清单：
L = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
并且我根据每个元组的索引号 2 对其进行排序，也就是说，我希望所有在第二个索引处具有 'F' 的元组都排在具有 'M' 的元组之前.
我写了下面的代码，稍微修改了原来的快速排序：
def quicksort(l):
if len(l) <= 1:
return l
pivot = l[0][2]
lower,upper = 1,1
#all elements from 1 to lower-1 is lower than or equal to the pivot
#all elements from lower to upper-1 is greater than pivot
for i in range(1,len(l)):
if l[i][2] > pivot:
upper += 1
else:
l[i],l[lower] = l[lower],l[i]
upper += 1
lower += 1
l[0],l[lower-1] = l[lower-1],l[0]
#pivot is now at index lower-1
quicksort(l[:lower-1])
quicksort(l[lower:])
L = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
quicksort(L)
print(L)
但我得到的输出是
[('Rani', 10, 'F'), ('Ishan', 4, 'M'), ('Priya', 4, 'F'), ('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'), ('Neha', 3, 'F'), ('Akash', 8, 'M'), ('Gauri', 6, 'F'), ('Hema', 0, 'F'), ('Ajay', 1, 'M')]
我不明白为什么它在一种情况下有效而在另一种情况下无效。
这条线并没有像你想象的那样做：
quicksort(l[:lower-1])
该语句实际上创建了一个 new sub-list 然后对其进行排序，它没有触及 original 列表。同上 sub-lists 等等。
它在您的整数列表上起作用的唯一原因是因为 那个 列表在 first 遍（修改原始列表）在 任何递归发生之前。如果您将原始列表更改为更无序的内容，您会看到 它 也失败了：
[5, 9, 2, 8, 3, 7, 4, 6, 5] ->
[5, 2, 3, 4, 5, 7, 8, 6, 9]
您最好在每个递归级别传递整个（原始）列表，并仅指定要排序的部分的上限和下限。例如，像这样：
def quicksort(coll, start=None, end=None):
# Allow simpler call.
if start is None:
start, end = 0, len(coll)
# Recursion terminator - one-element range is sorted by definition.
if end - start <= 1:
return
# Pivot on first element in range, prepare new pivot position.
pivot = coll[start]
new_pos = start + 1
# Process every element in range (other than pivot).
for i in range(start + 1, end):
# Correctly allocate to below/above-pivot sections.
if coll[i] < pivot:
if i != new_pos:
coll[i], coll[new_pos] = coll[new_pos], coll[i]
new_pos += 1
# Make order below-pivot, pivot, above-pivot.
coll[start], coll[new_pos-1] = coll[new_pos-1], coll[start]
# Recursively sort areas below and above that pivot point.
quicksort(coll, start, new_pos)
quicksort(coll, new_pos, end)
test_data = [24, 21, 22, 23, 20, 25, 5, 9, 2, 8, 3, 37, 34, 6, 5]
print(test_data)
quicksort(test_data)
print(test_data)
您可以在那里看到一些变化，例如：
- 已经提到的整个列表的传递以及限制排序区域的边界（针对您的特定问题的修复）。
- 删除不必要的
upper变量，因为您只需要枢轴的新位置来进行交换和递归。 - 更具描述性的变量名称。
- 其他各种小事，因为，好吧，...强迫症 :-)
而且，为了完整起见，您可以为 元组 列表使用以下（非常相似）代码：
def quicksort(coll, start=None, end=None):
# Allow simpler call.
if start is None:
start, end = 0, len(coll)
# Recursion terminator - one-element range is sorted by definition.
if end - start <= 1:
return
# Pivot on first element in range, prepare new pivot position.
pivot = coll[start][2]
#SPEC: pivot = (coll[start][2], coll[start][0], coll[start][1])
new_pos = start + 1
# Process every element in range (other than pivot).
for i in range(start + 1, end):
# Correctly allocate to below/above-pivot sections.
if coll[i][2] < pivot:
#SPEC: if (coll[i][2], coll[i][0], coll[i][1]) < pivot:
if i != new_pos:
coll[i], coll[new_pos] = coll[new_pos], coll[i]
new_pos += 1
# Make order below-pivot, pivot, above-pivot.
coll[start], coll[new_pos-1] = coll[new_pos-1], coll[start]
# Recursively sort areas below and above that pivot point.
quicksort(coll, start, new_pos)
quicksort(coll, new_pos, end)
test_data = [('Ajay',1,'M'),('Ishan',4,'M'),('Priya',4,'F'),('Ravi',7,'M'),('Dheeraj',2,'M'),('Neha',3,'F'),('Akash',8,'M'),('Gauri',6,'F'),('Hema',0,'F'),('Rani',10,'F')]
print(test_data)
quicksort(test_data)
print(test_data)
结果符合预期：
[('Ajay', 1, 'M'), ('Ishan', 4, 'M'), ('Priya', 4, 'F'),
('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'), ('Neha', 3, 'F'),
('Akash', 8, 'M'), ('Gauri', 6, 'F'), ('Hema', 0, 'F'),
('Rani', 10, 'F')]
[('Rani', 10, 'F'), ('Priya', 4, 'F'), ('Neha', 3, 'F'),
('Gauri', 6, 'F'), ('Hema', 0, 'F'), ('Ajay', 1, 'M'),
('Akash', 8, 'M'), ('Ravi', 7, 'M'), ('Dheeraj', 2, 'M'),
('Ishan', 4, 'M')]
如果您想使用 multi-field 键排序（在给定的示例中，性别，然后是姓名，然后是值），请参阅标有 #SPEC: 注释的行。