Java歸并排序算法代碼實現(xiàn)
歸并排序是常見的八大排序算法之一,歸并排序也是一種時間復雜度比較好的一種算法,為0(n*logn)級別。
歸并排序可以用遞歸和非遞歸兩種方式來實現(xiàn),當然,遞歸方法是比較簡單的,而非遞歸則是相對而言比較難的一種思路。
歸并排序的總體思路就是將一個大的無序數組,劃分為多個內部有序的數組,而組間可能是無序的,通過合并相鄰兩組得到一個新的有序數組來實現(xiàn),最終合并成總體的大數組,即完成排序。
因此,對于歸并排序,我們需要先向下分組,然后再將各個數組合并,得到一個新的數組,直到最后合并成一個數組,算法結束。
具體細節(jié),則是通過將大數組劃分,首先劃分為每一組單個元素,單個元素的數組可以認為是有序的。如何依次從左向右,每次取兩個相鄰數組,進行合并,即兩個有序數組的合并,合并完以后,再找下一組兩個相鄰的數組進行合并(并不包括上次合并好的數組),直到最后只有一個組或者沒有組了,就重新從頭開始合并,繼續(xù)上述步驟。
對于遞歸寫法,我們可以認為數組中的各個元素都是二叉樹的葉子結點,依據上述思路,兩兩合并成一個結點,最后合并成一個結點,即排序結束。
對于非遞歸寫法,我們可以設置一個變量來存儲要比較的數組長度,從一開始,到數組長度結束,即使分開后的數組元素個數并不等于這個變量,只要有和他配對的就可以合并。
代碼測試通過力扣中的題目進行測驗。
代碼實現(xiàn):
遞歸:
class Solution { public int[] sortArray(int[] nums) { mergeSort(nums,0,nums.length-1); return nums; } public void mergeSort(int[] nums,int left,int right){ if(right==left){ return; } int center=(left+right)/2; mergeSort(nums,left,center); mergeSort(nums,center+1,right); merge(nums,left,center,right); } public void merge(int[] nums,int left,int center,int right){ int i=left; int j=center+1; int[] temp=new int[right-left+1]; int count=0; while(i<=center && j<=right){ temp[count++]=nums[i]>nums[j]?nums[j++]:nums[i++]; } while(i<=center){ temp[count++]=nums[i++]; } while(j<=right){ temp[count++]=nums[j++]; } for(int k=0;k<temp.length;k++){ nums[left+k]=temp[k]; } } }
力扣提交結果:
非遞歸:
class Solution { public int[] sortArray(int[] nums) { for(int l,m,r,step=1;step<nums.length;step*=2){ l=0;//設置初始值 while(l<nums.length){//有左邊的組 m=l+step-1; if(m+1>=nums.length){//如果沒有右邊的組,就退出 break; } r=Math.min(l+(step*2)-1,nums.length-1);//獲取右邊界,取兩者的最小值 merge(nums,l,m,r);//將兩個組合并 l=r+1;//找到下一個左邊的組 } } return nums; } public void merge(int[] nums,int left,int center,int right){ int i=left; int j=center+1; int[] temp=new int[right-left+1]; int count=0; while(i<=center && j<=right){ temp[count++]=nums[i]>nums[j]?nums[j++]:nums[i++]; } while(i<=center){ temp[count++]=nums[i++]; } while(j<=right){ temp[count++]=nums[j++]; } for(int k=0;k<temp.length;k++){ nums[left+k]=temp[k]; } } }
力扣提交結果:
總結
到此這篇關于Java歸并排序算法的文章就介紹到這了,更多相關Java歸并排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
詳解基于MybatisPlus兩步實現(xiàn)多租戶方案
這篇文章主要介紹了詳解基于MybatisPlus兩步實現(xiàn)多租戶方案,本文分兩步,通過實例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04java Hibernate save()與persist()區(qū)別
本文章來給各位同學介紹一下Hibernate save()與persist()區(qū)別,希望此文章能對各位同學對于Hibernate save()與persist()有所理解2016-01-01Java中的FileInputStream是否需要close問題
這篇文章主要介紹了Java中的FileInputStream是否需要close問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-12-12ArrayList和JSONArray邊遍歷邊刪除到底該如何做
這篇文章主要介紹了ArrayList和JSONArray邊遍歷邊刪除到底該如何做,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-12-12