Java歸并排序代碼怎么寫

本篇內(nèi)容主要講解“Java歸并排序代碼怎么寫”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java歸并排序代碼怎么寫”吧!

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比睢陽(yáng)網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式睢陽(yáng)網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋睢陽(yáng)地區(qū)。費(fèi)用合理售后完善，十年實(shí)體公司更值得信賴。

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

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

歸并排序算法穩(wěn)定，數(shù)組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時(shí)間復(fù)雜度為O(nlog(n))，算法不是自適應(yīng)的，不需要對(duì)數(shù)據(jù)的隨機(jī)讀取。

工作原理：

1、申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列

2、設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

3、比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

4、重復(fù)步驟3直到某一指針達(dá)到序列尾

5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾

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

public void mergeSort(){    long[] workSpace = new long[nElems];    recMergeSort(workSpace,0,nElems-1);    }    private void recMergeSort(long[] workSpace, int lowerBound, int upperBound){    if(lowerBound == upperBound){    return;    }    else{    int mid=(lowerBound+upperBound)/2;    recMergeSort(workSpace, lowerBound, mid);    recMergeSort(workSpace, mid+1, upperBound);    merge(workSpace, lowerBound, mid+1, upperBound);    }    }    private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound){    int j = 0;    int lowerBound = lowPtr;    int mid = highPtr - 1;    int n = upperBound-lowerBound+1;    while(lowPtr<=mid&&highPtr<=upperBound){    if(theArray[lowPtr]<theArray[highPtr]){    workSpace[j++]=theArray[lowPtr++];    }    else{    workSpace[j++]=theArray[highPtr++];    }    }    while(lowPtr<=mid){    workSpace[j++] = theArray[lowPtr++];    }    while(highPtr<=upperBound){    workSpace[j++] = theArray[highPtr++];    }    for(j=0;j<n;j++){    theArray[lowerBound+j]=workSpace[j];    }    }

歸并排序是比較穩(wěn)定的排序.即相等的元素的順序不會(huì)改變.如輸入記錄 1(1) 3(2) 2(3) 2(4) 5(5) (括號(hào)中是記錄的關(guān)鍵字)時(shí)輸出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按輸入的順序.這對(duì)要排序數(shù)據(jù)包含多個(gè)信息而要按其中的某一個(gè)信息排序,要求其它信息盡量按輸入的順序排列時(shí)很重要.這也是它比快速排序優(yōu)勢(shì)的地方.

到此，相信大家對(duì)“Java歸并排序代碼怎么寫”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

本文名稱：Java歸并排序代碼怎么寫
文章URL：http://bm7419.com/article10/jjeido.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、網(wǎng)站內(nèi)鏈、Google、企業(yè)網(wǎng)站制作、靜態(tài)網(wǎng)站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)