成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

Java排序之歸并排序

gityuan / 2197人閱讀

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

Java排序之歸并排序 1. 簡介

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

2. 歸并排序思路

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

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

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

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

3. 代碼實例

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

// 基礎(chǔ)，合并兩個有序數(shù)組
public static int[] merge2Arr(int[] arr1, int[] arr2) {
  int len1 = arr1.length;
  int len2 = arr2.length;
  int[] res = new int[len1 + len2];  // 使用一個數(shù)組用來存儲排好序的數(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;
}
歸并排序的遞歸實現(xiàn)： 
// 歸并排序，遞歸實現(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;  // 當待排序的序列長度為1時，遞歸開始回溯，進行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++];
  }
}
歸并排序的非遞歸實現(xiàn)（迭代）： 
// 歸并排序，非遞歸實現(xiàn)(迭代)
public void sortMergeIteration(int[] nums) {
  int len = 1;  // 初始排序數(shù)組的長度
  while(len < nums.length) {
    for(int i = 0; i < nums.length; i += len * 2) {
      sortMergeIterationHelper(nums, i, len);
    }
    len *= 2;  // 每次將排序數(shù)組的長度*2
  }
}
/**
 * 輔助函數(shù)
 * @param nums  原數(shù)組
 * @param start 從start位置開始
 * @param len  本次合并的數(shù)組長度
 */
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也可能超出長度
    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++];
  }
}

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

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

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

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

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/69663.html

相關(guān)文章

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

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

    zhou_you 評論0 收藏0

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

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

    caoym 評論0 收藏0

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

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

    microcosm1994 評論0 收藏0

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

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

    Jokcy 評論0 收藏0

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

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

    silvertheo 評論0 收藏0

發(fā)表評論

0條評論

gityuan

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<