溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“java歸并排序如何實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“java歸并排序如何實現”吧!
歸并排序相對于冒泡、插入、選擇這三種排序時間復雜度是O(n2)來說適合大規模的數據排序，它的時間復雜度都是O(nlogn)。
它用到了分治的思想，把大問題分解成小問題，小問題再分，分而治之。
先來說說歸并排序的思想：把要排序的數組從中間一分為二，分為左邊和右邊，然后左右分別排序，排好了之后再合并到一起(如果左右兩邊還能分繼續一分為二，遞歸思想)這樣就排好了！是不是感覺挺簡單的？
來看一下圖
上代碼！我們利用遞歸來實現歸并排序
代碼關鍵點就是,recursion這個遞歸，就是把數組一分為二，然后排序！
merge方法的思路就是申請一個左邊數組和右邊數組一樣長度的空數組用來存放結果，然后搞了兩個游標i和j分別指向左數組和右數組，對比left[i]和right[j],哪個小就放入result中，然后對應的游標+1。循環結束之后，再把剩余的沒塞入result的數據塞入result。這樣就大功告成了！
歸并排序的時間復雜度是O(nlogn)，并且從代碼可以看left[i]小于等于right[j]的時候是塞入result所以它是穩定的排序！
例如[3,2,2,3]。當分為left和right之后并且內部排序之后是left[2,3]，right[2,3]。這時候還沒破壞兩個2直接的順序，之后合并還是left的2先塞入result,所以是穩定的！
但是歸并有一個不好點它不是原地排序，可以看到它需要額外的數組空間存放排序之后的結果。它的空間復雜度是O(n)。
到此，相信大家對“java歸并排序如何實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
