就地排序列表的一部分

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 中有没有类似的方法呢？

Answer 1

如果你想在两个索引之间进行排序，我建议使用快速排序。快速排序的好处在于，它不需要额外的内存，而使用 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) 

Answer 2

如果 a 是一个 numpy 数组，想要对 [i, j) 这个范围内的元素进行原地排序，可以这样写：

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])

Answer 3

我会这样写：

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

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

请注意，Python 只复制对象的引用，所以和真正的原地排序相比，速度上的损失不会那么大，跟你想象的可能不太一样。