題目

已知一個(gè)幾乎有序的數(shù)組，幾乎有序是指，如果把數(shù)組排好順序的話，每個(gè)元素移動(dòng)的距離可以不超過k，并且k相對(duì)于數(shù)組來說比較小。請(qǐng)選擇一個(gè)合適的排序算法針對(duì)這個(gè)數(shù)據(jù)進(jìn)行排序。
給定一個(gè)int數(shù)組A，同時(shí)給定A的大小n和題意中的k，請(qǐng)返回排序后的數(shù)組。

測(cè)試用例 [2,1,4,3,6,5,8,7,10,9],10,2
返回 [1,2,3,4,5,6,7,8,9,10]

思路

比較直觀的一種想法是直接插入排序，每次插入的時(shí)間復(fù)雜度是O(k)，所以總的時(shí)間復(fù)雜度是O(n*k)的,空間復(fù)雜度是O(1)。
還有一種解法是利用堆排序，維護(hù)一個(gè)大小為k的小根堆(類比滑動(dòng)窗口)。在遍歷數(shù)組的過程中，將根推出并賦值給原數(shù)組，在根部插入數(shù)組的下一個(gè)元素。然后從根部開始下沉,維護(hù)堆有序。當(dāng)窗口到達(dá)數(shù)組的末尾后，直接進(jìn)行普通的堆排序，依次推出最小根即可。插入元素并維護(hù)堆有序的時(shí)間復(fù)雜度是O(lgk),總的時(shí)間復(fù)雜度是O(n*lgk),空間復(fù)雜度是O(k)。

代碼如下，小根堆是通過下沉排序操作構(gòu)建的。

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];
        }
        //建立一個(gè)小根堆,由aux[]數(shù)組組成
        for (int i = (k - 2) / 2; i >= 0; i--) {
            sink(aux, i, k - 1);
        }
        //每次取出小根堆的根，換為新的元素，再sink維護(hù)小根堆
        for (int i = 0; i < n - k; i++) {
            A[i] = aux[0];
            aux[0] = A[i + k];
            sink(aux, 0, k - 1);
        }
        //將根和尾節(jié)點(diǎn)交換，完成堆排序
        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;
    }
}