题目描述
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过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]思路
因为元素移动距离不超过k，所以可以构造k项最小堆（在0-k的范围内必然可以找到正确的最小值），然后将最小堆的堆首(最小值)弹出，压入后一个值，反复进行这个过程即可得到有序数组，因为构建堆是常数时间，遍历数组时间复杂度是O(N),每次进行的下沉操作时间复杂度是O(lgK)，所以整个算法的时间复杂度是O(N*lgK)。这道题花了我将近一天的时间（醉了），原因是最后一个元素移入k项堆后的情况搞错了，详见代码。
class ScaleSort { public: //建立最小堆 void min_heap(vector<int> &A, int begin, int end){ int c = begin; int left = 2 * c + 1; int tmp = A[c]; while (left <= end){ if (left < end && A[left] > A[left + 1]) left++; if (A[c] < A[left]) break; else{ A[c] = A[left]; A[left] = tmp; } c = left; left = left * 2 + 1; } } vector<int> sortElement(vector<int> A, int n, int k) { // write code here for (int i = k / 2 - 1; i >= 0; i--){ min_heap(A, i, k); } int m = 0; for (int j = 0; j < n; j++){ if (j < n - k - 1){ res[j] = A[0]; A[0] = A[k + j+1]; min_heap(A, 0, k); } else{ //当最后几个元素都压入k项堆后，注意此时最后的k的元素所在的范围是A[0]-A[k]，并且弹出A[0]后需要把A[k]移到A[0]处， res[j] = A[0]; A[0] = A[k - m]; min_heap(A, 0 , k-m); m++; } } return res; } }; 另附上一篇讲解堆排序的文章，是我目前见过写得最好的文章： http://wangkuiwu.github.io/2013/05/06/heap-sort/