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

java 算法之歸并排序詳解及實(shí)現(xiàn)代碼

 更新時(shí)間:2017年03月01日 16:01:16   投稿:lqh  
這篇文章主要介紹了java 算法之歸并排序詳解及實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下

java 算法之歸并排序詳解

一、思想

歸并排序:將一個(gè)數(shù)組排序,可以先(遞歸地)將它分成兩半部份分別排序,然后將結(jié)果歸并起來;  

二、概念

歸并:將兩個(gè)有序的數(shù)組歸并成一個(gè)更大的有序數(shù)組;  

三、特點(diǎn)

優(yōu)點(diǎn):能夠保證將任意長(zhǎng)度為N的數(shù)組排序所需要的時(shí)間和NlogN成正比;

缺點(diǎn):需要額外的空間和N成正比; 

 四、實(shí)現(xiàn)方法

將兩個(gè)不同的有序數(shù)組歸并到第三個(gè)數(shù)組中;

先將前半部分排序,在將后半部分排序,然后在數(shù)組中移動(dòng)元素而不需要使用額外的空間; 

五、代碼

/** 
 * 歸并排序 
 *  
 * @author pengcx 
 *  
 */  
public class Merge extends Sort {  
  /** 歸并所需的輔助數(shù)組 */  
  private static Comparable[] aux;  
  
  public static void main(String[] args) {  
    String[] a = { "d", "a", "w", "b", "q" };  
    Merge.sort(a);  
    show(a);  
  }  
  
  public static void sort(Comparable[] a) {  
    aux = new Comparable[a.length];  
    sort(a, 0, a.length - 1);  
  }  
  
  /** 
  * 排序數(shù)組的a[lo]至a[hi]元素 
  *  
  * @param a 
  *      數(shù)組a 
  * @param lo 
  *      最小元素位置lo 
  * @param hi 
  *      最大元素位置hi 
  */  
  private static void sort(Comparable[] a, int lo, int hi) {  
    if (hi <= lo) {  
      return;  
    }  
  
    // 計(jì)算數(shù)組中間位置  
    int mid = lo + (hi - lo) / 2;  
    // 排序數(shù)組a左邊的元素  
    sort(a, lo, mid);  
    // 排序數(shù)組a右邊的元素  
    sort(a, mid + 1, hi);  
    // 合并數(shù)組a左邊和右邊的元素  
    merge(a, lo, mid, hi);  
  }  
  
  /** 
  * 將數(shù)組a的a[lo]至a[mid]的元素與a[mid]至a[hi]的元素合并 
  *  
  * @param a 
  *      合并的數(shù)組a 
  * @param lo 
  *      最小數(shù)組元素lo 
  * @param mid 
  *      中間元素位置mid 
  * @param hi 
  *      最大元素位置hi 
  */  
  public static void merge(Comparable[] a, int lo, int mid, int hi) {  
    int i = lo, j = mid + 1;  
  
    for (int k = lo; k <= hi; k++) {  
      aux[k] = a[k];  
    }  
  
    for (int k = lo; k <= hi; k++) {  
      // 如果左邊的元素用盡,取右邊的元素  
      if (i > mid) {  
        a[k] = aux[j++];  
      }  
      // 如果右邊的元素用盡,取左邊的元素  
      else if (j > hi) {  
        a[k] = aux[i++];  
      }  
      // 如果右半邊的當(dāng)前元素小于左半邊的當(dāng)前元素,取右半邊元素  
      else if (less(aux[j], aux[i])) {  
        a[k] = aux[j++];  
      }  
      // 如果右半邊的當(dāng)前元素大于等于左半邊的當(dāng)前元素,取左半邊元素  
      else {  
        a[k] = aux[i++];  
      }  
    }  
  }  
}  

感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!

相關(guān)文章

  • Java導(dǎo)入新項(xiàng)目報(bào)錯(cuò)java:JDK?isn‘t?specified?for?module解決辦法

    Java導(dǎo)入新項(xiàng)目報(bào)錯(cuò)java:JDK?isn‘t?specified?for?module解決辦法

    這篇文章主要給大家介紹了關(guān)于Java導(dǎo)入新項(xiàng)目報(bào)錯(cuò)java:JDK?isn‘t?specified?for?module的解決辦法,當(dāng)您在導(dǎo)入Java項(xiàng)目時(shí)遇到錯(cuò)誤時(shí),可以嘗試以下面的方法來處理,需要的朋友可以參考下
    2024-05-05
  • SpringBoot項(xiàng)目中連接Gauss數(shù)據(jù)庫

    SpringBoot項(xiàng)目中連接Gauss數(shù)據(jù)庫

    本文主要介紹了SpringBoot項(xiàng)目中連接Gauss數(shù)據(jù)庫,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2024-06-06
  • Java讓多線程按順序執(zhí)行的幾種方法

    Java讓多線程按順序執(zhí)行的幾種方法

    本文主要介紹了Java讓多線程按順序執(zhí)行的幾種方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-05-05
  • 詳解spring cloud分布式整合zipkin的鏈路跟蹤

    詳解spring cloud分布式整合zipkin的鏈路跟蹤

    這篇文章主要介紹了詳解spring cloud分布式整合zipkin的鏈路跟蹤,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2018-07-07
  • Java?LocalTime的常用時(shí)間操作總結(jié)

    Java?LocalTime的常用時(shí)間操作總結(jié)

    日常開發(fā)中,?我們會(huì)經(jīng)常遇到時(shí)間的運(yùn)算,?操作,?格式化等,?這篇文章主要為大家詳細(xì)介紹了LocalTime的常用時(shí)間操作,感興趣的小伙伴可以了解一下
    2023-11-11
  • 單機(jī)redis分布式鎖實(shí)現(xiàn)原理解析

    單機(jī)redis分布式鎖實(shí)現(xiàn)原理解析

    這篇文章主要介紹了單機(jī)redis分布式鎖實(shí)現(xiàn)原理解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • SpringData Repository接口用法解析

    SpringData Repository接口用法解析

    這篇文章主要介紹了SpringData Repository接口用法解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-08-08
  • java協(xié)變返回類型使用示例

    java協(xié)變返回類型使用示例

    在面向?qū)ο蟪绦蛟O(shè)計(jì)中,協(xié)變返回類型指的是子類中的成員函數(shù)的返回值類型不必嚴(yán)格等同于父類中被重寫的成員函數(shù)的返回值類型,而可以是更"狹窄"的類型
    2014-02-02
  • java Hibernate 一對(duì)多自身關(guān)聯(lián)問題

    java Hibernate 一對(duì)多自身關(guān)聯(lián)問題

    formBean在提交表單的時(shí)候,域中數(shù)據(jù)庫在下一次中仍然保留引起的,struts formBean 默認(rèn)的scope為session,手動(dòng)設(shè)置為request,就好了
    2008-07-07
  • 徹底理解Java 中的ThreadLocal

    徹底理解Java 中的ThreadLocal

    這篇文章主要介紹了徹底理解Java 中的ThreadLocal的相關(guān)資料,需要的朋友可以參考下
    2017-07-07

最新評(píng)論