---

套路

• 排序问题要时刻想到基本的八种排序算法，并且能够熟练掌握和灵活运用。
• 需要寻找排序后特定的数（如中位数）或者几个数（如最小 / 大的K个数）往往用堆排序最优，所以对排序也需要很好的掌握一下

---

注意点

• 暂无

---

目录

• 调整数组顺序使奇数位于偶数前面（直插的变形，稳定）
• 数组中的逆序对（归并的变形）
• 数据流中的中位数（堆排序的变形）
• 最小的K个数（堆排序的变形）

---

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

• 解题思路：感觉跟稳定性没什么关系，稳定排序指是相等的数保证相对位置不变，跟这个奇数与奇数、偶数与偶数间的相对位置没什么关系。不使用任何额外数据结构，直接插入变形。时间复杂度 O(n^2), 空间复杂度O(1)

public void reOrderArray(int [] array) {
    if (array == null || array.length == 0) {
        return;
    }
    for (int i = 1; i < array.length; i++) {
        if (array[i] % 2 == 1) {
            int t = array[i];
            for (int j = i - 1; j >= 0; j--) {
                if (array[j] % 2 == 0) {
                    array[j + 1] = array[j];
                    if (j == 0) {
                        array[j] = t;
                    }
                } else {
                    array[j + 1] = t;
                    break;
                }
            }
        }
    }
}

---

数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：对于%50的数据,size<=10^4, 对于%75的数据,size<=10^5, 对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7

private int total = 0;

public int InversePairs(int [] array) {
    if (array == null) {
        return 0;
    }
    sort(array, 0, array.length - 1);
    return total;
}

private void sort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

private void merge(int[] arr, int low, int mid, int high) {
    int left = low, right = mid + 1, len = high - low + 1;
    int[] temp = new int[len];
    int k = 0;
    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp[k++] = arr[left++];
        } else {
            // 说明数组左边从left到mid的值都大于right
            // 可组成 mid - left + 1个逆序对
            total += mid - left + 1;
            total %= 1000000007;
            temp[k++] = arr[right++];
        }
    }
    while (left <= mid) {
        temp[k++] = arr[left++];
    }
    while (right <= high) {
        temp[k++] = arr[right++];
    }
    for (int i = 0; i < len; i++) {
        // 注意这里从 low 开始加
        arr[low + i] = temp[i];
    }
}

---

数据流中的中位数

• 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
• 如果直接插入动态数组，然后排序的话，要进行n次nlogn的排序，也就是n^2logn级别。而优先级队列，可以做到nlogn级别的时间复杂度。

private int count = 0;
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<Integer>(15, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

public void Insert(Integer num) {
    if (count % 2 == 0) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
    } else {
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
    }
    count++;
}

public Double GetMedian() {
    if (count % 2 == 0) {
        return new Double((minHeap.peek() + maxHeap.peek())) / 2;
    } else {
        return new Double(minHeap.peek());
    }
}

---

最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

• 基于堆排序算法，构建最大堆。时间复杂度为 O(nlogk)
• 如果用快速排序，时间复杂度为 O(nlogn)；
• 如果用冒泡排序，时间复杂度为 O(n * k)

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> list = new ArrayList<>();
    //检查输入的特殊情况
    if(input == null || input.length <= 0 || input.length < k) {
        return list;
    }
    //构建最大堆
    for(int len = k / 2 - 1; len >= 0; len--) {
        adjustMaxHeapSort(input, len, k-1);
    }
    //从第k个元素开始分别与最大堆的最大值做比较，如果比最大值小，则替换并调整堆。
    //最终堆里的就是最小的K个数。
    int tmp;
    for(int i = k; i < input.length; i++) {
        if(input[i] < input[0]){
            tmp = input[0];
            input[0] = input[i];
            input[i] = tmp;
            adjustMaxHeapSort(input, 0, k-1);
        }
    }
    for(int j = 0; j < k; j++) {
        list.add(input[j]);
    }
    return list;
}
     
public void adjustMaxHeapSort(int[] input, int pos, int length) {
    int temp, child;
    for(temp = input[pos]; 2 * pos + 1 <= length; pos = child) {
        child = 2 * pos + 1;
        if(child < length && input[child] < input[child + 1]) {
            child++;
        }
        if(input[child] > temp) {
            input[pos] = input[child];
        } else {
            break;
        }
    }
    input[pos] = temp;
}

---