成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Java排序之歸并排序

gityuan / 2152人閱讀

摘要：排序之歸并排序簡(jiǎn)介歸并排序的算法是將多個(gè)有序數(shù)據(jù)表合并成一個(gè)有序數(shù)據(jù)表。如果參與合并的只有兩個(gè)有序表，則成為二路合并。對(duì)于一個(gè)原始的待排序數(shù)列，往往可以通過(guò)分割的方法來(lái)歸結(jié)為多路合并排序。

Java排序之歸并排序 1. 簡(jiǎn)介

歸并排序的算法是將多個(gè)有序數(shù)據(jù)表合并成一個(gè)有序數(shù)據(jù)表。如果參與合并的只有兩個(gè)有序表，則成為二路合并。對(duì)于一個(gè)原始的待排序數(shù)列，往往可以通過(guò)分割的方法來(lái)歸結(jié)為多路合并排序。

2. 歸并排序思路

將長(zhǎng)度為n的待排序數(shù)組看做是由n個(gè)有序長(zhǎng)度為1的數(shù)組組成

將其兩兩合并，得到長(zhǎng)度為2的有序數(shù)組

然后再對(duì)這些子表進(jìn)行合并，得到長(zhǎng)度為4的有序數(shù)組

重復(fù)上述過(guò)程，一直到最后的子表長(zhǎng)度為n也就完成了排序

3. 代碼實(shí)例

歸并排序有兩種實(shí)現(xiàn)方式：遞歸和非遞歸。在看歸并排序的代碼之前先來(lái)看一下怎么和合并兩個(gè)有序數(shù)組：

// 基礎(chǔ)，合并兩個(gè)有序數(shù)組
public static int[] merge2Arr(int[] arr1, int[] arr2) {
  int len1 = arr1.length;
  int len2 = arr2.length;
  int[] res = new int[len1 + len2];  // 使用一個(gè)數(shù)組用來(lái)存儲(chǔ)排好序的數(shù)組
  int i = 0, j = 0, k = 0;
  while(i < len1 && j < len2) {
    res[k++] = arr1[i] < arr2[j]? arr1[i++] : arr2[j++];
  }
  while(i < len1) {
    res[k++] = arr1[i++];
  }
  while(j < len2) {
    res[k++] = arr2[j++];
  }
  return res;
}
歸并排序的遞歸實(shí)現(xiàn)： 
// 歸并排序，遞歸實(shí)現(xiàn)
public void sortMergeRecursion(int[] nums) {
  sortMergeRecursionHelper(nums, 0, nums.length - 1);
}
public void sortMergeRecursionHelper(int[] nums,int left, int right) {
  if(left == right) return;  // 當(dāng)待排序的序列長(zhǎng)度為1時(shí)，遞歸開(kāi)始回溯，進(jìn)行merge
  int middle = left + (right - left) / 2;
  sortMergeRecursionHelper(nums, left, middle);
  sortMergeRecursionHelper(nums, middle + 1, right);
  mergeArr(nums, left, middle, right);
}
public void mergeArr(int[] nums, int left, int middle, int right) {
  int[] tem = new int[right - left + 1];
  int i = left, j = middle + 1, k = 0;
  while(i <= middle && j <= right) {
    tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
  }
  while(i <= middle) {
    tem[k++] = nums[i++];
  }
  while(j <= right) {
    tem[k++] = nums[j++];
  }
  // 將輔助數(shù)組數(shù)據(jù)寫入原數(shù)組
  int index = 0;
  while(left <= right) {
    nums[left++] = tem[index++];
  }
}
歸并排序的非遞歸實(shí)現(xiàn)（迭代）： 
// 歸并排序，非遞歸實(shí)現(xiàn)(迭代)
public void sortMergeIteration(int[] nums) {
  int len = 1;  // 初始排序數(shù)組的長(zhǎng)度
  while(len < nums.length) {
    for(int i = 0; i < nums.length; i += len * 2) {
      sortMergeIterationHelper(nums, i, len);
    }
    len *= 2;  // 每次將排序數(shù)組的長(zhǎng)度*2
  }
}
/**
 * 輔助函數(shù)
 * @param nums  原數(shù)組
 * @param start 從start位置開(kāi)始
 * @param len  本次合并的數(shù)組長(zhǎng)度
 */
public void sortMergeIterationHelper(int[] nums, int start, int len) {
  int[] tem = new int[len * 2];
  int i = start;
  int j = start + len;
  int k = 0;
  while(i < start + len && (j < start + len + len && j < nums.length)) {
    tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
  }
  while(i < start + len && i < nums.length) {  // 注意：這里i也可能超出長(zhǎng)度
    tem[k++] = nums[i++];
  }
  while(j < start + len + len && j < nums.length) {
    tem[k++] = nums[j++];
  }
  int right = start + len + len;
  int index = 0;
  while(start < nums.length && start < right) {
    nums[start++] = tem[index++];
  }
}

歸并排序的時(shí)間復(fù)雜度為O(n*log2n),空間復(fù)雜度為O(n)

歸并排序是一種穩(wěn)定的排序方法。

參考：
https://blog.csdn.net/y999666...

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69663.html

相關(guān)文章

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見(jiàn)的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。用一張圖概括歸并排序英語(yǔ)，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為。 常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 評(píng)論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見(jiàn)的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。用一張圖概括歸并排序英語(yǔ)，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為。 常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    caoym 評(píng)論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,系列之歸并排序

    摘要：常見(jiàn)的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。用一張圖概括歸并排序英語(yǔ)，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為。 常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    microcosm1994 評(píng)論0 收藏0

  • 歸并排序 - Algorithms, Part I, week 3 MERGESORTS

    摘要：兩個(gè)單元素?cái)?shù)組的合并實(shí)際就是對(duì)這兩個(gè)數(shù)進(jìn)行了排序，即變?yōu)?，同樣再?duì)后一組的兩個(gè)數(shù)歸并排序，即變?yōu)?，再將兩單元?shù)組歸并成四單元數(shù)組即和歸并為。 前言 本周講解兩個(gè)50多年前發(fā)明，但今天仍然很重要的經(jīng)典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個(gè)軟件系統(tǒng)中都可以找到其中一個(gè)或兩個(gè)的實(shí)現(xiàn)，并研究這些經(jīng)典方法的新變革。我們的涉及范圍從數(shù)學(xué)模型中解釋為什么這些方法有效到使這些算法...

    Jokcy 評(píng)論0 收藏0

  • java實(shí)現(xiàn)歸并排序

    摘要：歸并排序是一種十分優(yōu)秀的排序方法，在一開(kāi)始學(xué)習(xí)的時(shí)候可能會(huì)對(duì)它的實(shí)現(xiàn)思路有點(diǎn)難以理解，不過(guò)當(dāng)你想通了之后就會(huì)發(fā)現(xiàn)這種方法的絕妙之處。 歸并排序是一種十分優(yōu)秀的排序方法，在一開(kāi)始學(xué)習(xí)的時(shí)候可能會(huì)對(duì)它的實(shí)現(xiàn)思路有點(diǎn)難以理解，不過(guò)當(dāng)你想通了之后就會(huì)發(fā)現(xiàn)這種方法的絕妙之處。 showImg(https://segmentfault.com/img/bVbctoS?w=941&h=560);sh...

    silvertheo 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

gityuan

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<