java

幾大排序總結!圖解解析+程式碼例項(冒泡、選擇、插入、希爾、快排、歸併)

氣泡排序

氣泡排序是我們能想到的一個最簡單的排序方法,它的思想就是將一個數組內的數字和相鄰的進行比較,把比較大的放在靠後位置,當從頭到尾比較一遍,我們就可以拿到最大的那個資料了,這樣迴圈,每次排除最大的那個,就可以完成排序。
上圖:
在這裡插入圖片描述
程式碼實現:(寫法不唯一,可以自己簡化寫出)

public class BubbleSort {
    //冒泡,arr:需要排序的陣列,n:需要排序的陣列的長度
    public static void Bubble(int[] arr,int n){
        for (int i = 0; i < n-1; i++) {
            if(arr[i]>arr[i+1]){//如果前面的比後面的大,就交換位置
                int temp = arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
    }
    public static void bubbleSort(int[] arr){
        int n = arr.length;
        while (n>1){//迴圈找出最大的,直到剩下一個數
            Bubble(arr, n);
            n--;
        }
    }
    public static void main(String[] args) {
        int arr[] = {1,4,7,10,8,3,6};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

在這裡插入圖片描述

選擇排序

選擇排序的思想就是,我們把我們的需要排序的陣列看成一個已經排序好的陣列和未排序的陣列的組合,初始情況排序好的陣列沒有值,我們對未排序的陣列進行篩選,挑出最大的那個數,然後與未排序最後的那個數進行交換,這個最大的數就放進了已經排好序的陣列中了。
圖解
在這裡插入圖片描述
程式碼實現:

public class SelectSort {
      //arr是需要排序的陣列,n是需要排序的陣列長度
     //這個方法就是獲取當前需要排序的陣列中最大的值得下標
    public static int getMaxIndex(int[] arr, int n) {
        int max = arr[0];
        int index = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        return index;
    }
    public static void selectSort(int[] arr) {
        int n = arr.length - 1;
        
        while (n > 1) {
        //交換未排序的陣列中最大的值與最後一個數的位置
            int maxIndex = getMaxIndex(arr, n);
            int temp = arr[n];
            arr[n] = arr[maxIndex];
            arr[maxIndex] = temp;
            n--;//交換後,這個最大的數就已經在排好序的陣列中
        }
    }

    public static void main(String[] args) {
        int arr[] = {1, 4, 7, 10, 8, 3, 6};
        selectSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

在這裡插入圖片描述

插入排序

插入排序的思想就是我們把陣列看成一個排好序(初始可能只有一個數)和未排序的陣列的組合,我們在未排序的陣列中取出一個A,在已經排好序的陣列中找到arr[i],如若arr[i]>A,那麼我們就將他放在arr[i]和arr[i-1]這個位置。(如果沒有理解,參考圖片理解)
在這裡插入圖片描述
程式碼例項:

public class InsertSort {
    public static void insert(int[] arr, int n) {
        int key = arr[n];//記下當前需要排序的數
        int i = n;
        while (arr[i-1]>key){//在找到可以放的位置(小於key)之前,我們就把所有的數往後面”挪“一位
            arr[i]=arr[i-1];
            i--;
            if(i==0){//如果到開頭的位置還沒有出現小於的情況,那麼我們就應該將其放在開頭。
                break;
            }
        }
        arr[i]=key;
    }
    public static void insertSort(int arr[]){
        for (int i = 1; i < arr.length ; i++) {//預設從1開始,因為第一個數我們預設已經排好序
            insert(arr,i);
        }
    }
    public static void main(String[] args) {
        int arr[] = {1,4,7,10,8,3,6};
        insertSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

希爾排序

我們會了插入排序,不妨看看插入排序有哪些缺點?假設一串數字的前面很多都已經是有序的,只有最後的幾個是沒有排序的,比如:{2,3,4,5,6,7,8,9,1},我們可以看到,只需要把1放在開頭就可以,但是使用插入排序很不理想。
希爾排序的基本思想就是:我們把陣列按照一定增量分成組,每次比較組內的值大小進行插入排序,然後增量逐漸縮小,繼續排序,當我們的增量變為1的時候,所有的數就已經排好序(還是看圖解比較好理解),這樣的好處是,在分組的幾次排序後,我們就將一些較小的數放在了最前面,就不會出現上述例子的情況
在這裡插入圖片描述

程式碼實現:

public class ShellSort {
    //同樣是插入排序,但是每次排序的都是當前組內的成員
    //arr:需要排序的陣列,n:開始排序的位置,gap增量
    public static void shellInsert(int[] arr, int n, int gap) {
        int key = arr[n];//記下當前需要排序的數
        while ( n-gap>=0 && key < arr[n - gap]) {
            arr[n] = arr[n - gap];
            n -= gap;//尋找下一個組內成員
        }
        arr[n] = key;
    }

    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap >0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                shellInsert(arr,i,gap);
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int arr[] = {2,3,4,5,6,7,8,1};
        shellSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

在這裡插入圖片描述

快速排序

快速排序是我們最常用並且最快的一種排序演算法,實現起來也很簡單,但有點難理解,其主要思想就是我們在陣列中找到一個基準數,然後對陣列的左右兩邊進行遍歷,找到一個比基準數大的數和一個比基準數小的數,將兩個數換位,這樣一輪迴圈下來,當左右兩個指標相遇的時候,左邊都是比基準數小的數,右邊的都是比基準數大的數,然後我們對左右兩邊再遞迴運算,最後將所有的數都進行了排序。(話不多說,看圖理解)
在這裡插入圖片描述
步驟簡述:
我們的中心思想就是把比基準數大的放在基準數右邊,比基準數小的放在基準數左邊
1、定義left,right,基準數base=arr[left]
2、先從right開始找,找到一個比base小的樹,在開始從left開始找比base大的(如果我們從左邊先開始找,那麼我們的基準數就得是arr[right],否則我們進行第3步的時候,交換後可能會把一個比基準數大的交換到left位置,這樣就無法繼續操作)
3、當指標相遇的時候,我們交換指標位置和基準數的位置
4、此時新的基準數產生(指標相遇位置的數)
5、調整left和right,遞迴執行上述步驟

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        //如果左邊邊界大於右邊,就return
        if (left >= right) {
            return;
        }

        int l = left;//用於標識左邊指標
        int r = right;// 用於標識右邊指標
        int base = arr[left];//記錄基準數
        //判斷指標有沒有相遇
        while (l != r) {
            while (arr[r] >= base && r > l) {//先從右往左找出比基準數小的數
                r--;
            }
            while (arr[l] <= base && l < r) {//再從左向右找出比基準數大的數
                l++;
            }
            //交換
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //當指標相遇時,交換基準數和指標的位置,此時指標位置就是基準數,指標左邊的都不大於基準數,右邊的都不小於基準數
        arr[left] = arr[l];
        arr[l] = base;

        //遞迴呼叫,將左邊所有的數的進行排序
        quickSort(arr, left, l - 1);
        //右邊的排序
        quickSort(arr, r + 1, right);
    }

    public static void main(String[] args) {
        int[] arr ={4, 1, 7, 6, 8, 3, 10};
        int left = 0;
        int right = arr.length - 1;
        quickSort(arr, left, right);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

在這裡插入圖片描述

歸併排序:

在學習歸併排序之前,我們先看一個例子,如果一個數組{2,5,8,9,1,3,4,7},這個陣列的特點是前半部分和後半部分都是有序的,我們對他進行排序,那麼我們就把它分成兩個有序的陣列,然後透過對比,將較小的放進陣列中,最終就得到了一個有序的陣列。這個思想就是歸併
那麼我們就先把這個例子用圖解的形式分析一下,然後程式碼實現。當我們完成下面的例子後,就可以著手去實現任意情況的陣列的歸併排序。
在這裡插入圖片描述
實現程式碼:

public class MergeSort {
    /**
     * @param arr 傳入陣列
     * @param l 左邊起始位置下標
     * @param r 最右邊下標
     * @param m 中間點
     */
    public static void Merge(int[] arr, int l, int r, int m) {
        int LEFT_SIZE = m - l;
        int RIGHT_SIZE = r - m + 1;
        //建立兩個陣列存
        int[] left = new int[LEFT_SIZE];
        int[] right = new int[RIGHT_SIZE];
        for (int i = l; i < m; i++) {
            left[i-l] = arr[i];
        }
        for (int i = m; i <= r; i++) {
            right[i-m] = arr[i];
        }
        //透過上述步驟,我們就可以把陣列分成兩個有序的陣列,分別存放在兩個不同的陣列中
        int i=0,j=0,k=l;//定義三個指標,分別代表left陣列、right陣列、arr陣列的初始指標
        while(i<LEFT_SIZE && j<RIGHT_SIZE ){//如果兩邊都沒有到陣列邊界
            if(left[i]<right[j]){//我們比較兩個位置,將較小的放在陣列的位置
                arr[k]=left[i];
                k++;i++;
            }
            else {
                arr[k]=right[j];
                k++;j++;
            }
        }
        //出了上述迴圈,但是仍然存在可能有陣列中的數沒有放完的情況,我們直接按照順序放入即可。
        while (i<LEFT_SIZE){
            arr[k]=left[i];
            k++;i++;
        }while (j<RIGHT_SIZE){
            arr[k]=right[j];
            k++;j++;
        }

    }
    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 9, 1, 3, 4, 7};
        int l = 0;
        int r =arr.length-1;
        int mid =arr.length/2;
        Merge(arr, l, r,mid);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

在這裡插入圖片描述
這樣我們就把這個陣列排好序了。
這個時候就有人問了:你這剛好兩邊都是有序的,現實中可不是這樣。
那我們想想,其他混亂一點的陣列可以使用歸併嗎?
答案當然是可以
如果有一定經驗的小夥伴,肯定已經想到了分治,在上述案例中,我們是把資料砍成兩段,每段都是有序的,那麼給出一個混亂的資料,我們遞迴的去砍,到最後砍的兩邊各剩一個數,那麼它不就是上述情況了?就好比{5,3},我們砍一下{3}、{5},使用歸併,自然就是{3,5}了。如果還不明白,我們接著看圖
在這裡插入圖片描述
用程式碼實現它:

  public static void Merge(int[] arr, int l, int r, int m) {
        int LEFT_SIZE = m - l;
        int RIGHT_SIZE = r - m + 1;
        //建立兩個陣列存
        int[] left = new int[LEFT_SIZE];
        int[] right = new int[RIGHT_SIZE];
        for (int i = l; i < m; i++) {
            left[i-l] = arr[i];//注意 此時的left[i-l]不能寫arr[i],因為在遞迴中l的動態變化的,如果寫死的話,可能出現角標異常的情況
        }
        for (int i = m; i <= r; i++) {
            right[i-m] = arr[i];
        }
        //透過上述步驟,我們就可以把陣列分成兩個有序的陣列,分別存放在兩個不同的陣列中
        int i=0,j=0,k=l;//定義三個指標,分別代表left陣列、right陣列、arr陣列的初始指標
        while(i<LEFT_SIZE && j<RIGHT_SIZE ){//如果兩邊都沒有到陣列邊界
            if(left[i]<right[j]){//我們比較兩個位置,將較小的放在陣列的位置
                arr[k]=left[i];
                k++;i++;
            }
            else {
                arr[k]=right[j];
                k++;j++;
            }
        }
        //出了上述迴圈,但是仍然存在可能有陣列中的數沒有放完的情況,我們直接按照順序放入即可。
        while (i<LEFT_SIZE){
            arr[k]=left[i];
            k++;i++;
        }while (j<RIGHT_SIZE){
            arr[k]=right[j];
            k++;j++;
        }
    }
    public static  void mergeSort(int[] arr,int l,int r){
        if(l==r){
            return;
        }else {
        int m=(l+r)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        Merge(arr,l,r,m+1);
        }
    }
    public static void main(String[] args) {
       int[] arr = {1, 4, 7, 10, 8, 3, 6, 5};
        int l = 0;
        int r =arr.length-1;
        mergeSort(arr, l, r);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}

在這裡插入圖片描述
成功!

本文章已修改原文用詞符合繁體字使用者習慣使其容易閱讀

版權宣告:此處為CSDN博主「可樂不可樂。」的原創文章,依據CC 4.0 BY-SA版權協議,轉載請附上原文出處連結及本宣告。

原文連結:https://blog.csdn.net/l2470334493/article/details/109078770