求逆序對的個數

特點：利用歸并排序中合并的步驟，計算逆序對
時間復雜度O（nlgn）

int merge_inversion(int *arr,int start,int end,int middle); int count_inversion(int *arr,int start,int end) {if(start<end){int middle = (start + end)/2;int left = count_inversion(arr,start,middle);int right = count_inversion(arr,middle+1,end);return left + right + merge_inversion(arr,start,end,middle);}elsereturn 0; } int merge_inversion(int *arr,int start,int end,int middle) {int *left_arr = new int [middle - start + 2];int *right_arr = new int [end - middle + 3];for (int i = start; i < middle+1; ++i) {left_arr[i-start] = arr[i];}for (int i = middle+1; i < end+1; ++i) {right_arr[i-middle-1] = arr[i];}left_arr[middle -start + 1] = INT_MAX;right_arr[end - middle] = INT_MAX;int left = 0,right = 0,inversions = 0;int left_count = middle - start + 1;for (int i = start; i < end+1; ++i) {if(left_arr[left]<=right_arr[right]){arr[i] = left_arr[left];left++;}else{arr[i] = right_arr[right];right++;inversions += left_count - left;}}delete [] left_arr;delete [] right_arr;return inversions; }

總結

以上是生活随笔為你收集整理的算法-计算逆序对个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。