Java如何實現折半插入排序算法

今天小編給大家分享一下Java如何實現折半插入排序算法的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

排序算法介紹

排序算法是通過特定的算法因式將一組或多組數據按照既定模式進行重新排序。最終序列按照一定的規律進行呈現。

在排序算法中，穩定性和效率是我們經常要考慮的問題。

穩定性：穩定是指當兩個相同的元素同時出現于某個序列之中，則經過一定的排序算法之后，兩者在排序前后的相對位置不發生變化。

復雜度分析：

（1）時間復雜度：即從序列的初始狀態到經過排序算法的變換移位等操作變到最終排序好的結果狀態的過程所花費的時間度量。

（2）空間復雜度：就是從序列的初始狀態經過排序移位變換的過程一直到最終的狀態所花費的空間開銷。

常見的排序算法分為以下幾種：

折半插入排序

原理

折半插入排序（Binary Insertion Sort）是對插入排序算法的一種改進。不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。

代碼實現

在將一個新元素插入已排好序的數組的過程中，尋找插入點時，將待插入區域的首元素設置為 a[low] ，末元素設置為 a[high] ，則每輪比較時將待插入元素與 a[m] ，其中 m = (low+high)/2 相比較，如果比參考元素小，則選擇a[low]到a[m-1]為新的插入區域(即high=m-1)，否則選擇 a[m+1] 到 a[high] 為新的插入區域（即low=m+1），如此直至low<=high 不成立，即將此位置之后所有元素后移一位，并將新元素插入a[high+1]。

總之：利用已排好的元素有序的特點，使用折半查找的特點來快速找到要插入的位置。

    // Binary Insertion Sort method    
    private static void binaryInsertSort(int[] array){
       
        for(int i = 1; i < array.length; i++){
           
            int temp = array[i];            
            int low = 0;            
            int high = i - 1;  
           
            while(low <= high){                
                int mid = (low + high) / 2;                
                if(temp < array[mid]){                    
                    high = mid - 1;                
                }else{                    
                    low = mid + 1;
                }       
            }
           
            for(int j = i; j >= low + 1; j--){            
                array[j] = array[j - 1];                                                      
            }       
           
            array[low] = temp;       
        }   
    }

復雜度分析

折半插入排序算法是一種穩定的排序算法，比直接插入算法明顯減少了關鍵字之間比較的次數，因此速度比直接插入排序算法快，但記錄移動的次數沒有變，所以折半插入排序算法的時間復雜度仍然為O(n^2)，與直接插入排序算法相同。

時間復雜度

最好的情況：O(n)。如果元素排序正向有序，開始的時候就直接找到了位置，不需要尋找和移位。

最壞的情況：O(n^2)。如果元素排序反向有序，那么每次都需要進行數據查找。

平均復雜度：O(n^2)。

空間復雜度：O(1)。僅需幾個存儲空間用于記錄信息的關鍵單元，即空間復雜度為O(1)。

示例：

算法實踐

算法的整體思想已經在上面講述了，下面直接使用一個例子來試試水。

折半插入排序

題目描述：

給你一個整數數組 nums，請你將該數組升序排列。

示例 1：

輸入：nums = [5,2,3,1]

輸出：[1,2,3,5]

示例 2：

輸入：nums = [5,1,1,2,0,0]

輸出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 5 * 104

-5 * 104 <= nums[i] <= 5 * 104

class Solution {
    public int[] sortArray(int[] nums) {
        for(int i = 1; i < nums.length; i++){
           
            int temp = nums[i];            
            int low = 0;            
            int high = i - 1;  
           
            while(low <= high){                
                int mid = (low + high) / 2;                
                if(temp < nums[mid]){                    
                    high = mid - 1;                
                }else{                    
                    low = mid + 1;
                }       
            }
           
            for(int j = i; j >= low + 1; j--){            
                nums[j] = nums[j - 1];                                                      
            }       
           
            nums[low] = temp;       
        }   
        return nums;
    }
}

以上就是“Java如何實現折半插入排序算法”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。