排序算法介紹

排序算法是通過特定的算法因式將一組或多組數(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)文章希望大家以后多多支持腳本之家！

最新評論