欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)折半插入排序算法的示例代碼

 更新時(shí)間:2022年08月11日 11:34:54   作者:秦 羽  
折半插入排序(Binary Insertion Sort)是對插入排序算法的一種改進(jìn)。不斷的依次將元素插入前面已排好序的序列中。本文將利用Java語言實(shí)現(xiàn)這一排序算法,需要的可以參考一下

排序算法介紹

排序算法是通過特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序。最終序列按照一定的規(guī)律進(jìn)行呈現(xiàn)。

在排序算法中,穩(wěn)定性和效率是我們經(jīng)常要考慮的問題。

穩(wěn)定性:穩(wěn)定是指當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)于某個(gè)序列之中,則經(jīng)過一定的排序算法之后,兩者在排序前后的相對位置不發(fā)生變化。

復(fù)雜度分析:

(1)時(shí)間復(fù)雜度:即從序列的初始狀態(tài)到經(jīng)過排序算法的變換移位等操作變到最終排序好的結(jié)果狀態(tài)的過程所花費(fèi)的時(shí)間度量。

(2)空間復(fù)雜度:就是從序列的初始狀態(tài)經(jīng)過排序移位變換的過程一直到最終的狀態(tài)所花費(fèi)的空間開銷。

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

折半插入排序

原理

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

代碼實(shí)現(xiàn)

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

總之:利用已排好的元素有序的特點(diǎn),使用折半查找的特點(diǎn)來快速找到要插入的位置。

    // 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;       
        }   
    }

復(fù)雜度分析

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

時(shí)間復(fù)雜度

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

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

平均復(fù)雜度:O(n^2)。

空間復(fù)雜度:O(1)。僅需幾個(gè)存儲(chǔ)空間用于記錄信息的關(guān)鍵單元,即空間復(fù)雜度為O(1)。

示例:

算法實(shí)踐

算法的整體思想已經(jīng)在上面講述了,下面直接使用一個(gè)例子來試試水。

折半插入排序

題目描述:

給你一個(gè)整數(shù)數(shù)組 nums,請你將該數(shù)組升序排列。

示例 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;
    }
}

這個(gè)題目非常nice,你可以嘗試去使用不同的排序方法去測試。

到此這篇關(guān)于Java實(shí)現(xiàn)折半插入排序算法的示例代碼的文章就介紹到這了,更多相關(guān)Java折半插入排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評論