活動位址：21天學習挑戰賽
文章目錄
一、算法
1.算法概述
2.算法步驟
二、算法實踐
1.Java代碼
2.執行結果
三、複雜度分析
1.時間複雜度
2.空間複雜度
一、算法
1.算法概述
直接插入排序法采用順序查找法來查找目前記錄在已經排好序的序列中的插入位置，而折半插入排序法則是在查找的過程中采用折半查找法來确定目前記錄在有序序列中的位置，這便是折半插入排序法與直接插入排序法的不同之處
往期相關文章傳送門：
- 經典算法之直接插入排序法
- 經典算法之折半查找法
2.算法步驟
- 設待排序的記錄存放在數組r[1...n ]中，r[1]預設是一個有序序列
- 循環n-1次，每次使用折半查找法，查找r[i](i=2,...,n)在已排序好的序列r[1,....i-1]中的合适插入位置，然後将r[ i ]插入表長為i-1的有序序列r[ 1,...,i-1 ]中，直到将r[ n ]插入到表長為n-1的有序序列r[ 1...n-1 ]，最後得到一個表長為n的有序序列
（注：圖檔來源《資料結構簡明教程》）
二、算法實踐
1.Java代碼
package TwentyOne_Challenge;
public class DaySix {
public static void main(String[] args) {
int []a={3,38,5,44,15,36,26,27,2,47,46,4,19,50,48};
System.out.print("原來序列如下：");
for (int i = 0; i <a.length ; i++) {
System.out.print(a[i]+" ");
}
sort(a);
System.out.println();
System.out.print("經過折半插入排序後：");
for (int i = 0; i <a.length ; i++) {
System.out.print(a[i]+" ");
}
}
private static void sort(int a[]){
for (int i = 1; i <a.length ; i++) {
if(a[i]<a[i-1]){
int temp=a[i];//使用temp暫時存儲待排序的值
int left=0,right=i-1;//左右區間的起始下标
//使用折半查找法查找待排序的記錄在已經排好序的序列中的合适插入位置
while(left<=right){
int mid=(right-left)/2+left;
if(temp<a[mid]){
right=mid-1;
}else{
left=mid+1;
}
}
//找到合适位置後，下面将有序序列中逐個後移空出位置供待排序的記錄插入
for(int j=i-1;j>=right+1;j--){
a[j+1]=a[j];
}
//最後一次循環時,left與right相等，等下一次循環發生交錯循環結束，是以此時插入位置應為right+1或者left
a[right+1]=temp;
//a[left]=temp; 也是正确的
}
}
}
}
2.執行結果
三、複雜度分析
1.時間複雜度
從時間上比較，折半查找比順序查找快，是以就平均性能來說，折半插入排序優于直接插入排序。折半插人排序所需要的關鍵字比較次數與待排序序列的初始排列無關,僅依賴于記錄的個數。不論初始序列情況如何，在插入第i個記錄時，需要經過以2為底 i 的對數向上取整次比較，才能确定它應插人的位置。是以當記錄的初始排列為正序或接近正序時，直接插入排序比折半插入排序執行的關鍵字比較次數要少。
折半插入排序的對象移動次數與直接插入排序相同，依賴于對象的初始排列。
在平均情況下，折半插入排序僅減少了關鍵字間的比較次數,而記錄的移動次數不變。是以，折半插入排序的時間複雜度仍為O(n^2)
2.空間複雜度
在排序過程中隻需要一個輔助變量temp來記錄待排序的值，故其空間複雜度為O(1)