前言: 折半插入排序( Binary Insertion Sort )是对直接插入排序算法的一种改进。
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分,否则属于后半部分。依次类推,不断缩小范围,确定要插入的位置。
算法说明:
待排序数据: 2 , 1 , 6 , 7 , 4
取个元素作为有序表,剩余的元素作为无序表
其中有序表: 2 ;无序表: 1 , 6 , 7 , 4
次比较,从无序表中取出个数 1 ,与中间值 2 比较, 1<2 , 1 插到 2 的前面,得到
有序表: 1 , 2 ;无序表: 6 , 7 , 4
第二次比较,从无序表中取出个数 6 ,与中间值 1 比较, 6>1 ,要放在 1 的后面,再与后半区(有序表: 2 )的中间值 2 比较, 6>2 ,6 插入到 2 的后面,得到
有序表: 1 , 2 , 6 ;无序表: 7 , 4
第三次比较,从无序表中取出个数 7 ,与中间值 2 比较, 7>2 , 7 放在 2 后面,再与后半区(有序表: 6 )的中间值 6 比较, 7>6 , 7放在 6 后面,得到
有序表: 1 , 2 , 6 , 7 ;无序表: 4
第四次比较,从无序表中取出个数 4 ,与中间值 2 比较, 4>2 , 4 放在 2 后面,再与后半区(有序表 :6,7 )的中间值 6 比较, 4<6 , 4放在 6 前面,终得到:
1 , 2 , 4 , 6 , 7
折半插入排序的代码实现
private void binaryInsertSort(int arr[]){
int low = 0;
int high = 0;
int m = 0;// 中间位置
for(int i = 1; i < arr.length; i++){
low = 0;
high = i-1;
while(low <= high){
m = (low+high)/2;
if(arr[m] > arr[i])
high = m - 1;
else
low = m + 1;
}
// 统一移动元素,将待排序元素插入到指定位置
temp = arr[i];
for(int j=i; j > high+1; j--){
arr[j] = arr[j-1];
}
arr[high+1] = temp;
}
}
总结
折半插入排序相对稳定,相对于直接插入排序,减少了比较次数;但是相对直接插入排序,移动次数不变。
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分,否则属于后半部分。依次类推,不断缩小范围,确定要插入的位置 。
算法说明:
待排序数据: 2 , 1 , 6 , 7 , 4
取个元素作为有序表,剩余的元素作为无序表
其中 有序表: 2 ;无序表: 1 , 6 , 7 , 4
次 比较 ,从无序表中取出个数 1 , 与中间值 2 比较, 1<2 , 1 插到 2 的前面,得到
有序表: 1 , 2 ;无序表: 6 , 7 , 4
第二次 比较 ,从无序表中取出个数 6 , 与中间值 1 比较, 6>1 ,要放在 1 的后面,再与后半区(有序表: 2 )的中间值 2 比较, 6>2 , 6 插入到 2 的后面,得到
有序表: 1 , 2 , 6 ;无序表: 7 , 4
第三次 比较 ,从无序表中取出个数 7 , 与中间值 2 比较, 7>2 , 7 放在 2 后面,再与后半区(有序表: 6 )的中间值 6 比较,7>6 , 7 放在 6 后面,得到
有序表: 1 , 2 , 6 , 7 ;无序表: 4
第四次 比较 ,从无序表中取出个数 4 , 与中间值 2 比较, 4>2 , 4 放在 2 后面,再与后半区(有序表 :6,7 )的中间值 6 比较, 4<6 , 4 放在 6 前面,终得到:
1 , 2 , 4 , 6 , 7
折半插入排序的代码实现
private void binaryInsertSort( int arr[]){
2.
int low = ;
int high = ;
int m = ; // 中间位置
for ( int i = 1 ; i < arr.length; i++){
low = ;
high = i- 1 ;
while (low <= high){
m = (low+high)/ 2 ;
if (arr[m] > arr[i])
high = m - 1 ;
else
low = m + 1 ;
}
//统一移动元素,将待排序元素插入到指定位置
temp = arr[i];
for ( int j=i; j > high+ 1 ; j--){
arr[j] = arr[j- 1 ];
}
arr[high+ 1 ] = temp;
}
}
总结
折半插入排序相对稳定,相对于直接插入排序,减少了比较次数;但是相对直接插入排序,移动次数不变。