算法之逆序對

逆序對問題

​ 假設A[1..n]是一個有n個不同數的數組。若i<j且A[i]>A[j],則對偶(i, j)稱為A的一個逆序對(inversion)。

1. 列出數組{2, 3, 8, 6, 1}的5個逆序對
2. 由集合{1, 2, ..., n}中的元素構成的什麼數組具有最多的逆序對？它有多少逆序對?
3. 插入排序的運作時間與輸入數組中的逆序對的數量有什麼關系?
4. 給出一個求在n個元素的任何排列中逆序對數量的算法，最壞時間複雜度為: \(\Theta\)(nlgn)

1. 根據定義易得，逆序對為：(2, 1)、(3, 1)、(8, 6)、(8, 1)、(6, 1)
2. 當數組元素恰好為n個元素從大到小排列時，擁有最多的逆序對。此時逆序對為: (n - 1) + (n -2) + (n - 3) + ... + 1 = n(n - 1) / 2
3. 根據插入排序的實作過程，不難得出每次從未排序數組選擇一個值arr[j]插入已排序數組的時候，所需要的移動次數，即為以arr[j]為右側值的逆序對的個數。這個特性也可以設計出一個時間複雜度為: \(\Theta\)(\(n^2\))的算法。當然這種指數級别複雜度的算法我們直接PASS
4. 不難想到\(\Theta\)(nlgn)算法複雜度的歸并排序。其實歸并排序在分治的時候不會改變逆序對的個數。隻有在合并的時候，才會因為逆序對的出現導緻右側提前被合入原數組。其實修改點主要在兩個方面:

• 聲明一個全局變量用來存儲總的次數
• 在右側提前被合入原數組的時候對總次數進行累加（隻需要改歸并排序的merge方法， 歸并排序請參照 http://www.cnblogs.com/Kidezyq/p/8379267.html ）

具體源代碼如下：

private static int count;

private static void merge(int[] arr, int startIndex, int midIndex, int endIndex) {
    /**
     * 合并政策: 
     * 1. 建立兩個數組，分别存取左半部分排好序的數組和右半部分排好序的數組
     * 2. 分别從左右兩個數組最開始下标開始周遊，選取較小的依次放入原數組對應位置
     * 3. 最終如果左右數組中有一個已經周遊完成，另一個數組所剩的元素直接放入元素組後面部分即可
     */
    // STEP1
    int[] leftArr = new int[midIndex - startIndex];
    int[] rightArr = new int[endIndex - midIndex];
    System.arraycopy(arr, startIndex, leftArr, 0, leftArr.length);
    System.arraycopy(arr, midIndex, rightArr, 0, rightArr.length);
    
    // STEP2
    int k = startIndex; // 存儲原數組中的下标
    int i = 0;          // 存儲左邊數組的下标
    int j = 0;          // 存儲右邊數組的下标
    while (i < leftArr.length && j < rightArr.length) {
        // 将較小的元素複制到元素組對應下标k，并且移動較小元素所在數組下标
        if (leftArr[i] < rightArr[j]) {
            arr[k++] = leftArr[i++];    
        } else {
            // 此時說明 arr[i]到arr[leftArr.length - 1]的值都比arr[j]大，即此時以arr[j]結尾的逆序對個數為: 
            count += leftArr.length - i;
            arr[k++] = rightArr[j++];
        }
    }
    
    // STEP3
    if (i < leftArr.length) {
        System.arraycopy(leftArr, i, arr, k, leftArr.length - i);
    } else if (j <= rightArr.length) {
        System.arraycopy(rightArr, j, arr, k, rightArr.length - j);
    }
}
           

黎明前最黑暗，成功前最絕望！