时间戳

首页 > 解决方案 > 无法在python中使用快速排序对数组进行排序

python - 无法在python中使用快速排序对数组进行排序

问题描述

目前我正在为数组编写排序代码.....但是由于一些错误我无法对我的数组进行排序，请您帮忙修复这些错误。

代码

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4,78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = l
    i = l+1
    j = h
    while i<j:
        while a[i] < a[p]:
            i += 1
        while a[j] > a[p]:
            j -= 1
        if i<j:
            a[i],a[j] = a[j],a[i]
    a[p],a[j] = a[j],a[p]
    return j

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        quick(l,j,a)
        quick(j+1,h,a)

quick(0,len(a)-1,a)
print(a)

标签： pythonsortingdata-structuresquicksort

解决方案

我不确定您从哪里获得该算法，但这里有一个基于您的代码的实际有效的算法。这是霍尔分区：

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4,78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = a[(h+l)//2]
    i = l-1
    j = h+1
    while True:
        i += 1
        while a[i] < p:
            i += 1
        j -= 1
        while a[j] > p:
            j -= 1
        if i >= j:
            return j
        a[i],a[j] = a[j],a[i]

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        quick(l,j,a)
        quick(j+1,h,a)

quick(0,len(a)-1,a)
print(a)

跟进

您的代码的问题是while您必须在 Python 中使用的do/while循环与他在视频中使用的循环不同。您需要在进入 while 循环之前执行一次操作。这有效：

# QUICK SORT 
import math

a = [34, 1, 3, 90, 34, -1, -4, 78, 6, 55, 20, -65]
a.append(math.inf)

def partition(l,h,a):
    p = a[l]
    i = l
    j = h
    while i < j:
        i += 1
        while a[i] <= p:
            i += 1
        j -= 1
        while a[j] > p:
            j -= 1
        if i < j:
            a[i],a[j] = a[j],a[i]
    a[l],a[j] = a[j],p
    return j

def quick(l,h,a):
    if l<h:
        j = partition(l,h,a)
        quick(l,j-1,a)
        quick(j+1,h,a)

quick(0,len(a)-1,a)
print(a)

推荐阅读