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