溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關利用java 怎么實現一個歸并排序算法，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
歸并排序算法，顧名思義，是一種先分再合的算法，其算法思想是將要排序的數組分解為單個的元素，每個元素就是一個單個的個體，然后將相鄰的兩個元素進行從小到大或從大到小的順序排序組成一個整體，每個整體包含一到兩個元素，然后對相鄰的整體繼續“合”并，因為每個整體都是排過序的，因而可以采用一定的算法對其進行合并，合并之后每個整體包含三到四個元素，繼續對相鄰的整體進行合并，直到所有的整體都合并為一個整體，最終得到的整體就是將原數組進行排序之后的結果。
對于相鄰的整體，其合并的思想是每次都取兩個整體（假設其實按升序排序的）中最小的元素放到一個新數組中，依次循環，最終兩個整體中的元素都被取完即可得到一個按升序排序的整體。該合并過程就像有兩個升序排序的牌堆A和B（如圖所示），每次從最頂上取出一個元素放到牌堆C中：
從圖中可以看出，對于兩個相鄰的整體A和B，其內的元素都是按升序排序的，現在有一個臨時數組C，然后對A和B頂部的兩個元素進行比較，取出較小的一個元素放入C中，對于取出元素的整體，其指向元素的下標下移一位，繼續取出兩個整體中頂部元素較小的一個放入C中，依次循環，當某個整體元素取完之后直接將另一個整體的元素都移入C中。對于C這個整體，其就是經過A和B排序而得到的，由于A和B是相鄰的兩個整體，因而，最后只需要將C中的元素復制到A和B組成的一個共同整體中即可，這樣也就達到了將A和B合并的同時進行排序的目的。
以下是歸并排序的具體算法：
public class MergeSort {
public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr) {
AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
mergeSort(arr, 0, arr.length - 1, tmp);
}
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp) {
if (start < end) {
int mid = (start + end) >> 1;
mergeSort(arr, start, mid, tmp);
mergeSort(arr, mid + 1, end, tmp);
merge(arr, start, mid, end, tmp);
}
}
private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp) {
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end) {
if (arr[i].compareTo(arr[j]) < 0) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= end) {
tmp[k++] = arr[j++];
}
for (int m = start; m <= end; m++) {
arr[m] = tmp[m];
}
}
}代碼中主要有兩個方法
private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] arr, int start, int end, AnyType[] tmp)
private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] arr, int start, int mid, int end, AnyType[] tmp)
第一個方法是一個遞歸方法，對于遞歸方法，一定要明晰該方法功能的定義，這里這個遞歸方法的目的就是對傳入數組的start到end之間的元素進行排序，而tmp則是一個輔助數組。在該方法的具體實現中，我們可以看到，其思路是首先對start到mid之間的元素繼續調用遞歸進行排序，然后是對mid到end之間的元素調用遞歸進行排序，經過這兩個方法，從start到mid和從mid到end兩部分的元素都是經過排序的，此時就需要調用第二個方法。
第二個方法的功能是對兩個已經排序的部分進行合并，對于第一個方法，最后一步執行了第二個方法也即對前面兩步排序的部分進行合并之后也就完成了該方法的功能。而對于第二個方法，實現思路和前面描述的一樣，分別從兩堆牌頂取出較小的一個元素放入臨時數組中，當一個牌堆取完之后就將剩下的數組的元素放入第二個牌堆，最后將臨時數組的元素放回到原始數組中。
以上就是利用java 怎么實現一個歸并排序算法，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
