只有當前一個元素大于后一個元素時，才需要交換，若前一個元素小于后一個元素，則不需要走第二層循環(huán)。

2.希爾排序

核心思路

希爾排序其實是對插入排序的一種優(yōu)化。

先將待排序的數(shù)組分為若干個子數(shù)組。將子數(shù)組調(diào)整為有序狀態(tài)，不斷變大這個分組長度，當最終分組長度為1時，整個數(shù)組接近有序。最后來一次插入排序即可。

排序步驟

我們來舉一個實例：

1. 首先gap取5，此時相隔距離為5的元素分到了一組（一共五組，每組兩個元素），然后對每一組分別進行插入排序

2. gap折半為2，此時相隔距離為2的元素被分到了一組（一共兩組，每組五個元素），然后對每一組分別進行插入排序

3. gap再次折半為1，此時所有元素被分到了一組，對它進行插入排序，至此插入排序完成
   

本例中前兩趟就是希爾排序的預排序，最后一趟就是希爾排序的插入排序。

代碼

    private static void insertionSortByGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j-gap>=0 && arr[j]<arr[j-gap]; j-=gap) {
                int temp=arr[j];
                arr[j]=arr[j-gap];
                arr[j-gap]=temp;
            }
        }
    }

3.直接選擇排序

核心思路

直接選擇排序：每次在無序區(qū)間中選擇最小值與無序區(qū)間的第一個元素交換，直到整個數(shù)組有序。

排序步驟

1. 定義下標 i 為當前無序區(qū)間的第一個元素，下標 min 為無序區(qū)間的最小值，下標 j 遍歷無序區(qū)間。
2. 有序區(qū)間：[0…i)
3. 無序區(qū)間：[i…n)
4. j 遍歷無序數(shù)組，若 j 指向的元素小于min指向的元素，則min指向此元素。
5. 遍歷完之后，將min指向的元素與 i 指向的元素交換。
   

代碼

    public static void select(int[] arr){
        //有序區(qū)間：[0,i)
        //無序區(qū)間：[i,n)
        int n=arr.length;
        //當無序區(qū)間只剩下一個元素時，已經(jīng)不用再排了
        for (int i=0; i < n-1 ; i++) {
            //min指向無序區(qū)間的最小值
            int min=i;
            for (int j = i+1 ; j < n ; j++) {
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            //此時min一定指向無序區(qū)間的最小值
            int temp=arr[i];
            arr[i]=arr[min];
            arr[min]=temp;
        }
    }

缺點

無論數(shù)組是否接近有序，直接選擇排序都會執(zhí)行一遍內(nèi)部的排序流程，對數(shù)據(jù)不敏感。

4.堆排序

??原地堆排序?qū)懺诹硪黄恼铝藒

?原地堆排序

5.冒泡排序

核心思路

重復掃描待排序序列，并比較每一對相鄰的元素，當該對元素順序不正確時進行交換。一直重復這個過程，直到?jīng)]有任何兩個相鄰元素可以交換，就表明完成了排序。

排序步驟

1. 比較相鄰兩個數(shù)據(jù)如果。第一個比第二個大，就交換兩個數(shù)
2. 對每一個相鄰的數(shù)做同樣1的工作，這樣從開始一隊到結(jié)尾一隊在最后的數(shù)就是最大的數(shù)。
3. 針對所有元素上面的操作，除了最后一個。
4. 重復1~3步驟，直到順序完成。

代碼

    public static void bubbleSort(int[]arr){
        //外層循環(huán)表示要進行元素操作的趟數(shù)
        for (int i = 0; i < arr.length-1; i++) {
            boolean isSwaped=false;
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    isSwaped=true;
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
            if(!isSwaped){
                break;
            }
        }
    }

6.快速排序

??快速排序?qū)懺诹硪黄恼铝藒

?快速排序詳解

7.歸并排序

核心思路

1.歸： 先不斷的將原數(shù)組一分為二，直到拆分后的子數(shù)組只剩下一個元素。（當數(shù)組只有一個元素時，天然有序）
2.并： 不斷的將兩個連續(xù)的有序子數(shù)組合并為一個大的數(shù)組，直到整個數(shù)組合并完成。

排序步驟

并的核心步驟：給定一個臨時數(shù)組 aux 存儲即將歸并的子數(shù)組的值。

代碼

    public static void mergeSort(int[]arr){
        mergeSortInternal(arr,0,arr.length-1);
    }

    private static void mergeSortInternal(int[] arr, int l, int r) {
        if(l>=r){
            return;
        }
        int mid=l+((r-l)>>2);
        //先將原數(shù)組一分為二，在子數(shù)組上進行歸并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid+1,r);
        //此時兩個子數(shù)組已經(jīng)有序,將兩個子數(shù)組合并為原數(shù)組
        merge(arr,l,mid,r);
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        //創(chuàng)建一個臨時數(shù)組
        int[] aux=new int[r-l+1];
        //拷貝子數(shù)組的數(shù)據(jù)到臨時數(shù)組上
        System.arraycopy(arr,l,aux,0,r-l+1);
        //兩個子數(shù)組的開始索引
        int i=l;
        int j=mid+1;
        //k表示當前原數(shù)組合并到哪個位置
        for (int k = l; k <= r; k++) {
            if(i>mid){
                //此時子數(shù)組1全部拷貝完畢，將子數(shù)組2的內(nèi)容全部寫回
                arr[k] = aux[j-l];
                j++;
            }else if(j>r){
                //此時子數(shù)組2全部拷貝完畢，將子數(shù)組1的內(nèi)容全部寫回
                arr[k] = aux[i-l];
                i++;
            }else if(aux[i-l]<=aux[j-l]){
                arr[k]=aux[i-l];
                i++;
            }else{
                arr[k]=aux[j-l];
                j++;
            }
        }
    }

補充：希爾排序的圖片參考了這篇博文：希爾排序文章來源地址http://www.zghlxwxcb.cn/news/detail-651538.html

到了這里，關于【JAVA】七大排序算法(圖解)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！