题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过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]

思路

比较直观的一种想法是直接插入排序，每次插入的时间复杂度是O(k)，所以总的时间复杂度是O(n*k)的,空间复杂度是O(1)。
还有一种解法是利用堆排序，维护一个大小为k的小根堆(类比滑动窗口)。在遍历数组的过程中，将根推出并赋值给原数组，在根部插入数组的下一个元素。然后从根部开始下沉,维护堆有序。当窗口到达数组的末尾后，直接进行普通的堆排序，依次推出最小根即可。插入元素并维护堆有序的时间复杂度是O(lgk),总的时间复杂度是O(n*lgk),空间复杂度是O(k)。

代码如下，小根堆是通过下沉排序操作构建的。

import java.util.*;

public class ScaleSort {
    public int[] sortElement(int[] A, int n, int k) {
        int[] aux = new int[k];
        for (int i = 0; i < k; i++) {
            aux[i] = A[i];
        }
        //建立一个小根堆,由aux[]数组组成
        for (int i = (k - 2) / 2; i >= 0; i--) {
            sink(aux, i, k - 1);
        }
        //每次取出小根堆的根，换为新的元素，再sink维护小根堆
        for (int i = 0; i < n - k; i++) {
            A[i] = aux[0];
            aux[0] = A[i + k];
            sink(aux, 0, k - 1);
        }
        //将根和尾节点交换，完成堆排序
        for (int i = n - k; i < n; i++) {
            A[i] = aux[0];
            swap(aux, 0, k-1);
            k--;
            sink(aux, 0, k-1);
        }
        return A;

    }

    //下沉排序操作
    private void sink(int[] A, int lo, int hi) {
        int child;
        while ((child = 2 * lo + 1) <= hi) {
            if (child < hi && A[child] > A[child + 1]) child++;
            if (A[lo] <= A[child]) break;
            swap(A, lo, child);
            lo = child;
        }

    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}