一、小范围排序

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

1.分析

(1)时间复杂度为O(n)的算法：计数排序和基数排序

  由于我们不知道这个数组的具体范围，故无法使用桶排序思想（不适用所有范围）。

(2)时间复杂度为O(n^2)的算法：冒泡排序、选择排序、插入排序

  对于冒泡排序、选择排序：这两种算法的排序与数组的原始序列无关，因此时间复杂度仍为O(n^2)。
  对于插入排序：由于每个元素移动的距离可以不超过k，因此在该问题中插入排序的每个元素向前插入的位置不会超过k，因此时间复杂度下降为O(n*k)。

(3)时间复杂度为O(n*log n)的算法：快速排序、归并排序、堆排序

  对于快速排序、归并排序：这两种算法的排序与数组的原始序列无关，因此时间复杂度仍为O(n*log n)。
  堆排序（改进）：每个元素移动的距离可以不超过k，因此数组的最小值一定在array[0] ~ array[k-1]中。因此以array[0] ~ array[k-1]建立小顶堆，然后将堆顶元素赋值给array[0]，然后从数组中插入array[k]到堆顶，重建小顶堆。如此反复，直到所有元素都插入到小顶堆中。最后数组中的元素插入完后（还剩堆中的k个元素），则将剩余堆中的元素按照堆排序的方式排序即可。对于每个数进入小顶堆后都要进行时间复杂度O(log k)的建堆过程，然后一共要排序n个元素，因此时间复杂度为O(n*log k)。

2.总结

import java.util.*;

public class ScaleSort {
    public int[] sortElement(int[] A, int n, int k) {
        // write code here

        if(A == null || n <= 1)
            return A;

        int[] heap = getHeapK(A, k);        //获取辅助小顶堆

        //每次将堆顶元素放置于数组前部，并将数组的下一个元素放入堆顶，进行堆调整，如此反复
        for(int i = k; i < n; i++){
            A[i - k] = heap[0];
            heap[0] = A[i];
            adjustMinHeap(heap, 0, k);
        }

        //对剩余的k个元素进行堆排序，每次将堆顶元素置于数组前部
        for(int i = n-k; i < n; i++){
            A[i] = heap[0];
            swap(heap, 0, k-1);
            adjustMinHeap(heap, 0, --k);
        }

        return A;
    }

    private int[] getHeapK(int[] A, int k){
        //对前k个元素建立小顶堆
        int[] heap = new int[k];
        for(int i = 0; i < k; i++){
            heap[i] = A[i];
        }
        for(int i = k/2 - 1; i >= 0; i--){
            adjustMinHeap(heap, i, k);
        }

        return heap;
    }

    private void adjustMinHeap(int[] heap, int current, int length){
        int temp = heap[current];

        for(int i = current*2+1; i < length; i = i*2+1){
            if(i+1 < length && heap[i+1] < heap[i])
                i++;

            if(temp > heap[i]){
                heap[current] = heap[i];
                current = i;
            }
            else{
                break;
            }
        }

        heap[current] = temp;
    }

    private void swap(int[] A, int index1, int index2){
        int temp = A[index1];
        A[index1] = A[index2];
        A[index2] = temp;
    }
}

二、低空间复杂度重复值判断

  请设计一个高效算法，判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。
  本题如果没有空间复杂度限制，应使用哈希表实现，统计每个元素的个数，此时时间复杂度和空间复杂度均为O(n)。
  本题的解法为先排序，后遍历，遍历到相同元素说明有重复值，否则没有。因此问题转为应该使用何种排序算法。
  在排序算法中，我们知道堆排序的在空间复杂度符合要求O(1)的情况下时间复杂度相对较低，因此本题应使用堆排序（但要注意要非递归实现，否则空间复杂度就不是O(1)了）。

import java.util.*;

public class Checker {
    public boolean checkDuplicate(int[] a, int n) {
        if(a == null || n <= 1){
            return false;
        }

        //堆排序
        for(int i = n/2-1; i >=0; i--){
            adjustMaxHeap(a, i, n);
        }       
        for(int i = n-1; i > 0; i--){
            swap(a, 0, i);
            adjustMaxHeap(a, 0, i);
        }

        //查重
        for(int i = 1; i < n; i++){
            if(a[i] == a[i-1])
                return true;
        }

        return false;

    }

    private void  adjustMaxHeap(int[] a, int current, int length){
        int temp = a[current];

        for(int i = current*2 + 1; i < length; i = i*2+1){
            if(i+1 < length && a[i+1] > a[i])
                i++;

            if(temp < a[i]){
                a[current] = a[i];
                current = i;
            }
            else{
                break;
            }
        }

        a[current] = temp;
    }

    private void swap(int[] a, int index1, int index2){
        int temp = a[index1];
        a[index1] = a[index2];
        a[index2] = temp;
    }
}

三、有序数组合并

  有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。
  这道题非常简单，对两个数组分别从后向前遍历，每次比较两个指针指向的元素，将较大者至于A数组末尾（下一次放在末尾的前一个位置，如此反复）。最后所有数组遍历完，返回A即可。

import java.util.*;

public class Merge {
    public int[] mergeAB(int[] A, int[] B, int n, int m) {
        // write code here
        int indexA = n-1;
        int indexB = m-1;
        int mergeIndex = m+n-1;

        while(indexA >= 0 && indexB >= 0){
            A[mergeIndex--] = A[indexA] > B[indexB] ? A[indexA--] : B[indexB--]; 
        }

        while(indexB >= 0){
            A[mergeIndex--] = B[indexB--];
        }

        return A;
    }
}