-
折半插入排序
鎖定
折半插入排序（Binary Insertion Sort）是對插入排序算法的一種改進。所謂插入排序，就是不斷的依次將元素插入前面已排好序的序列中。
- 中文名
- 折半插入排序
- 外文名
- Binary Insertion Sort
- 類 型
- 插入排序
- 時間複雜度
- O(n^2)
- 空間複雜度
- O(1)
- 穩定性
- 穩定
折半插入排序基本概念
折半插入排序（binary insertion sort）是對插入排序算法的一種改進，由於排序算法過程中，就是不斷的依次將元素插入前面已排好序的序列中。由於前半部分為已排好序的數列，這樣我們不用按順序依次尋找插入點，可以採用折半查找的方法來加快尋找插入點的速度。
[1]
折半插入排序具體操作
在將一個新元素插入已排好序的數組的過程中，尋找插入點時，將待插入區域的首元素設置為a[low]，末元素設置為a[high]，則每輪比較時將待插入元素與a[m]，其中m=(low+high)/2相比較,如果比參考元素小，則選擇a[low]到a[m-1]為新的插入區域(即high=m-1)，否則選擇a[m+1]到a[high]為新的插入區域（即low=m+1），如此直至low＜=high不成立，即將此位置之後所有元素後移一位，並將新元素插入a[high+1]。
[1]
折半插入排序穩定性及複雜度
折半插入排序算法是一種穩定的排序算法，比直接插入算法明顯減少了關鍵字之間比較的次數，因此速度比直接插入排序算法快，但記錄移動的次數沒有變，所以折半插入排序算法的時間複雜度仍然為O(n^2)，與直接插入排序算法相同。附加空間O(1)。
[1]
折半查找只是減少了比較次數，但是元素的移動次數不變，所以時間複雜度為O(n^2)是正確的！
折半插入排序算法示例
折半插入排序C++
#define _CRT_SECURE_NO_WARNINGS
#include ＜iostream＞
#define LEN 8 // 有LEN個元素要排
int key;
int otherinfo;
};
void BInsertSort(Record *arr, int length) // length是要排序的元素的個數，0號單元除外
{
for (int i = 2; i ＜= length; ++i) {
arr[0] = arr[i]; // 將arr[i]暫存到arr[0]
int low = 1;
int high = i - 1;
while (low ＜= high) { // 在arr[low..high]中折半查找有序插入的位置
int m = (low + high) / 2; // 折半
if (arr[0].key ＜ arr[m].key) // 關鍵字相同時，使low = m + 1，到高半區，保證穩定性
high = m - 1; // 插入點在低半區
else
low = m + 1; // 插入點在高半區
}
for (int j = i - 1; j ＞= high + 1; --j)
arr[j + 1] = arr[j]; // 記錄後移
arr[high + 1] = arr[0]; // 插入
}
}
int main(void)
{
freopen("in.txt", "r", stdin);
Record a[LEN + 1] = {0};
for (int i = 1; i ＜= LEN; i++)
BInsertSort(a, LEN);
for (int i = 1; i ＜= LEN; i++)
cout ＜＜ a[i].key ＜＜ '\t' ＜＜ a[i].otherinfo ＜＜ endl;
return 0;
}
/*
in.txt:
49 1
38 0
65 0
97 0
76 0
13 0
27 0
49 2
out:
13 0
27 0
38 0
49 1
49 2
65 0
76 0
97 0
折半插入排序JAVA
public class MyBinaryInsertionSort{
public static void main(String[] args){
// 待排序的數組
int[] array = { 1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7};
binaryInsertSort(array);
// 顯示排序後的結果。
System.out.print("排序後： ");
for(int i = 0; i < array.length; i++){
System.out.print(array[i] + " ");
}
}
// 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;
}
}
}折半插入排序C語言
typedef int ElemType ;
ElemType arr[]={0,9,8,7,6,5,4,3,2,1};
ElemType n=10,i,j;
ElemType low,high,mid;
void BinSort(ElemType r[],ElemType n)
{
for(i=2;i＜=n;i++)
{
r[0]=r[i];
low=1; high=i-1;
while (low＜=high)
{
mid=(low+high)/2;
if(r[0]＜r[mid])
high=mid-1;
else
low=mid+1;}
for(j=i-1;j＞=low;j--)
{
r[i]=r[j];
i--;
}
r[low]=r[0];} }
void put(ElemType r[],ElemType n)
{
for(j=1;j＜n;j++)
printf("%d\t",r[j]);
printf("\n");
}
void main()
{
BinSort(arr,n);
put(arr,n);
}
- 參考資料
-
- 1. 折半插入排序 ．博客園[引用日期2012-11-29]
- 2. 折半插入排序 Java ．csdn[引用日期2012-11-29]
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：21次歷史版本
- 最近更新： 北辰以北1209