在你漸漸迷失在你的人生道路上的時(shí)候，千萬不要因?yàn)樽叩奶?，而忘記了我們?yōu)槭裁闯霭l(fā)，做碼農(nóng)，也要清楚自己如何才能用有效的土地種植出 出色的產(chǎn)品，于是細(xì)節(jié)就需要把握一下。
排序是一個(gè)非常經(jīng)典的問題，它以一定的順序?qū)σ粋€(gè)數(shù)組（或一個(gè)列表）中的項(xiàng)進(jìn)行重新排序（可以進(jìn)行比較，例如整數(shù)，浮點(diǎn)數(shù)，字符串等）（增加，非遞減，遞減， 增加，詞典等）。
有許多不同的排序算法，每個(gè)都有其自身的優(yōu)點(diǎn)和局限性
引用于 https:///zh
歸并排序，是創(chuàng)建在歸并操作上的一種有效的排序算法。算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 算法復(fù)雜度：O（nlogn） 核心思想：分治
如我這里有一組數(shù)據(jù)，歸并排序過程描述如下： 
我們把上面的流程圖合到一起就是如下： 
分割的過程中其實(shí)可理解為就是以二分法將數(shù)組分割成最小單元，如下圖所示分析了一下最后一步的合并過程 
//歸并排序 @Test public void mergeSortFunction2(){ //待排序數(shù)組 int arr[]={6,5,3,1,8,7,2,4}; int len = arr.length; //臨時(shí)數(shù)組 int[] result = new int[len]; //排序 sort(arr,result);
System.out.println(Arrays.toString(result)); }
public static void sort(int []arr,int []temp ){ sort(arr,0,arr.length-1,temp); }
private static void sort(int[] arr,int left,int right,int []temp){ if(left<right){ int mid = (left+right)/2; //左邊歸并排序，使得左子序列有序 sort(arr,left,mid,temp); //右邊歸并排序，使得右子序列有序 sort(arr,mid+1,right,temp); //將兩個(gè)有序子數(shù)組合并操作 merge(arr,left,mid,right,temp); } }
private static void merge(int[] arr,int left,int mid,int right,int[] temp){ int i = left;//左序列指針 int j = mid+1;//右序列指針 int t = 0;//臨時(shí)數(shù)組指針 while (i<=mid && j<=right){ if(arr[i]<=arr[j]){ temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } while(i<=mid){//將左邊剩余元素填充進(jìn)temp中 temp[t++] = arr[i++]; } while(j<=right){//將右序列剩余元素填充進(jìn)temp中 temp[t++] = arr[j++]; } t = 0; //將temp中的元素全部拷貝到原數(shù)組中 while(left <= right){ arr[left++] = temp[t++]; } }
|
