对列表的一部分进行原地排序

Question

假设我们有一个列表：

a = [4, 8, 1, 7, 3, 0, 5, 2, 6, 9]

现在，a.sort()会就地排序列表。如果我们想要只对列表的一部分进行排序，同时仍然就地排序，该怎么办？在C++中，我们可以这样写：

int array = { 4, 8, 1, 7, 3, 0, 5, 2, 6, 9 };
int * ptr = array;
std::sort( ptr + 1, ptr + 4 );

在Python中有类似的方法吗？

- Headcrab

---

为什么只需要就地排序？ - Matthew Schinckel

我认为将这个功能请求加入Python是件好事。它只是标准sort()方法的可选参数开始和结束。 - Justin Peel

原地排序的一个好理由是当你想要对列表的末尾进行排序（该列表已经基本排序，可能是通过一种较便宜的键函数），然后弹出最后一个值。在构建大多数贪婪TSP解决方案时遇到了这种用例。很可能会采用@fviktor提供的解决方案。 - Jostikas

Answer 1

我会这样写:

a[i:j] = sorted(a[i:j])

这也不是原地排序，但对于相对较小的数据段来说速度足够快。

请注意，Python仅复制对象引用，因此与实际原地排序相比速度惩罚不会太大，正如人们所期望的那样。

- fviktor

---

OP实际上要求整数。对于整数数组，复制引用不应该比复制实际值快很多。 - log0

问题并没有说明列表只能包含整数。C++示例确实对整数进行了操作，但这并不意味着问题仅限于此。 - fviktor

我认为这不如使用快速排序好，因为它需要额外的O(N)内存，而快速排序只需要额外的O(1)内存。我在下面留了一个快速排序实现的答案。 - Goodword

这不是一个原地排序。 - Jonathan

Answer 2

如果a是一个numpy数组，要原地排序[i, j)范围内的元素，那么请输入以下代码：

```python a[i:j].sort() ```

a[i:j].sort()

示例：

>>> import numpy as np
>>> a = np.array([4, 8, 1, 7, 3, 0, 5, 2, 6, 9])
>>> a[1:4].sort()
>>> a
array([4, 1, 7, 8, 3, 0, 5, 2, 6, 9])

- jfs

---

我们不想使用numpy。 - GilbertS

它同样适用于常规列表（而非NumPy数组）（至少在Python 3.10中）。 - undefined

@YuriiMotov 它不会：https://replit.com/@zed1/InplaceSliceSort#main.py - undefined

Answer 3

要在两个索引之间进行排序，我建议使用快速排序。与array[start:end] = sorted(arr[start:end])相比，快速排序的优点是不需要任何额外的内存，而分配给切片需要O(n)的额外内存。

我认为标准库中没有实现，但自己编写很容易。以下是一个实现，我从https://www.geeksforgeeks.org/quicksort-using-random-pivoting/复制并粘贴的。

import random 

def quicksort(arr, start , stop): 
    if(start < stop): 
        pivotindex = partitionrand(arr, start, stop) 
        quicksort(arr , start , pivotindex - 1) 
        quicksort(arr, pivotindex + 1, stop) 


def partitionrand(arr , start, stop): 

    randpivot = random.randrange(start, stop) 

    arr[start], arr[randpivot] = arr[randpivot], arr[start] 
    return partition(arr, start, stop) 


def partition(arr,start,stop): 
    pivot = start # pivot 
    i = start + 1 # a variable to memorize where the  
                  # partition in the array starts from. 
    for j in range(start + 1, stop + 1): 
        if arr[j] <= arr[pivot]: 
            arr[i] , arr[j] = arr[j] , arr[i] 
            i = i + 1
    arr[pivot] , arr[i - 1] = arr[i - 1] , arr[pivot] 
    pivot = i - 1
    return (pivot) 

要在你的示例中排序索引2和6之间（包括范围），我会这样做：

array = [4, 8, 1, 7, 3, 0, 5, 2, 6, 9]
quicksort(array, 2, 6) 
print(array) 

- Goodword

---

尽管在Python中实现的原地排序功能，复制并调用C中的sort函数几乎总是更好。 - undefined