欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

老生常談比較排序之歸并排序(遞歸)

 更新時間:2017年06月24日 08:11:14   投稿:jingxian  
下面小編就為大家?guī)硪黄仙U劚容^排序之歸并排序(遞歸)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧

歸并排序里運用到算法里很重要的一個思想——分治法:將原問題分解為幾個規(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)容了,希望能給大家一個參考,也希望大家多多支持腳本之家。

相關文章

  • Java線程池獲取池中所有線程列表的方法總結

    Java線程池獲取池中所有線程列表的方法總結

    在Java中,獲取線程池中所有線程列表并不是一個直接支持的功能,因為線程池的設計通常是為了隱藏和管理底層的線程細節(jié),從而提供更高層次的抽象和并發(fā)控制能力,本文給大家介紹了Java線程池獲取池中所有線程列表的方法,需要的朋友可以參考下
    2024-10-10
  • Spring?Cloud?Eureka?搭建?&?集群方式

    Spring?Cloud?Eureka?搭建?&?集群方式

    這篇文章主要介紹了Spring?Cloud?Eureka?搭建?&?集群方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-03-03
  • springboot實現(xiàn)注冊加密與登錄解密功能(demo)

    springboot實現(xiàn)注冊加密與登錄解密功能(demo)

    這篇文章主要介紹了springboot實現(xiàn)注冊的加密與登錄的解密功能,本文通過demo實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-02-02
  • Spring:bean注入--Set方法注入

    Spring:bean注入--Set方法注入

    這篇文章主要給大家總結介紹了關于Spring注入Bean的一些方式,文中通過示例代碼介紹的非常詳細,對大家學習或者使用Spring具有一定的參考學習價值,需要的朋友們下面來一起學習學習吧
    2021-07-07
  • Java簡單實現(xiàn)session保存到redis的方法示例

    Java簡單實現(xiàn)session保存到redis的方法示例

    這篇文章主要介紹了Java簡單實現(xiàn)session保存到redis的方法,結合實例形式分析了Java將session存入redis緩存服務器的相關設置、實現(xiàn)技巧與操作注意事項,需要的朋友可以參考下
    2018-05-05
  • java單例模式4種使用方式分享

    java單例模式4種使用方式分享

    到底如何寫一個在生產(chǎn)環(huán)境中使用的單實例模式?下面是4種方式,大家參考使用吧
    2014-02-02
  • SpringBoot+WebMagic+MyBaties實現(xiàn)爬蟲和數(shù)據(jù)入庫的示例

    SpringBoot+WebMagic+MyBaties實現(xiàn)爬蟲和數(shù)據(jù)入庫的示例

    WebMagic是一個開源爬蟲框架,本項目通過在SpringBoot項目中使用WebMagic去抓取數(shù)據(jù),最后使用MyBatis將數(shù)據(jù)入庫。具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-10-10
  • Springboot中如何使用過濾器校驗PSOT類型請求參數(shù)內(nèi)容

    Springboot中如何使用過濾器校驗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問題及處理

    這篇文章主要介紹了使用Mybatis-Plus時的SqlSessionFactory問題及處理方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-12-12
  • Ribbon單獨使用,配置自動重試,實現(xiàn)負載均衡和高可用方式

    Ribbon單獨使用,配置自動重試,實現(xiàn)負載均衡和高可用方式

    這篇文章主要介紹了Ribbon單獨使用,配置自動重試,實現(xiàn)負載均衡和高可用方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-12-12

最新評論