小范围排序

Description

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。

给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。

测试样例：

[2,1,4,3,6,5,8,7,10,9],10,2
返回：[1,2,3,4,5,6,7,8,9,10]

Solutions

1. 堆排序

　　堆排序实现最大不超过 K 次比较排序：

class ScaleSort:
    def sortElement(self, A, n, k):
        def heap_justify(h, i, size):
            j = 2 * i + 1
            while j < size:
                if j + 1 < size and h[j+1] < h[j]:
                    j += 1
                if h[i] <= h[j]:
                    break
                h[i], h[j] = h[j], h[i]
                i, j = j, 2*j+1
                
        def heap_build(arr, size):
            for i in range(size//2-1, -1, -1):
                heap_justify(arr, i, size)
            return arr
            
        if A is None or n <= 1:
            return A
        
        heap = heap_build(A[:k], k)
        for i in range(k, n):
            A[i-k] = heap[0]
            heap[0] = A[i]
            heap_justify(heap, 0, k)
        heap.sort()
        A[n-k:] = heap[:]
        return A

References

小范围排序