老生常談比較排序之歸并排序(遞歸)
歸并排序里運用到算法里很重要的一個思想——分治法:將原問題分解為幾個規(guī)模較小但類似于原問題的子問題——《算法導論》。
在每一層遞歸中都有3個步驟:
1.分解問題
2.解決問題
3.合并問題的解
舉例待排序數(shù)組:{6, 5, 3, 1, 7, 2, 4},將它原始序列做分解。
可以經(jīng)過不斷的遞歸分解可以看到已經(jīng)把原始數(shù)組序列不斷分解為最小單位,接下來不妨將它們看做是二叉樹的葉子節(jié)點。
將他們進行兩兩歸并排序形成二叉樹(也稱為2路歸并算法),可見二叉樹的根節(jié)點即為最終序列。在這個過程中我們完成了剩余的兩個步驟:解決問題和合并問題。
理論很簡單,實踐很“復雜”。對于歸并排序的理論從上面的二叉樹就看的很明白,將原始待排序數(shù)組不斷分解最后看成是二叉樹的葉子節(jié)點,再把它們兩兩排形成新的節(jié)點,逐漸歸并為一個節(jié)點,此時的節(jié)點即為排好序的數(shù)組序列。
Java
package com.algorithm.sort.merge; import java.util.Arrays; /** * 歸并排序(遞歸) * Created by yulinfeng on 2017/6/23. */ public class Merge { public static void main(String[] args) { int[] nums = {6, 5, 3, 1, 7, 2, 4}; nums = mergeSort(nums); System.out.println(Arrays.toString(nums)); } /** * 歸并排序 * @param nums 待排序數(shù)組序列 * @return 排好序的數(shù)組序列 */ private static int[] mergeSort(int[] nums) { segment(nums, 0, nums.length - 1); return nums; } /** * 遞歸切分待排 * @param nums 待切分數(shù)組 * @param left 待切分最后第一個元素的索引 * @param right 待切分數(shù)組最后一個元素的索引 */ private static void segment(int[] nums, int left, int right) { if (left >= right) return; // 找出中間索引 int center = (left + right) / 2; // 對左邊數(shù)組進行遞歸 segment(nums, left, center); // 對右邊數(shù)組進行遞歸 segment(nums, center + 1, right); // 合并 merge(nums, left, center, right); } /** * 兩兩歸并排好序的數(shù)組(2路歸并) * @param nums 帶排序數(shù)組對象 * @param left 左邊數(shù)組的第一個索引 * @param center 左數(shù)組的最后一個索引,center + 1右數(shù)組的第一個索引 * @param right 右數(shù)組的最后一個索引 */ private static void merge(int[] nums, int left, int center, int right) { int[] tmpArray = new int[nums.length]; int rightIndex = center + 1; // 右數(shù)組第一個元素索引 int tmpIndex = left; //臨時數(shù)組索引 int begin = left; // 緩存左數(shù)組第一個元素的索引,用于將排好序的數(shù)組拷貝回原數(shù)組 while (left <= center && rightIndex <= right) { if (nums[left] <= nums[rightIndex]) { tmpArray[tmpIndex++] = nums[left++]; } else { tmpArray[tmpIndex++] = nums[rightIndex++]; } } while (left <= center) { tmpArray[tmpIndex++] = nums[left++]; } while (rightIndex <= right) { tmpArray[tmpIndex++] = nums[rightIndex++]; } while (begin <= right) { nums[begin] = tmpArray[begin++]; } } }
Python3
#二路歸并排序(遞歸) def merge_sort(nums): segment(nums, 0, len(nums) - 1) return nums #切分待排序數(shù)組 def segment(nums, left, right): if left >= right: return center = int((left + right) / 2) segment(nums, left, center) segment(nums, center + 1, right) merge(nums, left, center, right) #兩兩歸并排好序的數(shù)組(二路歸并) def merge(nums, left, center, right): tmpArray = [0] * len(nums) rightIndex = center + 1 #右數(shù)組的第一個元素索引 tmpIndex = left begin = left while left <= center and rightIndex <= right: if nums[left] <= nums[rightIndex]: tmpArray[tmpIndex] = nums[left] tmpIndex += 1 left += 1 else: tmpArray[tmpIndex] = nums[rightIndex] tmpIndex += 1 rightIndex += 1 while left <= center: tmpArray[tmpIndex] = nums[left] tmpIndex += 1 left += 1 while rightIndex <= right: tmpArray[tmpIndex] = nums[rightIndex] tmpIndex += 1 rightIndex += 1 while begin <= right: nums[begin] = tmpArray[begin] begin += 1 nums = [6, 5, 3, 1, 7, 2, 4] nums = merge_sort(nums) print(nums)
以上這篇老生常談比較排序之歸并排序(遞歸)就是小編分享給大家的全部內(nèi)容了,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關文章
springboot實現(xiàn)注冊加密與登錄解密功能(demo)
這篇文章主要介紹了springboot實現(xiàn)注冊的加密與登錄的解密功能,本文通過demo實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02Java簡單實現(xiàn)session保存到redis的方法示例
這篇文章主要介紹了Java簡單實現(xiàn)session保存到redis的方法,結合實例形式分析了Java將session存入redis緩存服務器的相關設置、實現(xiàn)技巧與操作注意事項,需要的朋友可以參考下2018-05-05SpringBoot+WebMagic+MyBaties實現(xiàn)爬蟲和數(shù)據(jù)入庫的示例
WebMagic是一個開源爬蟲框架,本項目通過在SpringBoot項目中使用WebMagic去抓取數(shù)據(jù),最后使用MyBatis將數(shù)據(jù)入庫。具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-10-10Springboot中如何使用過濾器校驗PSOT類型請求參數(shù)內(nèi)容
在Springboot中創(chuàng)建過濾器,用來過濾所有POST類型請求并獲取body中的參數(shù)進行校驗內(nèi)容是否合法,該方法僅適用于POST類型請求,本文給大家介紹Springboot中如何使用過濾器校驗PSOT類型請求參數(shù)內(nèi)容,感興趣的朋友一起看看吧2023-08-08使用Mybatis-Plus時的SqlSessionFactory問題及處理
這篇文章主要介紹了使用Mybatis-Plus時的SqlSessionFactory問題及處理方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-12-12Ribbon單獨使用,配置自動重試,實現(xiàn)負載均衡和高可用方式
這篇文章主要介紹了Ribbon單獨使用,配置自動重試,實現(xiàn)負載均衡和高可用方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-12-12