时间戳

首页 > 解决方案 > 算法未按预期对数组进行排序

python - 算法未按预期对数组进行排序

问题描述

我得到了以下带有 [3, 7, 5 ,2, 1, 4, 8] 输入的算法。据说这是 QuickSort 的一部分，它构造了一个分区位置。输出应该是 [3, 1, 2, 5, 7, 4, 8] 在此处输入图像描述

我使用了以下python代码：

def partition(x, s, d):
    v = x[s]
    i = s-1
    j = d+1
    while i < j:
        while True:
            i = i+1 
            if x[i] >=v:
                break
        while True:
            j = j-1 
            if x[j] <=v:
                break 
        if (i<j):
            x[i], x[j] = x[j], x[i]
            
    print (x)
    return j
    
    
x = [3, 7, 5, 2, 1, 4, 8]
partition(x, 1, 6)

我无法得到[3, 1, 2, 5, 7, 4, 8]据称这是正确的结果。请帮忙，我尝试了 s 和 d 的不同值，这很可能代表左右。

标签： pythonalgorithmquicksortdata-partitioning

解决方案

这是快速排序的分区算法。

由于我们使用while循环而不是 a do.. while（这是您的算法中提到的REPEAT... UNTIL），我们不需要 decrements和 increment d。

def partition(x, s, d):
    v = x[s]
    i = s
    j = d
    
    while i < j:
        while x[i] <= v:
            i += 1
        
        while x[j] >= v:
            j -= 1

        if (i<j):
            x[i], x[j] = x[j], x[i]
            
    print(x)
    return j
    
    
x = [3, 7, 5, 2, 1, 4, 8]
partition(x, 0, 6)


Output:

[3, 1, 2, 5, 7, 4, 8]

推荐阅读