マージソート
時間計算量が O(nlogn) の並べ替えアルゴリズムの 1 つ (n は指定された配列の長さです)。
///tc : O(nlogn) //sc : O(n) for creating intermediate arrays a, b of size of part of subarray which is of size n class Solution { public int[] sortArray(int[] nums) { merge(0,nums.length-1,nums); return nums; } public void merge(int start, int end, int arr[]){ if(end>start){ int mid = (start+end)/2; merge(start,mid,arr); merge(mid+1,end,arr); sort(start, mid,end, arr); } } public void sort(int start, int mid ,int end, int arr[]){ int a[] = new int[mid-start+1]; int b[] = new int[end-mid]; for(int i = 0;i <hr> <p>反転回数</p> <p>配列がソートされるまでに必要な比較の回数 (配列 arr[] のインデックス i, j を指定すると、 <strong>arr[i]> arr[j]</strong> ( for j> i) は、この条件が満たされるたびに反転カウントが 1 ずつ増えます。</p> <p>注: <em>同じマージ ソート アプローチを使用して反転数を見つけることができます (マージ ソート コードは読みやすくするために少し変更されています)</em><br> </p> <pre class="brush:php;toolbar:false">class Solution { // arr[]: Input Array // N : Size of the Array arr[] // Function to count inversions in the array. static long inversionCount(long arr[], int n) { // Your Code Here //we can use merge sort long temp[]= new long[n]; return merge(0,n-1,arr,temp); } public static long merge(int start, int end, long arr[],long[] temp){ long count = 0; if(end>start){ int mid = (start+end)/2; count+=merge(start,mid,arr,temp); count+=merge(mid+1,end,arr,temp); count+=sort(start, mid,end, arr,temp); } return count; } public static long sort(int start, int mid ,int end, long arr[],long [] temp){ long count = 0; int i = start; int j = mid+1; int k = start; while(i arr[j] then all the values after ith index including will be // greater that jth index value hence count += mid-i+1 } k++; } while(i
以上が配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。