文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >问答首页 >Python中的Introsort，有人能指出我的错误吗？

问Python中的Introsort，有人能指出我的错误吗？
EN

Stack Overflow用户
提问于 2018-02-04 23:47:43
回答 2查看 728关注 0票数 3

试图使用Python实现Intro排序。

给出的伪码是：

代码语言：javascript
复制
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)

我的源代码是：

代码语言：javascript
复制
import math

def introSort(a,d):
    n = len(a)
    if n <= 1:
        return
    elif d == 0:
        heapSort(a)
    else:
        p = partition(a)
        a1 = a[0:p]
        a2 = a[p+1:n]
        introSort(a1, d-1)
        introSort(a2, d-1)
        a = a1 + [a[p]] + a2

def heapSort (a):
    END = len(a)
    for k in range (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):
    x = a[len(a) - 1]
    i = -1
    for j in range(0, len(a) - 2):
        if a[j] <= x:
            i = i + 1
            swap(a, i, j)
    swap(a, i + 1, len(a) - 1)
    return i + 1

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]

introSort(a,2)

print(a)

给出的结果是错误的：

代码语言：javascript
复制
>python introsort.py
[3, 5, 6, 1, 15, 7, 21, 632, 123, 53, 62, 421, 23, 672, 521, 435, 6243]

它似乎在分区之后就停止了，子列表上的排序也不起作用。很明显，21是支点，分区工作得很好。

有人能指出我的错误吗？非常感谢!

python
algorithm
introsort
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2018-02-05 20:40:59

实际上，我通过使用一个助手函数来修正这个问题，该函数调用列表中的一个片段上的堆排序。我不是通过修改堆排序函数来完成这个任务的，而是在一个单独的副本中这样做，并将排序的元素更新回原来的列表中。所示代码如下：

代码语言：javascript
复制
import math

def introSort(a, d, start, end):
    n = end - start
    if n <= 1:
        return
    elif d == 0:
        introHS(a, start, end)
    else:
        p = partition(a, start, end)
        introSort(a, d-1, start, p)
        introSort(a, d-1, p+1, end)

def introHS (a, start, end):
    b = a[start:end]
    heapSort(b)
    for i in range(0,len(b)):
        a[start+i] = b[i]

def heapSort (a):
    END = len(a)
    for k in range (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, start, end):
    x = a[end-1]
    i = start-1
    for j in range(start, end-1):
        if a[j] <= x:
            i=i+1
            swap(a, i, j)
    swap(a, i+1, end-1)
    return i+1

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

它通过以下几个方面的测试工作得很好：

代码语言：javascript
复制
a = [3,5,6,1,23,521,6243,632,123,53,62,421,15,672,7,435,21,123,41,52,6234,11,55,6345,324,58,46,2,123,152,6156,46,34,3426,5341,16,3314,34,73416,345]
print("Original:")
print(a)
for i in range(0,15):
    introSort(a,i,0,len(a))
    print("d=" + str(i))
    print(a)

给予：

代码语言：javascript
复制
>Original:
>[3, 5, 6, 1, 23, 521, 6243, 632, 123, 53, 62, 421, 15, 672, 7, 435, 21, 123, 41, 52, 6234, 11, 55, 6345, 324, 58, 46, 2, 123, 152, 6156, 46, 34, 3426, 5341, 16, 3314, 34, 73416, 345]
>d=0
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=1
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=2
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=3
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=4
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=5
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=6
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=7
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=8
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=9
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=10
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=11
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=12
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=13
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
>d=14
>[1, 2, 3, 5, 6, 7, 11, 15, 16, 21, 23, 34, 34, 41, 46, 46, 52, 53, 55, 58, 62, 123, 123, 123, 152, 324, 345, 421, 435, 521, 632, 672, 3314, 3426, 5341, 6156, 6234, 6243, 6345, 73416]
票数 1
EN

Stack Overflow用户

发布于 2018-02-05 07:04:40

删除

代码语言：javascript
复制
a = a1 + [a[p]] + a2

和插入

代码语言：javascript
复制
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)

完整代码：

代码语言：javascript
复制
#!/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中的引用的答案。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：

https://stackoverflow.com/questions/48614165

复制
相关文章

相似问题

领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档