数据结构与算法系列——排序(3)_折半插入排序
1.?工作原理（定義）
二分插入排序（Binary Insertion Sort，折半插入排序 OR?拆半插入排序），采用折半查找方法。?
二分查找插入排序的原理：是直接插入排序的一個變種；區(qū)別是：在有序區(qū)中查找新元素插入位置時，為了減少元素比較次數(shù)提高效率，采用二分查找算法進行插入位置的確定。
2.?算法步驟
? ? 設(shè)數(shù)組為a[0…n]。?
1. 將原序列分成有序區(qū)和無序區(qū)。a[0…i-1]為有序區(qū)，a[i…n] 為無序區(qū)。（i從1開始）?
2. 從無序區(qū)中取出第一個元素，即a[i]，使用二分查找算法在有序區(qū)中查找要插入的位置索引j。?
3. 將a[j]到a[i-1]的元素后移，并將a[i]賦值給a[j]。?
4. 重復(fù)步驟2~3，直到無序區(qū)元素為0。
3.?圖片演示
?
4.?性能分析
1. 時間復(fù)雜度
不難看出，折半插入排序僅僅是減少了比較元素的次數(shù)，約為O(nlogn)，而且該比較次數(shù)與待排序表的初始狀態(tài)無關(guān)，僅取決于表中的元素個數(shù)n；而元素的移動次數(shù)沒有改變，它依賴于待排序表的初始狀態(tài)。因此，折半插入排序的時間復(fù)雜度仍然為O(n2)，但它的效果還是比直接插入排序要好。?
最好時間復(fù)雜度O(n)
平均時間復(fù)雜度O(n2)
最壞時間復(fù)雜度O(n2)
2. 空間復(fù)雜度
插入排序過程中，需要一個臨時變量temp存儲待排序元素，因此空間復(fù)雜度為O(1)。
3. 算法穩(wěn)定性?
插入排序是一種穩(wěn)定的排序算法。
4.?優(yōu)缺點
- 優(yōu)點 : 穩(wěn)定，相對于直接插入排序元素減少了比較次數(shù)；
- 缺點 : 相對于直接插入排序元素的移動次數(shù)不變；
5.?優(yōu)化
2-路插入排序算法是在折半插入排序的基礎(chǔ)上對其進行改進，減少其在排序過程中移動記錄的次數(shù)從而提高效率。
具體實現(xiàn)思路為：另外設(shè)置一個同存儲記錄的數(shù)組大小相同的數(shù)組 d，將無序表中第一個記錄添加進 d[0] 的位置上，然后從無序表中第二個記錄開始，同 d[0] 作比較：如果該值比 d[0] 大，則添加到其右側(cè)；反之添加到其左側(cè)。
在這里的數(shù)組 d 可以理解成一個環(huán)狀數(shù)組。使用 2-路插入排序算法對無序表{3,1,7,5,2,4,9,6}排序的過程如下：
- 將記錄 3 添加到數(shù)組 d 中：
? - 然后將 1 插入到數(shù)組 d 中，如下圖所示：
? - 將記錄 7 插入到數(shù)組 d 中，如下圖所示：
? - 將記錄 5 插入到數(shù)組 d 中，由于其比 7小，但是比 3 大，所以需要移動 7 的位置，然后將 5 插入，如下圖所示：
? - 將記錄 2 插入到數(shù)組 d 中，由于比 1大，比 3 小，所以需要移動 3、7、5 的位置，然后將 2 插入，如下圖所示：
? - 將記錄 4 插入到數(shù)組 d 中，需要移動 5 和 7 的位置，如下圖所示：
? - 將記錄 9 插入到數(shù)組 d 中，如下圖所示：
? - 將記錄 6 插入到數(shù)組 d 中，如下圖所示：
?
最終存儲在原數(shù)組時，從 d[7] 開始依次存儲。
2-路插入排序相比于折半插入排序，只是減少了移動記錄的次數(shù)，沒有根本上避免，所以其時間復(fù)雜度仍為O(n2)。
6.?具體代碼
import java.util.Arrays;public class BinaryInsertionSort{public static void main(String[] args) {int[] arr = {8,7,6,5,4,3,2,1};System.out.println(Arrays.toString(binaryInsertionSort2(arr)));}// 二分插入排序public static int[] binaryInsertionSort(int[] sourceArray) {// 對 arr 進行拷貝，不改變參數(shù)內(nèi)容int len = sourceArray.length;int[] arr = Arrays.copyOf(sourceArray, len);// 從下標(biāo)為1的元素開始選擇合適的位置插入，因為下標(biāo)為0的只有一個元素，默認是有序的for (int i = 1; i < len; i++) {int left = 0;int right = i-1;int tmp = arr[i]; // 記錄要插入的數(shù)據(jù)while(left <= right) {int mid = (left + right) / 2; //二分區(qū)域if(arr[mid] > tmp) {right = mid - 1; //向左縮小區(qū)域}else {left = mid + 1; //向右縮小區(qū)域，當(dāng)?shù)扔诘臅r候往后加一位，保證了穩(wěn)定性 }}//arr[left,i-1]的元素整體后移for(int j=i; j>=left+1; j--) {arr[j] = arr[j-1];}arr[left] = tmp;}return arr;}//改進的二分插入--2路插入排序public static int[] binaryInsertionSort2(int[] sourceArray){int first = 0;//分別記錄temp數(shù)組中最大值和最小值的位置int last = 0;int k = 0;int len = sourceArray.length;int[] arr = Arrays.copyOf(sourceArray, len);int[] temp = new int[len];temp[0] = arr[0];for (int i = 1; i < len; i++){// 待插入元素比最小的元素小if (arr[i] < temp[first]){first = (first - 1 + len) % len;temp[first] = arr[i];}// 待插入元素比最大元素大else if (arr[i] > temp[last]){last = (last + 1 + len) % len;temp[last] = arr[i];}// 插入元素比最小大，比最大小else {k = (last + 1 + len) % len;//當(dāng)插入值比當(dāng)前值小時，需要移動當(dāng)前值的位置while (temp[((k - 1) + len) % len] > arr[i]) {temp[(k + len) % len] =temp[(k - 1 + len) % len];k = (k - 1 + len) % len;}//插入該值temp[(k + len) % len] = arr[i];//因為最大值的位置改變，所以需要實時更新final的位置last = (last + 1 + len) % len;}}// 將排序記錄復(fù)制到原來的順序表里for (k = 0; k < len; k ++) {arr[k] = temp[(first + k) % len];}return arr;} }7.?參考網(wǎng)址
轉(zhuǎn)載于:https://www.cnblogs.com/haimishasha/p/10841044.html
總結(jié)
以上是生活随笔為你收集整理的数据结构与算法系列——排序(3)_折半插入排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 数据结构与算法：单链表（利用万能指针实现
- 下一篇： 关于es6的const跟vuex里的ge