国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

打開(kāi)APP
userphoto
未登錄

開(kāi)通VIP,暢享免費(fèi)電子書(shū)等14項(xiàng)超值服

開(kāi)通VIP
Java實(shí)現(xiàn)歸并排序(Merge-Sort)算法

歸并排序算法思想:

 分而治之(divide - conquer);每個(gè)遞歸過(guò)程涉及三個(gè)步驟

第一, 分解: 把待排序的 n 個(gè)元素的序列分解成兩個(gè)子序列, 每個(gè)子序列包括 n/2 個(gè)元素.

第二, 治理: 對(duì)每個(gè)子序列分別調(diào)用歸并排序MergeSort, 進(jìn)行遞歸操作 .

第三, 合并: 合并兩個(gè)排好序的子序列,生成排序結(jié)果.

教材上的偽碼描述:

MERGE(A, p, q, r)1  n1  q - p + 1//修改為 n1 ← q - p2  n2  r - q    //修改 n2 ← r - q + 13  create arrays L[1  n1 + 1] and R[1  n2 + 1]4  for i  1 to n15       do L[i]  A[p + i - 1]6  for j  1 to n27       do R[j]  A[q + j]8  L[n1 + 1]  9  R[n2 + 1]  10  i  111  j  112  for k  p to r13       do if L[i]  R[j]14             then A[k]  L[i]15                  i  i + 116             else A[k]  R[j]17                  j  j + 1
MERGE-SORT(A, p, r)1 if p < r2   then q  (p + r)/23        MERGE-SORT(A, p, q)4        MERGE-SORT(A, q + 1, r)5        MERGE(A, p, q , r)//修改為MERGE(A, p, q + 1, r)
 
 
共有三個(gè)修改之處,按照教材中的描述結(jié)合Java數(shù)組下標(biāo)從0開(kāi)始的規(guī)定若修改為
MERGE(A, p, q, r)1  n1  q - p + 1//修改為 n1 ← q - p2  n2  r - q    //修改 n2 ← r - q MERGE-SORT(A, p, r)4        MERGE-SORT(A, q + 1, r)程序不能正常運(yùn)行,暫時(shí)還不太清楚問(wèn)題出在什么地方,懷疑和編譯器對(duì)遞歸算法的實(shí)現(xiàn)有關(guān).
按我所修改的方法,其具體實(shí)現(xiàn)代碼如下:
 
package org.chw;
public class MergeSortAlgorithm {
 final static int MAXVALUE = 10000;
 static int[] L;
 static int[] R;
 public static void Merge(int[] A,int p,int q,int r){
  int n1=q-p;//correct
  int n2=r-q+1;//correct
  //int n1 = q-p;
  //int n2 = r-q;
  L = new int[n1+1];
  R = new int[n2+1];
  for(int i = 0;i < n1;i++){
   L[i] = A[p+i];
  }
   
  
  for(int j = 0;j < n2;j++){
   R[j] = A[q+j];
  }
  L[n1]=MAXVALUE;
  R[n2]=MAXVALUE;
  
  int i = 0,j = 0;
  for(int k = p; k <= r ;k++){
  //for(int k = p; k < r ;k++){
    if(L[i]<=R[j]){
     A[k] = L[i];
     i++;
    }else{
     A[k] = R[j];
     j++;
    }
   }
 }
 
 public static void MergeSort(int[] A,int p,int r){
  int q;
  if(p<r){
   q = (p+r)/2;
   /*correctness*/
   MergeSort(A,p,q);
   MergeSort(A,q+1,r);
   Merge(A,p,q+1,r);
   /*test*//*
   MergeSort(A,p,q);
   MergeSort(A,q,r);
   Merge(A,p,q,r);*/
  }
 }
 
 public static void main(String[] args){
  
  int[] inputArray={1,3,2,6,5,2,4,7,1,3,2,6,5,2,4,7,1,3,2,6,5,2,4,7,1,3};
  
  MergeSort(inputArray,0,inputArray.length-1);
    
  for(int i=0;i<inputArray.length;i++){
   System.out.println("intArray["+i+"]="+inputArray[i]);
  }
 }
}
本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊舉報(bào)。
打開(kāi)APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
編程5大算法總結(jié)
幾種排序算法的改進(jìn)
八種排序算法總結(jié)(7)
【排序結(jié)構(gòu)4】 歸并排序
排序1+4:歸并排序(MergeSort)和堆排序(HeapSort)
八大排序算法實(shí)戰(zhàn):思想與實(shí)現(xiàn)(下)
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長(zhǎng)圖 關(guān)注 下載文章
綁定賬號(hào)成功
后續(xù)可登錄賬號(hào)暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服