百度:
? ??歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用件已。將已有序的子序列合并,得到完全有序的序列奈懒;即先使每個(gè)子序列有序掸掏,再使子序列段間有序文搂。若將兩個(gè)有序表合并成一個(gè)有序表瑰枫,稱為二路歸并斟叼。
我的理解:
? ? 首先將一組無(wú)序的數(shù)組按照長(zhǎng)度進(jìn)行等分拆分偶惠,直到分成只有一個(gè)數(shù)字,然后再進(jìn)行相鄰之間的比較朗涩,從而再合并起來(lái)忽孽。是一種先分后和的做法,高逼格說(shuō)法為分治法(分治法通常要運(yùn)用遞歸方法)谢床。
腦補(bǔ)例子:
? ? 原數(shù)組 ????[5,1,6,7,1,6,8,2,10]
? ? 使用遞歸進(jìn)行拆分后結(jié)果? ? 5 1 6 7 1 6 8 2 10????
? ? 第一次歸并后? ? {1,5}(+1){6,7} {1,6}(+1){2,8}(+1){10}? ? 共比較3次
????第二次歸并后? ? {1,5,6,7} (+2) {1,2,6,8} (+3)? {10}? ? 共比較5次
? ? 第三次歸并? ? {1,1,2,5,6,6,7,8} (+6)? ? {10}? ? 共比較6次
? ? 第四次歸并? ? ?{1,1,2,5,6,6,7,8,10}? {+8}? ? ?共比較8次? ??
????自己寫的數(shù)組兄一,死都要排完......
實(shí)現(xiàn)代碼(java):
package com.company;
import java.util.Arrays;public class Main {
????public static void main(String[] args) {
????????int[] arr = new int[]{1, 4, 6, 83, 5, 7, 2, 10};
//? ? ? Main.merge(arr,0,(arr.length-1)/2,arr.length-1);
????????Main.mergeSort(arr, 0, arr.length - 1);????????
????????System.out.println(Arrays.toString(arr));
}? ??
//歸并排序????
private static void mergeSort(int[] arr, int low, int hight) {
????????int middle = (hight + low) / 2;
????????//結(jié)束條件
????????if (low < hight) {
????????????//處理左邊
????????????mergeSort(arr, low, middle);
????????????//處理右邊?
???????????mergeSort(arr, middle + 1, hight);
????????????//歸并
????????????merge(arr, low, middle, hight);
????????}
????}
????public static void merge(int[] arr, int low, int midden, int hight) {
????????//用來(lái)存儲(chǔ)歸并后的臨時(shí)數(shù)組
????????int[] temp = new int[hight - low + 1];
????????//記錄第一個(gè)數(shù)組中需要遍歷的下標(biāo)
????????int i = low;
????????//記錄第二個(gè)數(shù)組中需要遍歷的下標(biāo)
????????int j = midden + 1;?
???????//用于記錄臨時(shí)數(shù)組中存放的下標(biāo)
????????int index = 0;
????????//遍歷兩組數(shù)組取出最小數(shù)字,放入臨時(shí)數(shù)組
????????while (i <= midden && j <= hight) {
????????????//第一組數(shù)組的數(shù)字比第二組數(shù)組小
????????????if (arr[i] <= arr[j]) {
????????????????temp[index] = arr[i];
????????????????i++;
????????????}
????????????//反之
????????????else {
????????????????temp[index] = arr[j];
????????????????j++;?
???????????}
????????????index++;
????????}
????????//當(dāng)?shù)谝唤M數(shù)組有剩下數(shù)時(shí)识腿,再把剩下的全部添加進(jìn)臨時(shí)數(shù)組
????????while (i <= midden) {
????????????temp[index] = arr[i];
????????????i++;
????????????index++;
????????}
????????//當(dāng)?shù)诙M數(shù)組有剩下數(shù)時(shí)出革,再把剩下的全部添加進(jìn)臨時(shí)數(shù)組
????????while (j <= hight) {?
???????????temp[index] = arr[j];
????????????j++;
????????????index++;
????????}
????????//把臨時(shí)數(shù)組重新放到原數(shù)組中
????????for (int k = 0; k < temp.length; k++) {
????????????arr[k + low] = temp[k];
????????}
????}
}?