java版十大排序經(jīng)典算法:完整代碼(3)

更新時(shí)間：2021年07月27日 09:35:33 作者：牛哄哄的柯南

優(yōu)秀的文章也不少，但是Java完整版的好像不多，我把所有的寫一遍鞏固下，同時(shí)也真誠的希望閱讀到這篇文章的小伙伴們可以自己去從頭敲一遍，不要粘貼復(fù)制！希望我的文章對(duì)你有所幫助，每天進(jìn)步一點(diǎn)點(diǎn)

歸并排序

簡單解釋：該算法是采用分治法，把數(shù)組不斷分割，直至成為單個(gè)元素，然后比較再合并（合并的過程就是兩部分分別從頭開始比較，取出最小或最大元素的放到新的區(qū)域內(nèi)，繼續(xù)取兩部分中最大或最小的元素，直到這兩部分合并完，最后所有的都合并完，最后形成完整的有序序列）

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: MergeSort
 * @Description: 歸并排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:35
 */
public class MergeSort {
    //歸并排序
    public static void mergeSort(int []arr ,boolean ascending){
        int[] temp = new int[arr.length]; //在排序前，先建好一個(gè)長度等于原數(shù)組長度的臨時(shí)數(shù)組，避免遞歸中頻繁開辟空間
        mergeSort(arr,0,arr.length-1,temp,ascending);
    }
    public static void mergeSort(int []arr){
        mergeSort(arr,true);
    }
    /**
     *
     * @param arr 傳入的數(shù)組
     * @param left 當(dāng)前子數(shù)組的起始下標(biāo)
     * @param right 當(dāng)前子數(shù)組的結(jié)束下標(biāo)
     * @param temp 拷貝暫存數(shù)組
     */
    public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){
        if(left<right){ //這里是遞歸結(jié)束的條件，我們是對(duì)半分，那當(dāng)left==right的時(shí)候肯定大家都是只有一個(gè)元素了。
            //對(duì)半分，比如總長度是10，left=0，right=9，mid=4確實(shí)是中間分了，0~4，5~9
            //當(dāng)長度9，left=0，right=8，mid=4，0~4，5~8
            int mid = left + (right-left)/2; // 防止越界的寫法
            //int mid = (left+right)/2;
            mergeSort(arr,left,mid,temp,ascending); //左邊歸并排序，使得左子序列有序
            mergeSort(arr,mid+1,right,temp,ascending); //右邊歸并排序，使得右子序列有序
            merge(arr,left,mid,right,temp,ascending); //將兩個(gè)有序子數(shù)組合并操作
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){
        int i = left; //左序列起始下標(biāo)
        int j = mid+1; //右序列起始下標(biāo)
        int t = 0; //臨時(shí)數(shù)組指針
        while(i<=mid&&j<=right){
            if(ascending?arr[i]<arr[j]:arr[i]>arr[j]){ //比較兩個(gè)序列第一個(gè)元素誰小，誰小先拷貝誰到temp，然后對(duì)應(yīng)子序列下標(biāo)加1
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){ //將左邊剩余元素填充進(jìn)temp中——左序列有一些數(shù)總是比右邊的大的數(shù)
            temp[t++] = arr[i++];
        }
        while(j<=right){ //將右序列剩余元素填充進(jìn)temp中——右序列有一些數(shù)總是比左邊的大的數(shù)
            temp[t++] = arr[j++];
        }
        t = 0;
        //將temp中的元素全部拷貝到原數(shù)組中
        while(left<=right){
            arr[left++] = temp[t++];
        }
    }
}

插入排序

簡單解釋：最簡單的理解就是打地主時(shí)我們拿到牌后的整理過程，從第二個(gè)牌（假設(shè)我們拿起來這個(gè)牌開始比較）開始，（說下升序）從后往前比較如果比前面的那個(gè)牌小，就把牌往后移動(dòng)，直到找到一個(gè)合適的位置（這個(gè)位置的前面的那個(gè)牌不比這個(gè)要放下的牌大）就把這個(gè)牌放到這個(gè)位置，慢慢的前面的部分變得有序，直至全部有序即可。

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: StraghtInsertSort
 * @Description: 插入排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:36
 */
public class StraghtInsertSort {
    //插入排序
    public static void straghtInsertSort(int[] arr) {
        straghtInsertSort(arr, true);//默認(rèn)進(jìn)行升序
    }
    public static void straghtInsertSort(int[] arr, boolean ascending) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j=0; //這就是那個(gè)合適的位置
            for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) {
                arr[j + 1] = arr[j];
            }
            //把牌放下，為啥是j+1，
            //是因?yàn)樯厦娴难h(huán)遍歷到不符合情況的時(shí)候 j是合適的位置的前面的那個(gè)數(shù)的位置
            //有點(diǎn)拗口，但是就是這個(gè)意思，看圖方便理解下
            arr[j + 1] = temp;

        }
    }
}

希爾排序

簡單解釋：希爾排序是插入排序的改進(jìn)版，我們理解一個(gè)叫做下標(biāo)差的的東西，也就是下面那個(gè)圖中的增量d，初始下標(biāo)差為arr.length/2，然后繼續(xù)/2，對(duì)在同一下標(biāo)差（相當(dāng)于把這幾個(gè)數(shù)單獨(dú)拿出來了）的若干個(gè)數(shù)進(jìn)行插入排序即可。

完整代碼：

package com.keafmd.Sequence;
/**
 * Keafmd
 *
 * @ClassName: ShellSort
 * @Description: 希爾排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 10:39
 */
public class ShellSort {
    public static void shellSort(int[] arr) {
        shellSort(arr,true);
    }
    public static void shellSort(int[] arr,boolean ascending) {
        for(int d = arr.length/2;d>0;d/=2){
            for(int i=d;i< arr.length;i++){
                int temp = arr[i];
                int j=0;
                for(j=i-d;j>=0&&(ascending?temp<arr[j]:temp>arr[j]);j-=d){
                    arr[j+d]=arr[j];
                }
                arr[j+d] = temp;
            }
        }
    }
}