溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
利用Java編寫一個歸并排序算法？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
一、歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；否則將第二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
二、歸并操作
三、兩路歸并算法
1、算法基本思路
設兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上：R[low..m]，R[m+1..high]，先將它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成后將R1復制回R[low..high]中。
（1）合并過程
合并過程中，設置i，j和p三個指針，其初值分別指向這三個記錄區的起始位置。合并時依次比較R[i]和R[j]的關鍵字，取關鍵字較小的記錄復制到R1[p]中，然后將被復制記錄的指針i或j加1，以及指向復制位置的指針p加1。
重復這一過程直至兩個輸入的子文件有一個已全部復制完畢(不妨稱其為空)，此時將另一非空的子文件中剩余記錄依次復制到R1中即可。
（2）動態申請R1
實現時，R1是動態申請的，因為申請的空間可能很大，故須加入申請空間是否成功的處理。
2、歸并算法
void Merge(SeqList R，int low，int m，int high)
{//將兩個有序的子文件R[low..m)和R[m+1..high]歸并成一個有序的
//子文件R[low..high]
int i=low，j=m+1，p=0； //置初始值
RecType *R1； //R1是局部向量，若p定義為此類型指針速度更快
R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；
if(! R1) //申請空間失敗
Error("Insufficient memory available!")；
while(i<=m&&j<=high) //兩子文件非空時取其小者輸出到R1[p]上
R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；
while(i<=m) //若第1個子文件非空，則復制剩余記錄到R1中
R1[p++]=R[i++]；
while(j<=high) //若第2個子文件非空，則復制剩余記錄到R1中
R1[p++]=R[j++]；
for(p=0，i=low；i<=high；p++，i++)
R[i]=R1[p]；//歸并完成后將結果復制回R[low..high]
} //Merge
四、歸并排序
歸并排序有兩種實現方法：自底向上和自頂向下。下面說說自頂向下的方法
（1）分治法的三個步驟
設歸并排序的當前區間是R[low..high]，分治法的三個步驟是：
①分解：將當前區間一分為二，即求分裂點
②求解：遞歸地對兩個子區間R[low..mid]和R[mid+1..high]進行歸并排序；
③組合：將已排序的兩個子區間R[low..mid]和R[mid+1..high]歸并為一個有序的區間R[low..high]。
遞歸的終結條件：子區間長度為1（一個記錄自然有序）。
（2）具體算法
void MergeSortDC(SeqList R，int low，int high)
{//用分治法對R[low..high]進行二路歸并排序
int mid；
if(low<high){//區間長度大于1
mid=(low+high)/2； //分解
MergeSortDC(R，low，mid); //遞歸地對R[low..mid]排序
MergeSortDC(R，mid+1，high)； //遞歸地對R[mid+1..high]排序
Merge(R，low，mid，high)； //組合，將兩個有序區歸并為一個有序區
}
}//MergeSortDC
（3）算法MergeSortDC的執行過程
算法MergeSortDC的執行過程如下圖所示的遞歸樹。
五、算法分析
1、穩定性
歸并排序是一種穩定的排序。
2、存儲結構要求
可用順序存儲結構。也易于在鏈表上實現。
3、時間復雜度
對長度為n的文件，需進行 趟二路歸并，每趟歸并的時間為O(n)，故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。
4、空間復雜度
需要一個輔助向量來暫存兩有序子文件歸并的結果，故其輔助空間復雜度為O(n)，顯然它不是就地排序。
注意：
若用單鏈表做存儲結構，很容易給出就地的歸并排序。
5、比較操作的次數介于(nlogn) / 2和nlogn - n + 1。
6、賦值操作的次數是(2nlogn)。歸并算法的空間復雜度為：0 (n)
7、歸并排序比較占用內存，但卻是一種效率高且穩定的算法。
六、代碼實現
public class MergeSortTest {
public static void main(String[] args) {
int[] data = new int[] { 2, 4, 7, 5, 8, 1, 3, 6 };
System.out.print("初始化：\t");
print(data);
System.out.println("");
mergeSort(data, 0, data.length - 1);
System.out.print("\n排序后: \t");
print(data);
}
public static void mergeSort(int[] data, int left, int right) {
if (left >= right)
return;
//兩路歸并
// 找出中間索引
int center = (left + right) / 2;
// 對左邊數組進行遞歸
mergeSort(data, left, center);
// 對右邊數組進行遞歸
mergeSort(data, center + 1, right);
// 合并
merge(data, left, center, center + 1, right);
System.out.print("排序中:\t");
print(data);
}
/**
* 將兩個數組進行歸并，歸并前面2個數組已有序，歸并后依然有序
*
* @param data
* 數組對象
* @param leftStart
* 左數組的第一個元素的索引
* @param leftEnd
* 左數組的最后一個元素的索引
* @param rightStart
* 右數組第一個元素的索引
* @param rightEnd
* 右數組最后一個元素的索引
*/
public static void merge(int[] data, int leftStart, int leftEnd,
int rightStart, int rightEnd) {
int i = leftStart;
int j = rightStart;
int k = 0;
// 臨時數組
int[] temp = new int[rightEnd - leftStart + 1]; //創建一個臨時的數組來存放臨時排序的數組
// 確認分割后的兩段數組是否都取到了最后一個元素
while (i <= leftEnd && j <= rightEnd) {
// 從兩個數組中取出最小的放入臨時數組
if (data[i] > data[j]) {
temp[k++] = data[j++];
} else {
temp[k++] = data[i++];
}
}
// 剩余部分依次放入臨時數組（實際上兩個while只會執行其中一個）
while (i <= leftEnd) {
temp[k++] = data[i++];
}
while (j <= rightEnd) {
temp[k++] = data[j++];
}
k = leftStart;
// 將臨時數組中的內容拷貝回原數組中 // （原left-right范圍的內容被復制回原數組）
for (int element : temp) {
data[k++] = element;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}
七、運行結果
初始化： 2 4 7 5 8 1 3 6 排序中: 2 4 7 5 8 1 3 6 排序中: 2 4 5 7 8 1 3 6 排序中: 2 4 5 7 8 1 3 6 排序中: 2 4 5 7 1 8 3 6 排序中: 2 4 5 7 1 8 3 6 排序中: 2 4 5 7 1 3 6 8 排序中: 1 2 3 4 5 6 7 8 排序后: 1 2 3 4 5 6 7 8
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
