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

歸并排序的原理及java代碼實(shí)現(xiàn)

 更新時(shí)間:2016年02月02日 10:54:33   投稿:hebedich  
歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表,即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。遞歸形式的算法在形式上較簡(jiǎn)潔,但實(shí)用性很差。一般情況下,很少利用二路歸并排序法進(jìn)行內(nèi)部排序。

概述

歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表,即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序采用的是遞歸來(lái)實(shí)現(xiàn),屬于“分而治之”,將目標(biāo)數(shù)組從中間一分為二,之后分別對(duì)這兩個(gè)數(shù)組進(jìn)行排序,排序完畢之后再將排好序的兩個(gè)數(shù)組“歸并”到一起,歸并排序最重要的也就是這個(gè)“歸并”的過(guò)程,歸并的過(guò)程中需要額外的跟需要?dú)w并的兩個(gè)數(shù)組長(zhǎng)度一致的空間。

效果圖:

步驟

申請(qǐng)空間,使其大小為兩個(gè)已經(jīng)排序序列之和,該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針,最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑?,選擇相對(duì)小的元素放入到合并空間,并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針達(dá)到序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
實(shí)例

原始數(shù)據(jù):

3 5 2 6 2
歸并的前提是將數(shù)組分開(kāi),一分為二,再一分為二,分到不能再分,進(jìn)行歸并。

第一輪分隔,索引2 ((0+4)/2=2) 為中間

[3 5 2] [6 2]

第二輪分隔,對(duì)[3 5 2]進(jìn)行分隔

[3 5] [2] [6 2]

第三輪分隔,對(duì)[3 5]進(jìn)行分隔

[3] [5] [2] [6 2]

合并[3] [5]

[3 5] [2] [6 2]

合并[3 5] [2]

[2 3 5] [6 2]

第四輪分隔,對(duì)[6 2]進(jìn)行分隔

[2 3 5] [6] [2]

合并[6] [2]

[2 3 5] [2 6]

合并[2 3 5] [2 6]

[2 2 3 5 6]

代碼實(shí)現(xiàn)(Java)

package com.coder4j.main.arithmetic.sorting;

public class Merge {
  
  private static int mark = 0;

  /**
   * 歸并排序
   * 
   * @param array
   * @param low
   * @param high
   * @return
   */
  private static int[] sort(int[] array, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
      mark++;
      System.out.println("正在進(jìn)行第" + mark + "次分隔,得到");
      System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
      // 左邊數(shù)組
      sort(array, low, mid);
      // 右邊數(shù)組
      sort(array, mid + 1, high);
      // 左右歸并
      merge(array, low, mid, high);
    }
    return array;
  }

  /**
   * 對(duì)數(shù)組進(jìn)行歸并
   * 
   * @param array
   * @param low
   * @param mid
   * @param high
   */
  private static void merge(int[] array, int low, int mid, int high) {
    System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
    int[] temp = new int[high - low + 1];
    int i = low;// 左指針
    int j = mid + 1;// 右指針
    int k = 0;
    // 把較小的數(shù)先移到新數(shù)組中
    while (i <= mid && j <= high) {
      if (array[i] < array[j]) {
        temp[k++] = array[i++];
      } else {
        temp[k++] = array[j++];
      }
    }
    // 兩個(gè)數(shù)組之一可能存在剩余的元素
    // 把左邊剩余的數(shù)移入數(shù)組
    while (i <= mid) {
      temp[k++] = array[i++];
    }
    // 把右邊邊剩余的數(shù)移入數(shù)組
    while (j <= high) {
      temp[k++] = array[j++];
    }
    // 把新數(shù)組中的數(shù)覆蓋array數(shù)組
    for (int m = 0; m < temp.length; m++) {
      array[m + low] = temp[m];
    }
  }

  /**
   * 歸并排序
   * 
   * @param array
   * @return
   */
  public static int[] sort(int[] array) {
    return sort(array, 0, array.length - 1);
  }

  public static void main(String[] args) {
    int[] array = { 3, 5, 2, 6, 2 };
    int[] sorted = sort(array);
    System.out.println("最終結(jié)果");
    for (int i : sorted) {
      System.out.print(i + " ");
    }
  }
}

測(cè)試輸出結(jié)果:

正在進(jìn)行第1次分隔,得到
[0-2] [3-4]
正在進(jìn)行第2次分隔,得到
[0-1] [2-2]
正在進(jìn)行第3次分隔,得到
[0-0] [1-1]
合并:[0-0] 和 [1-1]
合并:[0-1] 和 [2-2]
正在進(jìn)行第4次分隔,得到
[3-3] [4-4]
合并:[3-3] 和 [4-4]
合并:[0-2] 和 [3-4]
最終結(jié)果
2 2 3 5 6 

經(jīng)測(cè)試,與實(shí)例中結(jié)果一致。

相關(guān)文章

  • 探究Java中Integer緩沖區(qū)底層原理

    探究Java中Integer緩沖區(qū)底層原理

    本文將會(huì)給大家講一講Integer這個(gè)包裝類(lèi)的底層原理。在現(xiàn)在的就業(yè)環(huán)境下,我們需要知其然,還要知其所以然,才能更好地滿(mǎn)足就業(yè)需求,感興趣的小伙伴可以參考閱讀
    2023-05-05
  • Java 8 引入lambda表達(dá)式的原因解析

    Java 8 引入lambda表達(dá)式的原因解析

    這篇文章主要介紹了Java 8 引入lambda表達(dá)式的原因解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-08-08
  • mybatis-plus?分頁(yè)類(lèi)型轉(zhuǎn)換工具類(lèi)

    mybatis-plus?分頁(yè)類(lèi)型轉(zhuǎn)換工具類(lèi)

    用mybatis-plus?的分頁(yè)對(duì)象的時(shí)候,因?yàn)橛胢ybatis-puls?查詢(xún)出來(lái)的分頁(yè)對(duì)象的records里的泛型是實(shí)體,有時(shí)候需要將實(shí)體轉(zhuǎn)換為前端展示的對(duì)象,所有寫(xiě)了一個(gè)分頁(yè)數(shù)據(jù)的類(lèi)型轉(zhuǎn)換工具,解決這個(gè)問(wèn)題,對(duì)mybatis-plus?分頁(yè)工具類(lèi)相關(guān)知識(shí)感興趣的朋友一起看看吧
    2022-03-03
  • Java Swing編寫(xiě)一個(gè)簡(jiǎn)單的計(jì)算器軟件

    Java Swing編寫(xiě)一個(gè)簡(jiǎn)單的計(jì)算器軟件

    大家好,本篇文章主要講的是Java Swing編寫(xiě)一個(gè)簡(jiǎn)單的計(jì)算器軟件,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下,方便下次瀏覽
    2021-12-12
  • Java中Runnable和Callable分別什么時(shí)候使用

    Java中Runnable和Callable分別什么時(shí)候使用

    提到 Java 就不得不說(shuō)多線(xiàn)程了,就算你不想說(shuō),面試官也得讓你說(shuō)呀,那說(shuō)到線(xiàn)程,就不得不說(shuō)Runnable和Callable這兩個(gè)家伙了,二者在什么時(shí)候使用呢,下面就來(lái)和簡(jiǎn)單講講
    2023-08-08
  • 淺析Java中為什么要設(shè)計(jì)包裝類(lèi)

    淺析Java中為什么要設(shè)計(jì)包裝類(lèi)

    我們知道Java是一個(gè)面相對(duì)象的編程語(yǔ)言,基本類(lèi)型并不具有對(duì)象的性質(zhì),為了讓基本類(lèi)型也具有對(duì)象的特征,就出現(xiàn)了包裝類(lèi)型,它相當(dāng)于將基本類(lèi)型“包裝起來(lái)”,使得它具有了對(duì)象的性質(zhì),并且為其添加了屬性和方法,豐富了基本類(lèi)型的操作
    2021-06-06
  • Mybatis實(shí)現(xiàn)查詢(xún)相冊(cè)數(shù)據(jù)列表流程講解

    Mybatis實(shí)現(xiàn)查詢(xún)相冊(cè)數(shù)據(jù)列表流程講解

    這篇文章主要介紹了Mybatis實(shí)現(xiàn)查詢(xún)相冊(cè)數(shù)據(jù)列表流程,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧
    2022-12-12
  • 深入理解Java虛擬機(jī)體系結(jié)構(gòu)

    深入理解Java虛擬機(jī)體系結(jié)構(gòu)

    這篇文章主要介紹了深入理解Java虛擬機(jī)體系結(jié)構(gòu),具有一定借鑒價(jià)值,需要的朋友可以參考下
    2018-01-01
  • JAVA初級(jí)項(xiàng)目——實(shí)現(xiàn)圖書(shū)管理系統(tǒng)

    JAVA初級(jí)項(xiàng)目——實(shí)現(xiàn)圖書(shū)管理系統(tǒng)

    這篇文章主要介紹了JAVA如何實(shí)現(xiàn)圖書(shū)管理系統(tǒng),文中示例代碼非常詳細(xì),供大家參考和學(xué)習(xí),感興趣的朋友可以了解下
    2020-06-06
  • Java常用HASH算法總結(jié)【經(jīng)典實(shí)例】

    Java常用HASH算法總結(jié)【經(jīng)典實(shí)例】

    這篇文章主要介紹了Java常用HASH算法,結(jié)合實(shí)例形式總結(jié)分析了Java常用的Hash算法,包括加法hash、旋轉(zhuǎn)hash、FNV算法、RS算法hash、PJW算法、ELF算法、BKDR算法、SDBM算法、DJB算法、DEK算法、AP算法等,需要的朋友可以參考下
    2017-09-09

最新評(píng)論