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)文章
關(guān)于springboot使用rocketmq?RocketMQMessageListener參數(shù)問題
這篇文章主要介紹了springboot使用rocketmq?RocketMQMessageListener參數(shù)問題,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值需要的朋友可以參考下2022-11-11Java進(jìn)階學(xué)習(xí):jar打包詳解
Java進(jìn)階學(xué)習(xí):jar打包詳解...2006-12-12MyBatis-Plus之邏輯刪除的實(shí)現(xiàn)
這篇文章主要介紹了MyBatis-Plus之邏輯刪除的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11Mybatis持久層框架入門之CRUD實(shí)例代碼詳解
這篇文章主要介紹了Mybatis持久層框架入門之CRUD實(shí)例,需要的朋友可以參考下2022-05-05Java實(shí)現(xiàn)多文件壓縮加密并重命名壓縮文件對象的方法
這篇文章主要介紹了Java實(shí)現(xiàn)多文件壓縮加密并重命名壓縮文件對象的方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-01-01SpringBoot Redis配置Fastjson進(jìn)行序列化和反序列化實(shí)現(xiàn)
這篇文章主要介紹了SpringBoot Redis配置Fastjson進(jìn)行序列化和反序列化實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10Java 創(chuàng)建線程的3種方法及各自的優(yōu)點(diǎn)
這篇文章主要介紹了Java 創(chuàng)建線程的3種方法及各自的優(yōu)點(diǎn),文中講解非常細(xì)致,代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下2020-07-07MyBatis-Plus聯(lián)表查詢以及分頁代碼實(shí)例
在開發(fā)中遇到了一個(gè)問題,需要進(jìn)行聯(lián)表查詢并進(jìn)行分頁,因?yàn)椴幌胱约簛韺懛猪?所以還是依靠MybatisPlus來實(shí)現(xiàn)想要的功能,下面這篇文章主要給大家介紹了關(guān)于MyBatis-Plus聯(lián)表查詢以及分頁的相關(guān)資料,需要的朋友可以參考下2023-06-06