Shell排序算法和合并排序算法

Shell排序算法和合并排序算法

Shell排序（希爾排序）算法

Shell排序嚴格來說基于插入排序的思想，其又稱為希爾排序或者縮小增量排序。

Shell排序的流程：

1.将由n個元素的數組分成n/2個數字序列，第1個資料和第n/2+1個資料為一對，......

2.一次循環使每個序列對排序好順序

3.然後，再變為n/4個序列，再次排序。

4.不斷重複上述過程，随着序列減少最後為一個，也就完成整個排序

/**
 * Shell排序（希爾排序）
 * @author Red Ants(guangboyuan.cn) 
 *         微信公衆号：程式員之路 堆排序
 */
public class ShellSort {

    public static void shellSort(int[] a) {
        int x = 0;
        for (int r = a.length / 2; r >= 1; r /= 2) {//分解數組元素為多個序列，每次比較兩數的間距，直到其值為0就結束循環
            for(int i = r;i<a.length;i++){//按設定的間距r,分别比較對應的數組元素。在該循環中使用插入排序法對指定間距的元素進行排序
                int temp = a[i];
                int j = i-r;
                while (j>=0 && temp <a[j]) {
                    a[j+r] = a[j];
                    j-=r;
                }
                a[j+r] = temp;
            }
            x++;
            System.out.println("第"+x+"步排序結構："+Arrays.toString(a));
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,22,77,8,12,54,11,15,2};
        System.out.println("排序前："+Arrays.toString(nums));
        shellSort(nums);
        System.out.println("排序後："+Arrays.toString(nums));
    }
}      

合并排序算法

是用分治政策實作對N個元素進行排序的算法。其基本思想是：

将待排序元素分成大小大緻相同 的兩個子集合，分别 對兩個子集合進行排序，最終将排好序的子集合合并成所要求的排好序的集合。

重點：

1.分治的實作

2.合并的實作

分治，就是把整個集合的元素一直除2化分，一直化為到沒有兩個元素開始合并。

/**
 * 合并排序
 * @author Red Ants(guangboyuan.cn) 
 *         微信公衆号：程式員之路 堆排序
 */
public class MergeSort {

    public static void main(String[] args) {
        MergeSort m = new MergeSort();
        int a[] = { 5, 4, 10, 8, 7, 9, 11 };
        System.out.println("排序前："+Arrays.toString(a));
        m.mergeSort(a, 0, a.length - 1);
        System.out.println("排序後："+Arrays.toString(a));
    }

    public void mergeSort(int[] arrays, int start, int end) {//遞歸算法
        if (start < end) {//出口
            int m = (start + end) / 2;
            mergeSort(arrays, start, m);
            mergeSort(arrays, m + 1, end);
            combin_arrays(arrays, start, m, end);
        }
    }

    // 合并數組
    public void combin_arrays(int[] arrays, int start, int m, int end) {
        int length = end - start + 1;
        int temp[] = new int[length];// 用來存放比較的數組，用完複制回到原來的數組
        int i = start;
        int j = m + 1;
        int c = 0;
        while (i <= m && j <= end) {
            if (arrays[i] < arrays[j]) {
                temp[c] = arrays[i];
                i++;
                c++;
            } else {
                temp[c] = arrays[j];
                j++;
                c++;
            }
        }
        while (i <= m) {
            temp[c] = arrays[i];
            i++;
            c++;
        }
        while (j <= end) {
            temp[c] = arrays[j];
            j++;
            c++;
        }
        c = 0;
        for (int t = start; t <= end; t++, c++) {
            arrays[t] = temp[c];
        }
        System.out.println(Arrays.toString(arrays));
    }
}