python - python中的插入排序，列表末尾有负数

Question

我使用排序算法对数字进行排序，例如正数，然后是负数（就地交换，您可以使用变量但不使用任何容器变量。假设我们没有更多的内存空间用于额外的容器）。所以首先排序的正数，然后是排序的负数。

我做到了，但我需要另一个for循环来对底片进行排序并将它们插入到列表的末尾。

我的问题：有没有办法修改第一个循环以达到相同的结果？（即：仅使用 1 个for循环）

例如：

x = [9, -3, 2, -7, -4, -1, 5, 4]

输出应该是：

[2, 4, 5, 9, -7, -4, -3, -1]

这是我的解决方案（但我使用了 2 个for循环，我只想使用 1 个）：

def insertion_sort(data):
    for i in range(1, len(data)):
        e = i
        while e > 0 and data[e - 1] > data[e]:
            data[e - 1], data[e] = data[e], data[e - 1]
            e -= 1
    for i in range(1, len(data)):
        e = i
        while e > 0 and data[e - 1] < 0:
            if data[e] < 0:
                if data[e - 1] < data[e]:
                    data[e - 1], data[e] = data[e], data[e - 1]
            data[e - 1], data[e] = data[e], data[e - 1]
            e -= 1
    print(data)

标签： pythonpython-3.xsorting

Answer 1

当数字开始为正时，您只需要找到枢轴值

def insertion_sort(data):

    pivot = -1
    for i in range(1, len(data)):
        e = i
        while e > 0 and data[e - 1] > data[e]:
            data[e - 1], data[e] = data[e], data[e - 1]
            if data[e] >= 0 and data[e-1] < 0:
                pivot = e
            e -= 1

    data[-pivot:], data[:-pivot] = data[:pivot], data[pivot:]
    print(data)