歸并排序

2018-07-27 21:04 更新
  1. 基本思想: 歸并(Merge)排序法是將兩個(gè)(或兩個(gè)以上)有序表合并成一個(gè)新的有序表,即把待排序序列分為若干個(gè)子序列,每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
  2. 代碼實(shí)現(xiàn):
    
    /**
     * 打印數(shù)組內(nèi)容
     * 
     * @param a
     */
    public static void saymsg(int[] src) {
        for (int i = 0; i < src.length; i++) {
            System.out.print(src[i]);
            System.out.print(",");
        }
        System.out.println();
    }

public static void mergingSort(int[] data, int left, int right) { if (left < right) { // System.out.println(left+";"+right); int center = (left + right) / 2; mergingSort(data, left, center); mergingSort(data, center + 1, right); merge(data, left, center, right);

} }

public static void merge(int[] data, int left, int center, int right) { // System.out.println(left+";"+center+";"+right); int[] tmpArr = new int[data.length]; int mid = center + 1; int third = left; int tmp = left; while (left <= center && mid <= right) { if (data[left] <= data[mid]) { tmpArr[third++] = data[left++]; } else { tmpArr[third++] = data[mid++]; } } while (mid <= right) { tmpArr[third++] = data[mid++]; } while (left <= center) { tmpArr[third++] = data[left++]; } while (tmp <= right) { data[tmp] = tmpArr[tmp++]; } saymsg(data); }

public static void main(String[] args) { int[] src = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 }; System.out.println("原始數(shù)組排序:"); saymsg(src); if (src.length > 0) { mergingSort(src, 0, src.length - 1); } }


兩個(gè)方法可以分開理解,第一個(gè) 是一個(gè)待比較排序組合,第二個(gè)是數(shù)值的比較


![](//atts.w3cschool.cn/attachments/image/20170727/1501127342130116.gif)
*圖片來(lái)自維基百科*
以上內(nèi)容是否對(duì)您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號(hào)
微信公眾號(hào)

編程獅公眾號(hào)