常見的排序算法,一篇就夠了

更新時間：2021年07月09日 17:07:18 作者：程序dunk

這篇文章主要介紹了一些常用排序算法整理，插入排序算法、直接插入排序、希爾排序、選擇排序、冒泡排序等排序,需要的朋友可以參考下

排序算法介紹

排序也稱排序算法(Sort Algorithm)，排序是將一組數(shù)據(jù)，依指定的順序進行排列的過程。

排序的分類：

1) 內(nèi)部排序:

指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲器中進行排序。

2) 外部排序法：

數(shù)據(jù)量過大，無法全部加載到內(nèi)存中，需要借助外部存儲進行排序。

常見的排序的排序算法分類如圖：

冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）,依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。

原始數(shù)組：3, 9, -1, 10, 20

第一趟排序

(1) 3, 9, -1, 10, 20 // 如果相鄰的元素逆序就交換

(2) 3, -1, 9, 10, 20

(3) 3, -1, 9, 10, 20

(4) 3, -1, 9, 10, 20

第二趟排序

(1) -1, 3, 9, 10, 20 //交換

(2) -1, 3, 9, 10, 20

(3) -1, 3, 9, 10, 20

第三趟排序

(1) -1, 3, 9, 10, 20

(2) -1, 3, 9, 10, 20

第四趟排序

(1) -1, 3, 9, 10, 20

小結(jié)冒泡排序規(guī)則

(1) 一共進行數(shù)組的大小-1 次大的循環(huán)

(2)每一趟排序的次數(shù)在逐漸的減少

(3) 如果我們發(fā)現(xiàn)在某趟排序中，沒有發(fā)生一次交換，可以提前結(jié)束冒泡排序。這個就是優(yōu)化

因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設(shè)置一個標志flag判斷元素是否進行過交換。從而減少不必要的比較。(這

里說的優(yōu)化，可以在冒泡排序?qū)懞煤?，在進行)

代碼實現(xiàn)

public static void bubbleSort(int[] arr){
        int temp = 0;
        //標識變量，表示是否進行過交換
        boolean flag = false;
        //時間復雜度O(n^2)
        for (int i = 0; i < arr.length - 1; i++) { //一共要排序幾次
            for (int j = 0; j < arr.length - 1 - i; j++) {//每次排序需要比較的次數(shù)
                if (arr[j] > arr[j + 1]){
                    flag = true;
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
            if (flag){//出現(xiàn)過交換，重置flag
                flag = false;
            }else//在上一趟排序中，一次交換也沒有發(fā)生過
                break;
        }
    }

選擇排序

選擇式排序也屬于內(nèi)部排序法，是從欲排序的數(shù)據(jù)中，按指定的規(guī)則選出某一元素，再依規(guī)定交換位置后達到排序的目的。

選擇排序思想

選擇排序（select sorting）也是一種簡單的排序方法。它的基本思想是：第一次從arr[0]~arr[n-1]中選取最小值，與arr[0]交換，第二次從arr[1]~arr[n-1]中選取最小值，與arr[1]交換，第三次arr[2]~arr[n-1]中選取最小值，與arr[2]交換，…，第i次從arr[i-1]~arr[n-1]中選取最小值，與arr[i-1]交換，…, 第n-1次從arr[n-2]~arr[n-1]中選取最小值，與arr[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列

原始的數(shù)組： 101, 34, 119, 1

第一輪排序 : 1, 34, 119, 101

第二輪排序 : 1, 34, 119, 101

第三輪排序 : 1, 34, 101, 119

小結(jié)選擇排序的規(guī)則

1. 選擇排序一共有數(shù)組大小 - 1 輪排序

2. 每1輪排序，又是一個循環(huán), 循環(huán)的規(guī)則(代碼)

先假定當前這個數(shù)是最小數(shù)
然后和后面的每個數(shù)進行比較，如果發(fā)現(xiàn)有比當前數(shù)更小的數(shù)，就重新確定最小數(shù)，并得到下標
當遍歷到數(shù)組的最后時，就得到本輪最小數(shù)和下標 2.4 交換 [代碼中再繼續(xù)說 ]

代碼實現(xiàn)

public static void selectSort(int[]arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]){
                    minIndex = j;
                    min = arr[j];
                }
            }
            //將最小值放在arr[i],即交換
            if (minIndex != i){//如果最小值的下標改變了則交換
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

插入排序

插入式排序?qū)儆趦?nèi)部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當位置，以達到排序的目的。

插入排序思想

插入排序（Insertion Sorting）的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。

原始的數(shù)組： (101), 34, 119, 1

橘色箭頭表示待插入的元素下標

綠色箭頭表示待插入元素

第一次插入排序

第二次插入排序

第三次插入排序

代碼實現(xiàn)

public static void insertSort(int[] arr){
        int insertIndex = 0;
        int insertValue = 0;
        for (int i = 1; i < arr.length; i++) {
            insertIndex = i - 1;
            insertValue = arr[i];
            while(insertIndex >= 0 && arr[insertIndex] > insertValue){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //優(yōu)化是否需要賦值
            if (insertIndex + 1 != i){
                arr[insertIndex + 1] = insertValue;
            }
        }
    }

分析簡單插入排序存在的問題

我們看簡單的插入排序可能存在的問題.

數(shù)組 arr = {2,3,4,5,6,1} 這時需要插入的數(shù) 1(最小), 這樣的過程是：

{2,3,4,5,6,6}

{2,3,4,5,5,6}

{2,3,4,4,5,6}

{2,3,3,4,5,6}

{2,2,3,4,5,6}

{1,2,3,4,5,6}

結(jié)論: 當需要插入的數(shù)是較小的數(shù)時，后移的次數(shù)明顯增多，對效率有影響.

希爾排序

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進之后的一個更高效的版本，也稱為縮小增量排序。

希爾排序基本思想

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止

為了方便大家理解

希爾排序時，對有序序列在插入時先采用交換法(冒泡法)

public static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]){//這里采用交換法
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

希爾排序時，對有序序列在插入時采用移位法（真正的希爾排序）(插入法)

public static void shellSort(int[]arr){
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i - gap;
                int insertValue = arr[insertIndex + gap];
                while(insertIndex >= 0 && insertValue < arr[insertIndex]){
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                if (insertIndex != (i - gap)){
                    arr[insertIndex + gap] = insertValue;
                }
            }
        }
    }

快速排序

快速排序（Quicksort）是對冒泡排序的一種改進?；舅枷胧牵和ㄟ^一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列

代碼實現(xiàn)

 public static void quickSort(int[] arr,int left,int right){
        int r = right;
        int l = left;
        int temp = 0;
        int pivot = arr[(right + left) / 2];
        while(l < r){
            while(arr[l] < pivot){
                l++;
            }
            while(arr[r] > pivot){
                r--;
            }
            if(l == r)
                break;
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;
            if (arr[l] == pivot){
                r--;
            }
            if (arr[r] == pivot){
                l++;
            }
        }
        if (l == r){
            l += 1;
            r -= 1;
        }
        //向左遞歸
        if(left < r){
            quickSort(arr,left,r);
        }
        //向右遞歸
        if(right > l){
            quickSort(arr,l,right);
        }
    }

歸并排序

歸并排序（MERGE-SORT）是利用歸并的思想實現(xiàn)的排序方法，該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。

說明: 可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現(xiàn)（也可采用迭代的方式去實現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過程。

再來看看治階段，我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現(xiàn)步驟

代碼實現(xiàn)

治

/**
     *
     * @param arr   排序的原始數(shù)組
     * @param left  左邊有序序列的初始索引
     * @param mid   中間索引
     * @param right 右邊索引
     * @param temp  中轉(zhuǎn)數(shù)組
     */
    public static void merge(int[] arr,int left,int mid,int right,int[]temp){
        //System.out.println("*****");
        int i = left;
        int j = mid + 1;
        int t = 0;
        /*
        (一)
        先把兩邊有序的數(shù)據(jù)按照規(guī)則填充到temp數(shù)組
        指導左右兩邊的有序序列，有一邊處理完畢
        */
        while(i <= mid && j <= right){
            temp[t++] = arr[i] > arr[j] ? arr[j++] : arr[i++];
        }
        /*
        (二)
        把所有剩余數(shù)據(jù)的一邊一次全部填充到temp
         */
        while(i <= mid){
            temp[t++] = arr[i++];
        }
        while (j <= right){
            temp[t++] = arr[j++];
        }
        /*
        (三)
        將temp數(shù)組的元素拷貝到arr
         */
        t = 0;
        int tempLeft = left;
        //System.out.println("tempLeft = " + tempLeft + "right = " + right);
        while(tempLeft <= right){
            arr[tempLeft++] = temp[t++];
        }
    }

分（遞歸）

public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid + 1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

基數(shù)排序（桶排序）

1、基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是通過鍵值的各個位的值，將要排序的元素分配至某些“桶”中，達到排序的作用

2、基數(shù)排序法是屬于穩(wěn)定性的排序，基數(shù)排序法的是效率高的穩(wěn)定性排序法

3、基數(shù)排序(Radix Sort)是桶排序的擴展

4、基數(shù)排序是1887年赫爾曼·何樂禮發(fā)明的。它是這樣實現(xiàn)的：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。

基數(shù)排序的基本思想

將所有待比較數(shù)值統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。

這樣說明，比較難理解，下面我們看一個圖文解釋，理解基數(shù)排序的步驟

數(shù)組的初始狀態(tài) arr = {53, 3, 542, 748, 14, 214}

第1輪排序:

(1) 將每個元素的個位數(shù)取出，然后看這個數(shù)應該放在哪個對應的桶(一個一維數(shù)組)

(2) 按照這個桶的順序(一維數(shù)組的下標依次取出數(shù)據(jù)，放入原來數(shù)組)

數(shù)組的第1輪排序 arr = {542, 53, 3, 14, 214, 748}

第2輪排序:

(1) 將每個元素的十位數(shù)取出，然后看這個數(shù)應該放在哪個對應的桶(一個一維數(shù)組)

(2) 按照這個桶的順序(一維數(shù)組的下標依次取出數(shù)據(jù)，放入原來數(shù)組)

數(shù)組的第2輪排序 arr = {3, 14, 214, 542, 748, 53}

第3輪排序:

(1) 將每個元素百位數(shù)取出，然后看這個數(shù)應該放在哪個對應的桶(一個一維數(shù)組)

(2) 按照這個桶的順序(一維數(shù)組的下標依次取出數(shù)據(jù)，放入原來數(shù)組)

數(shù)組的第3輪排序 arr = {3, 14, 53, 214, 542, 748}

以上就是基數(shù)排序的實現(xiàn)過程

代碼實現(xiàn)

代碼說明

獲取數(shù)組最大元素的位數(shù)

使用二維數(shù)組bucket[10][arr.length]模擬桶

使用bucketElementCounts[10]模擬每個桶的指針

 public static void redixSort(int[]arr){
        //獲取數(shù)組中最大元素的位數(shù)
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(max < arr[i])
                max = arr[i];
        }
        int maxLength = (max + "").length();
        //定義一個二維數(shù)組模擬桶
        int [][] bucket = new int[10][arr.length];
        //為了記錄每個桶中的元素個數(shù)定義一個一維數(shù)組
        int [] bucketElementCounts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++,n *= 10) {
            //入桶
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j] / n %10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            //出桶
            for (int j = 0; j < bucketElementCounts.length; j++) {
                if(bucketElementCounts[j] != 0){
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        arr[index++] = bucket[j][k];
                    }
                }
                //取出元素后，需要將bucketElementCount中的元素清零
                bucketElementCounts[j] = 0;
            }
            //System.out.println("第" + (i + 1) + "次排序后的數(shù)組" + Arrays.toString(arr));
        }
    }

排序算法的速度測試

下面我創(chuàng)建了一個長度分別為80000的隨機數(shù)組進行測試

硬件:CPU8代i7

public static void main(String[] args) {
        System.out.println("測試排序算法的時間");
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }
        Long startTime = System.currentTimeMillis();
        redixSort(arr);
        Long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime + "ms");
    }