??1. 排序的概念及引用

1.1 排序的概念

排序：所謂排序，就是對(duì)一組任意數(shù)據(jù)元素(或記錄)經(jīng)過(guò)指定關(guān)鍵字排序操作后，就可以把它們變成一組按照關(guān)鍵字排序的有序序列。通常排序的目的是快速查找。

1.2 十個(gè)排序算法

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。

?1.3 十個(gè)排序性能對(duì)比

【注意】以下排序算法全部為升序排序

為了避免代碼太多的重復(fù)，這里提供一個(gè)swap方法（交換兩個(gè)值），后面多個(gè)排序方法會(huì)用到：

    //    交換兩個(gè)值
    private static void swap(int[] arr,int j, int i) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

??2. 冒泡排序

冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。?

2.1 算法描述

冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較，看是否滿足大小關(guān)系要求。如果不滿足就讓它倆互換。一次冒泡會(huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置，重復(fù) n 次，就完成了 n 個(gè)數(shù)據(jù)的排序工作。

2.2 動(dòng)圖

2.3?代碼

public static void bubbleSort(int[] arr){
        if(arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
//                j + 1保證索引不越界，因此，j < arr.length - i - 1
                if(arr[j] > arr[j + 1]){
                    swap(arr,j,j + 1);
                }
            }          
        }
    }

??代碼優(yōu)化

當(dāng)某次冒泡操作已經(jīng)沒(méi)有數(shù)據(jù)交換時(shí)，說(shuō)明已經(jīng)達(dá)到完全有序，不用再繼續(xù)執(zhí)行后續(xù)的冒泡操作。

    //    冒泡排序
    public static void bubbleSort(int[] arr){
        if(arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwap = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
//                j + 1保證索引不越界，因此，j < arr.length - i - 1
                if(arr[j] > arr[j + 1]){
                    isSwap = true;
                    swap(arr,j,j + 1);
                }
            }
            if(!isSwap){
                break;
            }
        }
    }

??3. 選擇排序

選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。?

3.1 算法描述

• n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。具體算法描述如下：
• 初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
• 第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
• n-1趟結(jié)束，數(shù)組有序化了。

3.2 動(dòng)圖

?3.3 代碼

public static void selectionSort(int[] arr){
        // 起始狀態(tài) : 有序區(qū)間[0..i)
        // 無(wú)序區(qū)間[i....n)
        for (int i = 0; i < arr.length - 1; i++) {
            // min指向的當(dāng)前無(wú)序區(qū)間的最小值,min是下標(biāo)
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            // 此時(shí)min一定指向無(wú)序區(qū)間最小值下標(biāo)，換到無(wú)序區(qū)間的最開(kāi)始位置
            swap(arr,i,min);
        }
    }

??4. 插入排序

插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

4.1 算法描述

• 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
• 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
• 如果該元素（已排序）大于新元素，將該元素移到下一位置；
• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
• 將新元素插入到該位置后；
• 重復(fù)步驟2~5。

4.2 動(dòng)圖

?4.3 代碼

    public static void insertionSort(int[] arr){
        // 無(wú)序區(qū)間[i...n)
        // 有序區(qū)間[0...i)
        // i指向當(dāng)前無(wú)序區(qū)間的第一個(gè)元素
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j - 1 >= 0 && arr[j] < arr[j - 1]; j--) {
//                簡(jiǎn)化寫(xiě)法
                swap(arr,j,j - 1);
//                j - 1 要保證不為負(fù)數(shù) 因此j > 0，而不是 j >= 0
//                if(arr[j] < arr[j - 1]){
//                    swap(arr,j,j - 1);
//                }
            }
        }
    }

??5 希爾排序

1959年Shell發(fā)明，第一個(gè)突破O(n^2)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。希爾排序又叫縮小增量排序。

希爾（Shell）排序又稱縮小增量排序，是對(duì)直接插入排序的優(yōu)化。

5.1 描述

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：

• 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；

• 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；

• 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

5.2 動(dòng)圖

?5.3 代碼

 //    希爾排序（插入排序的優(yōu)化），不穩(wěn)定
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            // 先按照gap分組，組內(nèi)使用插入排序
            insertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
        // 當(dāng)gap == 1時(shí)，整個(gè)數(shù)組接近于有序，此時(shí)來(lái)一個(gè)插入排序
        insertionSortByGap(arr,1);
    }

    // 按照gap分組，組內(nèi)的插入排序
    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) {
                swap(arr,j,j - gap);
            }
        }
    }

??6. 歸并排序

歸并排序的核心思想還是蠻簡(jiǎn)單的。如果要排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。歸并排序使用的就是分治思想。分治，顧名思義，就是分而治之，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決。小的子問(wèn)題解決了，大問(wèn)題也就解決了。

6.1 描述

• 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
• 對(duì)這兩個(gè)子序列分別采用歸并排序；
• 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

6.2 動(dòng)圖

?6.3 代碼

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

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

    private static void merge(int[] arr, int l, int mid, int r) {
//        本身就是插入排序
        // 創(chuàng)建一個(gè)大小為r - l + 1的與原數(shù)組長(zhǎng)度一樣的臨時(shí)數(shù)組aux
        int[] aux = new int[r - l + 1];
//        arraycopy:原數(shù)組，原數(shù)組開(kāi)始copy的第一個(gè)下標(biāo)，目標(biāo)數(shù)組，目標(biāo)數(shù)組copy的第一個(gè)下標(biāo)，copy的長(zhǎng)度
        System.arraycopy(arr,l,aux,0,r - l + 1);
        // 兩個(gè)子數(shù)組的開(kāi)始索引
        int i = l,j = mid + 1;
        // k表示當(dāng)前原數(shù)組合并到哪個(gè)位置
//        時(shí)間復(fù)雜度O(n)
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 子數(shù)組1全部拷貝完畢，將子數(shù)組2的所有內(nèi)容寫(xiě)回arr
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 子數(shù)組2全部拷貝完畢，將子數(shù)組1的剩余內(nèi)容寫(xiě)回arr
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 穩(wěn)定性 <=
                arr[k] = aux[i - l];
                i ++;
            }else {
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }

??優(yōu)化代碼（優(yōu)化部分）

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

    // 在arr[l...r]進(jìn)行歸并排序
    private static void mergeSortInternal(int[] arr, int l, int r) {
        // base case
//        if(l > r){
//            return;
//        }
        // 優(yōu)化2.小數(shù)組(64個(gè)元素以內(nèi))直接使用插入排序
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        // mid = (l + r) / 2
        int mid = l + ((r - l) >> 1);
        // 先將原數(shù)組一分為二，在子數(shù)組上先進(jìn)行歸并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        // 此時(shí)兩個(gè)子數(shù)組已經(jīng)有序,將這兩個(gè)子數(shù)組合并為原數(shù)組
//        merge(arr,l,mid,r);
        if (arr[mid] > arr[mid + 1]) {
            // 優(yōu)化1.只有子數(shù)組1和子數(shù)組2存在元素的亂序才需要合并
            merge(arr,l,mid,r);
        }
    }
    // 在數(shù)組arr[l..r]上進(jìn)行插入排序
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

??7.堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

7.1 算法描述

• 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；
• 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
• 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成。

7.2 動(dòng)圖

?7.3 代碼

//    原地堆排序   升序最大堆
//    1.堆化,不斷將堆頂和無(wú)序數(shù)組最后一個(gè)交換
//    2.再siftDown
//    3.重復(fù)12
    public static void heapSort(int[] arr){
//        堆化
        for (int i = (arr.length - 2)/2; i >= 0; i--) {
            siftDown(arr,i, arr.length);
        }
        // 不斷的將當(dāng)前無(wú)序數(shù)組的最大值(堆頂) 和 最后一個(gè)元素進(jìn)行交換~
        for (int i = arr.length - 1; i >= 0 ; i--) {
            // 將堆頂(最大值) 和 i交換
            swap(arr,0,i);
            // 進(jìn)行元素的下沉操作
            siftDown(arr,0,i);
        }
    }
//    元素下沉
    private static void siftDown(int[] arr, int i, int length) {
        int j =  2 * i + 1;
        while (j < length){
            if(j + 1 < length && arr[j] < arr[j + 1]){
                j = j + 1;
            }
            if(arr[j] <= arr[i]){
//                下沉結(jié)束
                break;
            }else {
                swap(arr,i,j);
                i = j;
                j =  2 * i + 1;//更新孩子節(jié)點(diǎn)
            }
        }
    }

??8. 快速排序（挖坑法）

快排的思想是這樣的：如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到 r 之間的任意一個(gè)數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）。

我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過(guò)這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的。

8.1 描述

• 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）；
• 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；
• 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

8.2 動(dòng)圖

8.3 代碼

（1）遞歸版

//    挖坑法快速排序 快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
//    時(shí)間復(fù)雜度：O(N*logN)
    public static void quickSortHole(int[] arr){
        quickSortHoleInternal(arr,0, arr.length - 1);
    }

//     默認(rèn)挖坑法快速排序
    private static void quickSortHoleInternal(int[] arr,int left,int right){
        // base case
        if(left > right){
            return;
        }

        int p = partitionByHole(arr,left,right);
        // 繼續(xù)在兩個(gè)子區(qū)間上進(jìn)行快速排序
        quickSortHoleInternal(arr,left,p - 1);
        quickSortHoleInternal(arr,p + 1,right);
    }

//    時(shí)間復(fù)雜度n
    private static int partitionByHole(int[] arr, int left, int right) {
//        漸進(jìn)有序（極端情況完全有序）的數(shù)組，快速排序性能會(huì)退化為O(n*n)
//        原因：每次取最左邊的值，假設(shè)這個(gè)值是最小的，那么j要一直減到left（二叉樹(shù)會(huì)變成單支樹(shù)）
//        解決：①三數(shù)取中法(課本中的方法)，②隨機(jī)數(shù)法
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int pivot = arr[left];
        int i = left,j = right;
        while (i < j) {
            // 先讓j從后向前掃描碰到第一個(gè) < pivot的元素終止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            // 再讓i從前向后掃描碰到第一個(gè) > pivot的元素終止,
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        // 回填分區(qū)點(diǎn)
        arr[j] = pivot;
        return j;
    }

（2）遞歸版優(yōu)化

    private static void qiuckSortHoleInternal(int[] arr,int left,int right){
        // base case
//        if(left > right){
//            return;
//        }
        // 優(yōu)化1.小數(shù)組使用插入排序
        if (right - left <= 64) {
            insertionSort(arr,left,right);
            return;
        }
        int p = partitionByHole(arr,left,right);
        // 繼續(xù)在兩個(gè)子區(qū)間上進(jìn)行快速排序
        qiuckSortHoleInternal(arr,left,p - 1);
        qiuckSortHoleInternal(arr,p + 1,right);
    }

（3）非遞歸版

//    非遞歸挖坑法快速排序
    public static void quickSortNonRecursion(int[] arr){
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length - 1);
        stack.push(0);
        while (!stack.isEmpty()){
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 當(dāng)前這個(gè)子數(shù)組已經(jīng)處理完畢
                continue;
            }
            int p = partitionByHole(arr,l,r);
            // 先將右半?yún)^(qū)間壓入棧中
            stack.push(r);
            stack.push(p + 1);
            // 繼續(xù)處理左半?yún)^(qū)間
            stack.push(p - 1);
            stack.push(l);
        }
    }

??9. 快速排序（二路快排）

代碼?

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

    private static void quickSortInternal(int[] arr, int left, int right) {
        if (right - left <= 64) {
            insertionSort(arr,left,right);
            return;
        }
        int p = partition(arr,left,right);
        quickSortInternal(arr,left,p - 1);
        quickSortInternal(arr,p + 1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int v = arr[left];
        // arr[l + 1..j] < v
        int j = left;
        // arr[j + 1..i) >= v
        for (int i = left + 1; i < right; i++) {
            if(arr[i] < v){
                swap(arr,i,j + 1);
                j ++;
            }
        }
        swap(arr,left,j);
        return j;
    }

??10.?三路快排

    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr,0,arr.length - 1);
    }
// 三路快排

    private static void quickSortInternal3(int[] arr, int l, int r) {
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1...lt] < v
        int lt = l;
        // arr[gt...r] > v
        int gt = r + 1;
        // arr[lt + 1..i) == v,i指向當(dāng)前要處理的元素
        int i = l + 1;
        // 終止條件i和gt重合
        while (i < gt) {
            if (arr[i] < v) {
                swap(arr,lt + 1,i);
                lt ++;
                i ++;
            }else if (arr[i] > v) {
                // 此時(shí)不需要i++，因?yàn)間t-1這個(gè)未處理的元素?fù)Q到i位置
                swap(arr,gt - 1,i);
                gt --;
            }else {
                // 此處arr[i] == v
                i ++;
            }
        }
        swap(arr,l,lt);
        // 交換后arr[l..lt - 1] < v ; arr[gt..r] >v
        quickSortInternal3(arr,l,lt - 1);
        quickSortInternal3(arr,gt,r);
    }

??11. 測(cè)試排序后的數(shù)組是否正確排序?

//    測(cè)試是否排序正確
    public static boolean isSorted(int[] data){
        for (int i = 0; i < data.length - 1; i++) {
            if(data[i] > data[i + 1]){
//                反例
                return false;
            }
        }
        return true;
    }

??12. 全部代碼

（1）生成數(shù)組（漸進(jìn)有序，亂序）

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class ArrayUtil {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();

    // 生成一個(gè)大小為n的近乎有序的數(shù)組
    // 數(shù)組的有序與否取決于元素的交互次數(shù)
    public static int[] generateSortedArray(int n,int swapTimes){
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        for (int i = 0; i < swapTimes; i++) {
            int x = random.nextInt(0,n);
            int y = random.nextInt(0,n);
            swap(arr,x,y);
        }
        return arr;
    }

    private static void swap(int[] arr,int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

    // 生成一個(gè)大小為n的隨機(jī)數(shù)數(shù)組
    // 隨機(jī)數(shù)的取值范圍為[l..r)
    public static int[] generateRandomArray(int n,int l,int r){
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = random.nextInt(l,r);
        }
        return arr;
    }

    // 深拷貝數(shù)組
    public static int[] arrCopy(int[] arr) {
        return Arrays.copyOf(arr,arr.length);
    }

}

（2）排序代碼

import util.ArrayUtil;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;


public class SevenSort {
    private static ThreadLocalRandom random = ThreadLocalRandom.current();
    private static int[] arr6;

    public static void main(String[] args) throws Exception{

        int n = 10_0000;
//        漸進(jìn)有序的數(shù)組
//        int[] arr = ArrayUtil.generateSortedArray(n,10);

//        無(wú)序數(shù)組
        int[] arr = ArrayUtil.generateRandomArray(n,0,Integer.MAX_VALUE);

        int[] arr1 = ArrayUtil.arrCopy(arr);
        int[] arr2 = ArrayUtil.arrCopy(arr);
        int[] arr3 = ArrayUtil.arrCopy(arr);
        int[] arr4 = ArrayUtil.arrCopy(arr);
        int[] arr5 = ArrayUtil.arrCopy(arr);
        int[] arr6 = ArrayUtil.arrCopy(arr);
        int[] arr7 = ArrayUtil.arrCopy(arr);
        int[] arr8 = ArrayUtil.arrCopy(arr);


        // --------------------------------
        long start = System.nanoTime();
        qiuckSort(arr8);
        long end = System.nanoTime();
        if (isSorted(arr8)) {
            System.out.println("快速排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }
        //--------------------------------
        start = System.nanoTime();
        qiuckSortNonRecursion(arr7);
        end = System.nanoTime();
        if (isSorted(arr7)) {
            System.out.println("快速排序(挖坑法，非遞歸法)共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }
        //---------------------------------
        start = System.nanoTime();
        qiuckSortHole(arr6);
        end = System.nanoTime();
        if (isSorted(arr6)) {
            System.out.println("快速排序(挖坑法，遞歸法)共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

        //----------------------------------
        start = System.nanoTime();
        mergeSort(arr5);
        end = System.nanoTime();
        if (isSorted(arr5)) {
            System.out.println("歸并排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

        //---------------------------------
        start = System.nanoTime();
        shellSort(arr4);
        end = System.nanoTime();
        if (isSorted(arr4)) {
            System.out.println("希爾排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

        // ------------------------------
        start = System.nanoTime();
        insertionSort(arr3);
        end = System.nanoTime();
        if (isSorted(arr3)) {
            System.out.println("插入排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

        // -------------------------------
        start = System.nanoTime();
        selectionSort(arr2);
        end = System.nanoTime();
        if (isSorted(arr2)) {
            System.out.println("選擇排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

        // ------------------------------
        start = System.nanoTime();
        bubbleSort(arr1);
        end = System.nanoTime();
        if (isSorted(arr1)) {
            System.out.println("冒泡排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

        // ------------------------------
        start = System.nanoTime();
        heapSort(arr);
        end = System.nanoTime();
        if (isSorted(arr)) {
            System.out.println("堆排序共耗時(shí) : " + (end - start) / 1000000.0 + "ms");
        }

    }

//    測(cè)試是否排序正確
    public static boolean isSorted(int[] data){
        for (int i = 0; i < data.length - 1; i++) {
            if(data[i] > data[i + 1]){
//                反例
                return false;
            }
        }
        return true;
    }

    //    交換兩個(gè)值
    private static void swap(int[] arr,int j, int i) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr,0,arr.length - 1);
    }
// 三路快排

    private static void quickSortInternal3(int[] arr, int l, int r) {
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1...lt] < v
        int lt = l;
        // arr[gt...r] > v
        int gt = r + 1;
        // arr[lt + 1..i) == v,i指向當(dāng)前要處理的元素
        int i = l + 1;
        // 終止條件i和gt重合
        while (i < gt) {
            if (arr[i] < v) {
                swap(arr,lt + 1,i);
                lt ++;
                i ++;
            }else if (arr[i] > v) {
                // 此時(shí)不需要i++，因?yàn)間t-1這個(gè)未處理的元素?fù)Q到i位置
                swap(arr,gt - 1,i);
                gt --;
            }else {
                // 此處arr[i] == v
                i ++;
            }
        }
        swap(arr,l,lt);
        // 交換后arr[l..lt - 1] < v ; arr[gt..r] >v
        quickSortInternal3(arr,l,lt - 1);
        quickSortInternal3(arr,gt,r);
    }

//    算法4的分區(qū)快排（二路快排）
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length - 1);
    }

    private static void quickSortInternal(int[] arr, int left, int right) {
        if (right - left <= 64) {
            insertionSort(arr,left,right);
            return;
        }
        int p = partition(arr,left,right);
        quickSortInternal(arr,left,p - 1);
        quickSortInternal(arr,p + 1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int v = arr[left];
        // arr[l + 1..j] < v
        int j = left;
        // arr[j + 1..i) >= v
        for (int i = left + 1; i < right; i++) {
            if(arr[i] < v){
                swap(arr,i,j + 1);
                j ++;
            }
        }
        swap(arr,left,j);
        return j;
    }


    //    挖坑法快速排序 快速排序整體的綜合性能和使用場(chǎng)景都是比較好的，所以才敢叫快速排序
//    時(shí)間復(fù)雜度：O(N*logN)
    public static void quickSortHole(int[] arr){
        quickSortHoleInternal(arr,0, arr.length - 1);
    }

//     默認(rèn)挖坑法快速排序
    private static void quickSortHoleInternal(int[] arr,int left,int right){
        // base case
//        if(left > right){
//            return;
//        }
        // 優(yōu)化1.小數(shù)組使用插入排序
        if (right - left <= 64) {
            insertionSort(arr,left,right);
            return;
        }
        int p = partitionByHole(arr,left,right);
        // 繼續(xù)在兩個(gè)子區(qū)間上進(jìn)行快速排序
        quickSortHoleInternal(arr,left,p - 1);
        quickSortHoleInternal(arr,p + 1,right);
    }
//    非遞歸挖坑法快速排序
    public static void quickSortNonRecursion(int[] arr){
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length - 1);
        stack.push(0);
        while (!stack.isEmpty()){
            int l = stack.pop();
            int r = stack.pop();
            if (l >= r) {
                // 當(dāng)前這個(gè)子數(shù)組已經(jīng)處理完畢
                continue;
            }
            int p = partitionByHole(arr,l,r);
            // 先將右半?yún)^(qū)間壓入棧中
            stack.push(r);
            stack.push(p + 1);
            // 繼續(xù)處理左半?yún)^(qū)間
            stack.push(p - 1);
            stack.push(l);
        }
    }

//    時(shí)間復(fù)雜度n
    private static int partitionByHole(int[] arr, int left, int right) {
//        漸進(jìn)有序（極端情況完全有序）的數(shù)組，快速排序性能會(huì)退化為O(n*n)
//        原因：每次取最左邊的值，假設(shè)這個(gè)值是最小的，那么j要一直減到left（二叉樹(shù)會(huì)變成單支樹(shù)）
//        解決：①三數(shù)取中法(課本中的方法)，②隨機(jī)數(shù)法
        int randomIndex = random.nextInt(left,right);
        swap(arr,left,randomIndex);
        int pivot = arr[left];
        int i = left,j = right;
        while (i < j) {
            // 先讓j從后向前掃描碰到第一個(gè) < pivot的元素終止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            arr[i] = arr[j];
            // 再讓i從前向后掃描碰到第一個(gè) > pivot的元素終止,
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            arr[j] = arr[i];
        }
        // 回填分區(qū)點(diǎn)
        arr[j] = pivot;
        return j;
    }


//    歸并排序是一種穩(wěn)定的排序方法。
//    和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，
//    因?yàn)槭冀K都是O(n * logn）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。
//    歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤(pán)中的外排序問(wèn)題。
//    空間復(fù)雜度：O(N)
//    穩(wěn)定性：穩(wěn)定
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length - 1);
    }

    // 在arr[l...r]進(jìn)行歸并排序
    private static void mergeSortInternal(int[] arr, int l, int r) {
        // base case
//        if(l > r){
//            return;
//        }
        // 優(yōu)化2.小數(shù)組(64個(gè)元素以內(nèi))直接使用插入排序
        if (r - l <= 64) {
            insertionSort(arr,l,r);
            return;
        }
        // mid = (l + r) / 2
        int mid = l + ((r - l) >> 1);
        // 先將原數(shù)組一分為二，在子數(shù)組上先進(jìn)行歸并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid + 1,r);
        // 此時(shí)兩個(gè)子數(shù)組已經(jīng)有序,將這兩個(gè)子數(shù)組合并為原數(shù)組
//        merge(arr,l,mid,r);
        if (arr[mid] > arr[mid + 1]) {
            // 優(yōu)化1.只有子數(shù)組1和子數(shù)組2存在元素的亂序才需要合并
            merge(arr,l,mid,r);
        }
    }
    // 在數(shù)組arr[l..r]上進(jìn)行插入排序
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    private static void merge(int[] arr, int l, int mid, int r) {
//        本身就是插入排序
        // 創(chuàng)建一個(gè)大小為r - l + 1的與原數(shù)組長(zhǎng)度一樣的臨時(shí)數(shù)組aux
        int[] aux = new int[r - l + 1];
//        arraycopy:原數(shù)組，原數(shù)組開(kāi)始copy的第一個(gè)下標(biāo)，目標(biāo)數(shù)組，目標(biāo)數(shù)組copy的第一個(gè)下標(biāo)，copy的長(zhǎng)度
        System.arraycopy(arr,l,aux,0,r - l + 1);
        // 兩個(gè)子數(shù)組的開(kāi)始索引
        int i = l,j = mid + 1;
        // k表示當(dāng)前原數(shù)組合并到哪個(gè)位置
//        時(shí)間復(fù)雜度O(n)
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 子數(shù)組1全部拷貝完畢，將子數(shù)組2的所有內(nèi)容寫(xiě)回arr
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 子數(shù)組2全部拷貝完畢，將子數(shù)組1的剩余內(nèi)容寫(xiě)回arr
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 穩(wěn)定性 <=
                arr[k] = aux[i - l];
                i ++;
            }else {
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }


    //    希爾排序（插入排序的優(yōu)化），不穩(wěn)定
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            // 先按照gap分組，組內(nèi)使用插入排序
            insertionSortByGap(arr,gap);
            gap = gap >> 1;
        }
        // 當(dāng)gap == 1時(shí)，整個(gè)數(shù)組接近于有序，此時(shí)來(lái)一個(gè)插入排序
        insertionSortByGap(arr,1);
    }

    // 按照gap分組，組內(nèi)的插入排序
    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) {
                swap(arr,j,j - gap);
            }
        }
    }


    //    插入排序，穩(wěn)定！近乎有序的集合上性能非常好，經(jīng)常作為其他高階排序的優(yōu)化手段
    public static void insertionSort(int[] arr){
        // 無(wú)序區(qū)間[i...n)
        // 有序區(qū)間[0...i)
        // i指向當(dāng)前無(wú)序區(qū)間的第一個(gè)元素
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j - 1 >= 0 && arr[j] < arr[j - 1]; j--) {
//                簡(jiǎn)化寫(xiě)法
                swap(arr,j,j - 1);
//                j - 1 要保證不為負(fù)數(shù) 因此j > 0，而不是 j >= 0
//                if(arr[j] < arr[j - 1]){
//                    swap(arr,j,j - 1);
//                }
            }
        }
    }


    //    選擇排序：對(duì)數(shù)據(jù)不敏感，無(wú)論是否有序，都會(huì)進(jìn)行比較
    public static void selectionSort(int[] arr){
        // 起始狀態(tài) : 有序區(qū)間[0..i)
        // 無(wú)序區(qū)間[i....n)
        for (int i = 0; i < arr.length - 1; i++) {
            // min指向的當(dāng)前無(wú)序區(qū)間的最小值,min是下標(biāo)
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            // 此時(shí)min一定指向無(wú)序區(qū)間最小值下標(biāo)，換到無(wú)序區(qū)間的最開(kāi)始位置
            swap(arr,i,min);
        }
    }


    //    冒泡排序
    public static void bubbleSort(int[] arr){
        if(arr.length < 2){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwap = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
//                j + 1保證索引不越界，因此，j < arr.length - i - 1
                if(arr[j] > arr[j + 1]){
                    isSwap = true;
                    swap(arr,j,j + 1);
                }
            }
            if(!isSwap){
                break;
            }
        }
    }


//    原地堆排序   升序最大堆
//    1.堆化,不斷將堆頂和無(wú)序數(shù)組最后一個(gè)交換
//    2.再siftDown
//    3.重復(fù)12
    public static void heapSort(int[] arr){
//        堆化
        for (int i = (arr.length - 2)/2; i >= 0; i--) {
            siftDown(arr,i, arr.length);
        }
        // 不斷的將當(dāng)前無(wú)序數(shù)組的最大值(堆頂) 和 最后一個(gè)元素進(jìn)行交換~
        for (int i = arr.length - 1; i >= 0 ; i--) {
            // 將堆頂(最大值) 和 i交換
            swap(arr,0,i);
            // 進(jìn)行元素的下沉操作
            siftDown(arr,0,i);
        }
    }
//    元素下沉
    private static void siftDown(int[] arr, int i, int length) {
        int j =  2 * i + 1;
        while (j < length){
            if(j + 1 < length && arr[j] < arr[j + 1]){
                j = j + 1;
            }
            if(arr[j] <= arr[i]){
//                下沉結(jié)束
                break;
            }else {
                swap(arr,i,j);
                i = j;
                j =  2 * i + 1;//更新孩子節(jié)點(diǎn)
            }
        }
    }

}

（3）測(cè)試結(jié)果?

?

參考文章：https://www.cnblogs.com/onepixel/p/7674659.html文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-422937.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】用Java實(shí)現(xiàn)七大排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！