java版十大排序經典算法:完整代碼(3)
歸並排序
簡單解釋:該算法是采用分治法,把數組不斷分割,直至成為單個元素,然後比較再合並(合並的過程就是兩部分分別從頭開始比較,取出最小或最大元素的放到新的區域內,繼續取兩部分中最大或最小的元素,直到這兩部分合並完,最後所有的都合並完,最後形成完整的有序序列)
完整代碼:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: MergeSort * @Description: 歸並排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:35 */ public class MergeSort { //歸並排序 public static void mergeSort(int []arr ,boolean ascending){ int[] temp = new int[arr.length]; //在排序前,先建好一個長度等於原數組長度的臨時數組,避免遞歸中頻繁開辟空間 mergeSort(arr,0,arr.length-1,temp,ascending); } public static void mergeSort(int []arr){ mergeSort(arr,true); } /** * * @param arr 傳入的數組 * @param left 當前子數組的起始下標 * @param right 當前子數組的結束下標 * @param temp 拷貝暫存數組 */ public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){ if(left<right){ //這裡是遞歸結束的條件,我們是對半分,那當left==right的時候肯定大傢都是隻有一個元素瞭。 //對半分,比如總長度是10,left=0,right=9,mid=4確實是中間分瞭,0~4,5~9 //當長度9,left=0,right=8,mid=4,0~4,5~8 int mid = left + (right-left)/2; // 防止越界的寫法 //int mid = (left+right)/2; mergeSort(arr,left,mid,temp,ascending); //左邊歸並排序,使得左子序列有序 mergeSort(arr,mid+1,right,temp,ascending); //右邊歸並排序,使得右子序列有序 merge(arr,left,mid,right,temp,ascending); //將兩個有序子數組合並操作 } } private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){ int i = left; //左序列起始下標 int j = mid+1; //右序列起始下標 int t = 0; //臨時數組指針 while(i<=mid&&j<=right){ if(ascending?arr[i]<arr[j]:arr[i]>arr[j]){ //比較兩個序列第一個元素誰小,誰小先拷貝誰到temp,然後對應子序列下標加1 temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } while(i<=mid){ //將左邊剩餘元素填充進temp中——左序列有一些數總是比右邊的大的數 temp[t++] = arr[i++]; } while(j<=right){ //將右序列剩餘元素填充進temp中——右序列有一些數總是比左邊的大的數 temp[t++] = arr[j++]; } t = 0; //將temp中的元素全部拷貝到原數組中 while(left<=right){ arr[left++] = temp[t++]; } } }
插入排序
簡單解釋:最簡單的理解就是打地主時我們拿到牌後的整理過程,從第二個牌(假設我們拿起來這個牌開始比較)開始,(說下升序)從後往前比較如果比前面的那個牌小,就把牌往後移動,直到找到一個合適的位置(這個位置的前面的那個牌不比這個要放下的牌大)就把這個牌放到這個位置,慢慢的前面的部分變得有序,直至全部有序即可。
完整代碼:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: StraghtInsertSort * @Description: 插入排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:36 */ public class StraghtInsertSort { //插入排序 public static void straghtInsertSort(int[] arr) { straghtInsertSort(arr, true);//默認進行升序 } public static void straghtInsertSort(int[] arr, boolean ascending) { for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j=0; //這就是那個合適的位置 for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) { arr[j + 1] = arr[j]; } //把牌放下,為啥是j+1, //是因為上面的循環遍歷到不符合情況的時候 j是合適的位置的前面的那個數的位置 //有點拗口,但是就是這個意思,看圖方便理解下 arr[j + 1] = temp; } } }
希爾排序
簡單解釋:希爾排序是插入排序的改進版,我們理解一個叫做下標差的的東西,也就是下面那個圖中的增量d,初始下標差為arr.length/2,然後繼續/2,對在同一下標差(相當於把這幾個數單獨拿出來瞭)的若幹個數進行插入排序即可。
完整代碼:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: ShellSort * @Description: 希爾排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:39 */ public class ShellSort { public static void shellSort(int[] arr) { shellSort(arr,true); } public static void shellSort(int[] arr,boolean ascending) { for(int d = arr.length/2;d>0;d/=2){ for(int i=d;i< arr.length;i++){ int temp = arr[i]; int j=0; for(j=i-d;j>=0&&(ascending?temp<arr[j]:temp>arr[j]);j-=d){ arr[j+d]=arr[j]; } arr[j+d] = temp; } } } }
總結
本篇文章就到這裡瞭,希望能給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!
推薦閱讀:
- java版十大排序經典算法:完整代碼(4)
- java版十大排序經典算法:完整代碼(2)
- java版十大排序經典算法:完整代碼
- Java輕松入門冒泡 選擇 插入 希爾 歸並排序算法
- Java算法練習題,每天進步一點點(1)