Сортировка слиянием — эффективный и стабильный алгоритм сортировки, основанный на операциях слияния. Этот алгоритм представляет собой очень типичное применение метода «разделяй и властвуй» .
Сортировка слиянием объединяет две упорядоченные подпоследовательности для получения полностью упорядоченной последовательности, то есть сначала сортируется каждая подпоследовательность, а затем сортируются сегменты подпоследовательности. Если два упорядоченных списка объединяются в один упорядоченный список, мы называем это двусторонним слиянием .
Скорость сортировки слиянием уступает только быстрой сортировке, а временная сложность равна O(nlogn). В процессе разделения используется идея дихотомии, которая является рекурсивным процессом. Чтобы уменьшить проблему постоянного открытия пространства во время рекурсивного процесса, мы можем сначала открыть временное пространство перед слиянием и сортировкой и использовать это пространство. равномерно во время рекурсивного процесса. Просто слейте.
Например:
importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){int[]arr=newint[]{86,23,7,45,19,10};intleft=0;intright=arr.length-1; int[]tem=Arrays.copyOf(arr,arr.length);print(arr);mergeSort(arr,left,right,tem);print(arr);}publicstaticvoidmergeSort(int[]arr,intleft,intright,int []tem){if(right-left<1){return;}intmid=left+(right-left)/2;mergeSort(arr,left,mid,tem);mergeSort(arr,mid+1,right,tem);mergeSort(arr,mid+1,right,tem) );merge(arr,left,mid,right,tem);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]tem){intindex=0;intl=left,r=mid+1; while (l<=mid&&r<=right){if(arr[l]<arr[r]){tem[index++]=arr[l++];}else{tem[index++]=arr[r++];}} while( l<=mid){tem[index++]=arr[l++];} while(r<=right){tem[index++]=arr[r++];}for(inti=0;i<(right-left+1 );i++){arr[left+i]=tem[i];}}privatestaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+t);}System.out. println();}} Результаты бега следующие:
8623745191071019234586