Java冒泡選擇插入希爾排序的原理是什么與怎么實現

這篇文章主要介紹了Java冒泡選擇插入希爾排序的原理是什么與怎么實現的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java冒泡選擇插入希爾排序的原理是什么與怎么實現文章都會有所收獲，下面我們一起來看看吧。

一、冒泡排序

1、基本介紹

冒泡排序是重復地走訪要排序的元素，依次比較兩個相鄰的元素，如果它們的順序與自己規定的不符合，則把兩個元素的位置交換。走訪元素重復地進行，直到沒有相鄰元素需要交換為止，完成整個排序過程。

? 算法原理

1、比較相鄰元素，如果前一個元素大于后一個元素，則交換。

2、依次向后對每一對相鄰元素做同樣的工作，直到隊列末尾，第一輪過后最大的元素就位于最后一個元素位置了。

3、重復以上步驟，直到最后一個元素位置的前一位為止（因為最后一位已經排了）。

4、持續每次對越來越少的元素重復上面步驟，直到第一個元素和第二個元素交換后順序為從大到小或從小到大，排序結束。

2、代碼實現

冒泡排序實際上就是兩個數兩個數的比較，每循環一次將最大或最小的數放在最后，剩下的就繼續兩兩比較。

public static void bubbleSort(int[] arr){
        //中間變量，用來交換數據
        int temp = 0;
        //外層循環
        for (int i = 0 ; i < arr.length - 1 ; i++){
            //內層循環，每次找到最大的數后放在最后，下次遍歷則會少一次，及arr.length - i - 1
            for(int j = 0; j < arr.length - i - 1; j++){
                //判斷大小
                if(arr[j] > arr[j + 1]){
                    //將兩數進行交換
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
}

二、 選擇排序

1、基本介紹

首先第一次確定第一個數為最小的，然后利用for循環，將第一個數后的數據遍歷一遍，找是否還有比第一個數更小的，記錄下來，遍歷完畢后將第一個數與最小的數進行交換。然后又確定第二數，找第二個數以后的數，是否還有比第二個數更小的，找到后與第二個數又進行交換，重復上面即可。

以后的每次循環都是按照這種方式，直到最后兩個數排完，數據就是有序的了。

2、代碼實現

public static void choiceSort(int[] arr){
        //用來記錄最小的數
        int arrData = 0;
        //記錄最小的數的下標
        int arrindx = 0;
        //外層循環，直到 arr.length - 1 即可
        for(int i = 0; i < arr.length - 1; i++){
            //首先把arr[i] 當做最小的數，并記錄下標
            arrData = arr[i];
            arrindx = i;
            //內層循環，遍歷 i 以后的數，找到比 arr[i] 還小的數
            for (int j = i + 1; j < arr.length; j++){
                //找到更小的數，就進行記錄
                if(arrData > arr[j]){
                    arrData = arr[j];
                    arrindx = j;
                }
            }
            //循環完畢，說明找到了，最小的數，與arr[i] 進行交換即可
            arr[arrindx] = arr[i];
            arr[i] = arrData;
        }
}

三、插入排序

1、基本介紹

前面我們介紹的選擇排序，找到最小的就與前面的進行交換。而插入排序，就是將確定的數的后一位插入到前面即可。圖形介紹：

開始，id指向第一個數，mid指向第二個數，然后兩個數進行比較。

此時，1 比 3 小，但是3前面沒數據了，于是將1插入到3的前面，注意這里是插入，不是交換。下一步 3 比 5 小，于是不用插入。

經過三次比較，確定了 2 的位置在 1 和 3 直接，直接將 2 插入。

又經過四次比較，找到 0 的位置 在 1 的前面，于是將 0 插入到 1 的前面即可。

2、代碼實現

 public static void insertSort(int[] arr){
        //下標為 0 的數是確定的，從下標為 1 開始循環
        for (int i = 1; i < arr.length; i++){
            // 將下標為 i 的數暫存起來
            int arrData = arr[i];
            //從 i - 1 開始往前循環
            int arrIndx = i - 1;
            //判斷退出的條件 大于等于0
            while (arrIndx >= 0){
                //如果arrData 大于 下標為arrIndx 的數，則位置找到，退出循環
                if (arrData > arr[arrIndx]){
                    break;
                }
                //沒有找到，就將前面的數往后移
                arr[arrIndx + 1] = arr[arrIndx];
                arrIndx--;
            }
            //找到位置后，就將暫存的數據arrData 插入到下標為arrIndx的位置
            arr[arrIndx + 1] = arrData;
        }
    }

四、希爾排序

1、基本介紹

首先將數組分為兩組，3、2、0 為一組，1、5為一組，g = arr.length / 2。

2 和 3 進行判斷，3 比 2 大 ，然后進行交換位置，交換后 j = j- g< 0（因為第一次的分為兩組，所以 i - 2）。所以 i++ ，j = i - g

不需要交換， 然后 j = j- g < 0 ,所以 i++ ，j = i - g

3 比 0 大 ，需要交換。然后 j = j - g > 0 , j = j - g

交換后 j = j - g < 0 , i++ > arr.length 了，第一輪結束

第二輪：在arr.length / 2的基礎上再除2 ， 于是 g = 1 ；

然后兩兩交換，交換后 進行j = j - g > 0 的判斷 ，不成立則 i++, j = i - g ，成立則 j = j - g ，就這樣一直循環下去。第二輪后的結果：

第二輪結束后，g / 2 = 0 結果不大于 0，所以排序結束

2、代碼實現（交換排序）

    public static void shellSort_exchange(int[] arr){
        //做中間變量，進行數據交換
        int temp = 0;
        // g 首先數組總長除以2， 然后每次除以2
        for(int g = arr.length / 2 ; g > 0 ; g /= 2){
            // i 從 g 的位置開始遍歷
            for(int i = g ; i < arr.length ; i++){
                // j 從 i - g 的位置開始向前遍歷，j 的位置由 j - g 來決定
                for(int j = i - g ; j >= 0 ; j -= g){
                    //判斷 下標(j + g) 和 下標j 位置的數的大小，然后進行交換
                    if(arr[j + g] < arr[j]){
                        //交換即可
                        temp = arr[j + g];
                        arr[j + g] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    }

3、代碼實現（移位排序）

移位排序的思想與前面的交換排序一樣的，只是在交換數的方式上有變化。交換排序數的交換方式來自冒泡排序，而移位排序數的交換方式來自插入排序。

    public static void test1(int[] arr){
        //與前面一樣，開始數組長度除以2 ， 然后每次除以2
        for(int g = arr.length / 2 ; g > 0 ; g /= 2){
            // i 從 g 位置開始，每次加一
            for(int i = g ; i < arr.length ; i++){
                //定義 j 的位置 為 i
                int j = i ;
                //將 下標為 i 位置的數暫存起來
                int temp = arr[i];
                //判斷 下標j位置的數 和 j - g 位置的數，與前面一樣
                if(arr[j] < arr[j - g] ){
                    //遍歷循環
                    while(j - g >= 0 && temp < arr[j - g]){
                        //滿足條件，就移位，將前面的數 (下標j - g) 往后移 (下標j)
                        arr[j] = arr[j - g];
                        j -= g;// j 每次 -g
                    }
                }
                //退出循環或判斷條件后，將暫存的temp (arr[i]) 賦值給 arr[j]
                arr[j] = temp;
            }
        }
    }

關于“Java冒泡選擇插入希爾排序的原理是什么與怎么實現”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Java冒泡選擇插入希爾排序的原理是什么與怎么實現”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。