演算法 經典的八大排序演算法詳解和代碼實作

排序演算法的介紹

排序也稱排序演算法，排序時將一組資料，依指定的順序進行排列的程序

排序的分類

內部排序，指將需要處理的所有資料都加載到內部記憶體中進行排序

外部排序，資料量很大，無法全部加載到記憶體中，需要借助外部存盤進行排序，記憶體和外存結合

演算法的時間復雜度

時間頻度

時間頻度：一個演算法花費的時間與演算法中陳述句的執行次數成正比，哪個演算法中陳述句執行次數多，它花費時間就多，一個演算法中的陳述句執行次數稱為陳述句頻度或時間頻度，即為T(n).

示例

比如計算1-100所有數字之和，我們設計兩種演算法：

1.使用for回圈計算

int total=0;
int end=100;
for(int i=1;i <=end;i++){
	total+=i;
}

使用for回圈的時間頻度：T(n)=n+1

2.直接計算

total=(1+end)*end/2;

直接計算的時間頻度：T(n)=1

圖表理解時間復雜度的特點

1.常數項可以忽略

2.低次項可以忽略

3.系數可以忽略

隨著n增大的結果如下圖：

結論：

2n+20和2n隨著n變大，執行曲線無限接近，20可以忽略

3n+10和3n隨著n變大，執行曲線無限接近，10可以忽略

結論：

算式隨著n變大，同次方項執行曲線無限接近，低次項可以忽略

結論：

隨著n變大，同次方項曲線近似重合，系數可以忽略

時間復雜度

1）一般情況下，演算法中的基本操作陳述句的重復執行次數是問題規模n的某個函式，用T(n)表示，若有個輔助函式f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函式，記作T(n)=O(f(n)),稱O(f(n))為演算法的漸進時間復雜度，簡稱時間復雜度，

2）T(n)不同，但時間復雜度可能相同，如：T(n)=n^{2+7n+6與T(n)=3n}2+2n+2它們的T(n)不同，但是時間復雜度相同都為O(n^2)

3)計算時間復雜度的方法：

• 用常數1代替運行時間中的所有加法常熟
• 修改后的運行次數函式中，只保留最高階項
• 去除最高階項的系數

常見的時間復雜度

空間復雜度

空間復雜度該演算法所耗費的存盤空間

在做演算法分析時，主要討論的是時間復雜度，

排序演算法的時間復雜度

冒泡排序

基本思想

基本思想：通過對待排序序列從前向后，依次比較元素相鄰元素的值，若發現逆序則變換，使值較大的元素逐漸從前移向后部，就像水底的氣泡一樣逐漸向上冒；

圖解

小結：

• 一共進行陣列長度的減1次回圈
• 每一趟排序的次數在逐漸減少
• 如果相鄰的逆序就交換

代碼示例

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {11, 3, 17, 5, 9, 20,-1};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.println("程序展示：");
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }
}

結果展示

代碼優化

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {11, 3, 17, 5, 9, 20,21};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.println("程序展示：");
        boolean flag=false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag=true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        if (!flag) {//在一趟排序中，一次交換都沒有發生過
            break;
        }else{
            flag=false;
        }
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }
}

結果展示

選擇排序

基本思想

每次找到最大值（最小值），從最后一位（最前一位）進行交換，依次向前（向后）交換，得到一個從小到大排列的有序序列

圖解

結論：

• 選擇排序一共有陣列的長度減1輪排序
• 每一輪排序又是一個回圈
• 假定第一個數是最小數，然后和后面依次進行比較，從而確定最小數，并得到下標，然后進行交換

代碼實作

public class SelectSort {
    public static void main(String[] args) {
        int[] arr={1,4,2,76,34,12};
        System.out.println("原資料：");
        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

    //選擇排序
    public static void selectSort(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
                }
                if (minIndex!=i) {
                    arr[minIndex]=arr[i];
                    arr[i]=min;
            }
                System.out.println("第"+(i+1)+"輪后~~");
                System.out.println(Arrays.toString(arr));
        }
    }
}

結果展示

插入排序

基本思想

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

圖解

代碼實作

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {2, 4, 32, 12, 45, 2, 1, 4};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        System.out.println("排序程序：");
        insetSort(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

    public static void insetSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i];//假設是插入的數
            int index = i-1;//插入的數的前面一個數
            while (index >= 0 && value < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = value;
            System.out.println(Arrays.toString(arr));
        }
    }
}

結果展示

希爾排序

基本思想

希爾也是一種插入排序，它是簡單插入排序經過改進之后的一個更高效的版本，也稱為縮小增量排序

希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵字越來越多，當增量減至1時，整個檔案恰被分成一組，演算法并終止

圖解

在這里插入圖片描述

代碼實作

交換法：

public class ShellSort {
    public static void main(String[] args) {
        int[] arr={1,4,2,3,8,5,9,6,7};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));

    }
    private static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        //一共gap組
        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;
                    }
                }
            }
            System.out.println("希爾排序第"+(++count)+"輪");
            System.out.println(Arrays.toString(arr));
        }

    }
}

移位法：

  public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}

結果展示

1.交換法

2.移動法

快速排序

基本思想

快速排序是對冒泡排序的一種改進；通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有的資料都要小，然后再按此方法對者兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列

圖解

代碼實作

public class QuickSort {
    public static void main(String[] args) {
        int[] arr={1,5,3,-1,544,3,45,6,23,22,15};
        quickSort(arr,0,arr.length-1);
        System.out.println("arr"+ Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        int temp=0;
        int l=left;//左下標
        int r=right;//右下標
        int pivot=arr[(left+right)/2];//中軸值
        while (l < r) {
            while (arr[l] < pivot) {
                l+=1;
            }
            while (arr[r] > pivot) {
                r-=1;
            }
            if (l >= r) {
                break;
            }
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            if (arr[l]==pivot) {
                r-=1;
            }
            if (arr[r]==pivot) {
                l+=1;
            }
        }
        if(l==r){
            l+=1;
            r-=1;
        }
        //向左遞回
        if (left < r) {
            quickSort(arr,left,r);
        }
        //向右遞回
        if (right > l) {
            quickSort(arr,l,right);
        }
    }
}

結果展示

歸并排序

基本思想

本文的歸并排序我們采用遞回去實作（也可采用迭代的方式去實作），分階段可以理解位就是遞回拆分子序列的程序

圖解

代碼實作

public class MergeSort {
    public static void main(String[] args) {
        int[] arr={8,4,5,7,1,3,6,2};
        System.out.println("排序前："+Arrays.toString(arr));
        int temp[]=new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println("歸并排序后："+ Arrays.toString(arr));
    }
    //分+和方法
    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);
        }
    }
    /**
     *
     * @param arr 排序的原始陣列
     * @param left 左邊有序序列的初始索引
     * @param mid 中間索引
     * @param right 右邊索引
     * @param temp 做中轉的陣列
     */
    public static void merge(int[] arr,int left,int mid,int right ,int[] temp){
        int i= left;
        int j=mid+1;
        int t=0;//指向temp陣列的當前索引
        while(i<=mid && j<=right){
            if (arr[i]<=arr[j]) {
                temp[t]=arr[i];
                t+=1;
                i+=1;
            }else{
                temp[t]=arr[j];
                t+=1;
                j+=1;
            }
        }
        while (i <= mid) {
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while (j <= right) {
            temp[t]=arr[j];
              t+=1;
              j+=1;
        }
        t=0;
        int tempLeft=left;
        while (tempLeft <= right) {
            arr[tempLeft]=temp[t];
            t +=1;
            tempLeft+=1;
        }
    }

結果展示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-e47XKM5S-1640004020334)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211220192324138.png)]

基數排序

基本思想

基數排序屬于‘’分配式排序‘’，又稱‘’桶子法‘’或bin sort，它是通過鍵值的各個位的值，將要排序的元素分配至某些‘’桶‘’中，達到排序的作用

是桶排序的擴展，屬于穩定性的排序

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

圖解

代碼實作

public class RadixSort {
    public static void main(String[] args) {
        int arr[]={53,3,542,748,14,214};
        radixSort(arr);
    }
    public static void radixSort(int[] arr){
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max=arr[i];
            }
        }
        int maxLength=(max+"").length();
        int[][] bucket=new int[10][arr.length];
        int[] bucketElementCounts=new int[10];
        for(int j=0,n=1;j<maxLength;j++,n*=10) {
            for (int i = 0; i < arr.length; i++) {
                int digitOfElement = arr[i]/n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            for (int k = 0; k < bucket.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index] = bucket[k][l];
                    }
                }
                bucketElementCounts[k]=0;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}