Python的介绍，有人能指出我的错误吗？

Question

尝试使用Python实现Introsort。在

给出的伪代码是：

1 n ←|A| 
2 if n ≤ 1 
3 return 
4 elseif d = 0 
5 Heap-Sort(A) 
6 else 
7 p ← Partition(A) // Partitions A and returns pivot position 
8 Intro-Sort(A[0:p],d−1) 
9 Intro-Sort(A[p+1:n],d−1)

我的源代码是：

^{pr2}$

给出的结果是错误的：

>python introsort.py
[3, 5, 6, 1, 15, 7, 21, 632, 123, 53, 62, 421, 23, 672, 521, 435, 6243]

在子列表上排序似乎停止了，而且在子列表上也没有停止工作。很明显，21是轴心，隔板工作得很好。在

谁能指出我的错误吗？非常感谢你！在

Answer 1

删除

a = a1 + [a[p]] + a2

并插入

^{pr2}$

完整代码：

#!/usr/bin/python
import math


def introSort(a,d):
    n = len(a)
    if n <= 1:
        return
    elif d == 0:
        heapSort(a)
    else:
        p = partition(a)
        a1 = a[:p]
        a2 = a[p+1:n]
        introSort(a1, d-1)
        introSort(a2, d-1)
        for i in range(0, len(a1)):
            a.insert(i, a1[i])
            a.pop(i+1)
        for i in range(0, len(a2)-1):
            a.insert(i+p+1, a2[i])
            a.pop(i+p+2)

def heapSort (a):
    END = len(a)
    for k in range ( int(math.floor(END/2)) - 1, -1, -1):
        heapify(a, END, k)

    for k in range(END, 1, -1):
        swap(a, 0, k-1)
        heapify(a, k-1, 0)

def partition(a):
    hi = len(a)-1
    x = a[hi]
    i = 0
    for j in range(0, hi-1):
        if a[j] <= x:
            swap(a, i, j)
            i = i + 1
    swap(a, i, hi)
    return i

def swap(a, i, j):
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp

def heapify(a,iEnd,iRoot):
    iL = 2*iRoot + 1
    iR = 2*iRoot + 2
    if iR < iEnd:
        if (a[iRoot] >= a[iL] and a[iRoot] >= a[iR]):
            return

        else:
            if(a[iL] > a[iR]):
                j = iL
            else: 
                j = iR
            swap(a, iRoot, j)
            heapify(a, iEnd, j)
    elif iL < iEnd:
        if (a[iRoot] >= a[iL]):
            return
        else:
            swap(a, iRoot, iL)
            heapify(a,iEnd,iL)

    else: 
        return

a = [3,5,6,1,23,521,6243,632,123,53,62,421,15,672,7,435,21]
print(a)

introSort(a,2)

print(a)

另外，请参阅关于Python中引用的答案https://stackoverflow.com/a/986145/9210255