MergeSort
Salah satu algoritma pengisihan dengan kerumitan masa O(nlogn) dengan n ialah panjang tatasusunan yang diberikan.
///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
Kiraan penyongsangan
Berapa banyak perbandingan yang diperlukan sebelum tatasusunan diisih (diberikan indeks i, j tatasusunan arr[] , arr[i]> arr[j] ( untuk j> i) akan menambah kiraan penyongsangan sebanyak 1 setiap kali syarat ini dipenuhi.
nota: kita boleh menggunakan pendekatan isihan gabungan yang sama untuk mencari kiraan penyongsangan (kod isihan cantum telah diubah sedikit untuk menjadikannya lebih mudah dibaca)
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(iSalin selepas log masuk
以上是Tatasusunan的详细内容。更多信息请关注PHP中文网其他相关文章!