本文主要详细介绍了Java经典排序算法中的二进制插入排序。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下。
一、折半插入排序(二分插入排序)
将直接插入排序中求A[i]插入位置的方法改为半比较,可以得到半插入排序算法。处理A[i]时,A[0]……A[i-1]已经按照键值排序。所谓半比较,就是在插入A[i]时,将A[i-1/2]的键值与A[i]的键值进行比较。如果A[i]的键值小于A[i-1/2]的键值,则意味着A[i]只能将A[0]插入到A [I-]中,否则只能插入到A[i-1/2]和A[i-1]之间,因此可以在A[i-1/2 1]和A[i-1]之间继续进行二元比较。如此,直到插入位置最终被确定。一般在A[k]和A[r]之间使用半折叠,其中中间节点为A[k r/2]。经过比较,可以剔除一半的记录,可能的插入间隔减少一半,所以叫对折。执行半插入排序的前提是文件记录必须按顺序存储。
二、算法原理
半插入排序的算法思想;
算法的基本过程:
(1)计算0 ~ i-1的中间点,将I索引处的元素与中间值进行比较。如果I索引处的元素很大,则意味着要插入的元素应该在中间值和新添加的I索引之间。相反,是从初始位置到中间值,所以完成半折叠非常简单;
(2)在相应的一半范围内寻找插入位置时,继续用步骤(1)缩小范围,继续对折,范围依次缩小到1/2 1/4 1/8.快速确定第I个元素应该插入的位置;
(3)位置确定后,将整个序列向后移动,将元素插入相应的位置。
三、代码实现
公共类二进制排序{
public static void binary sort(int[]source){
int i,j;
int高、低、中;
内部温度;
for(I=1;I源.长度;i ) {
//求面积的上界
低=0;
//求面积的下限
高=I-1;
//保存当前要插入到临时变量中的记录。
temp=source[I];
while(低=高){
//找出中间值
//mid=(低高)/2;
mid=(低高)1;
//如果要插入的记录小于中间记录
if (tempsource[mid] ) {
//插入点在下半部分
高=中-1;
}否则{
//插入点在上半部分。
低=中1;
}
}
//将所有大于要插入的当前记录的先前记录向后移动。
for(j=I-1;j=低;j - ) {
source[j 1]=source[j];
}
//将要插入的记录回填到正确的位置。
source[low]=temp;
system . out . print(' I '行排序:');
printArray(来源);
}
}
私有静态void printArray(int[] source) {
for(int I=0;I源.长度;i ) {
system . out . print(' \ t ' source[I]);
}
system . out . println();
}
公共静态void main(String[] args) {
int source[]=new int[] { 12,15,9,14,4,18,23,6 };
System.out.print ('initial关键字:');
printArray(来源);
system . out . println(');
binarySort(源);
system . out . print(' \ n \ n n \ n已编辑的结果:');
printArray(来源);
}
}
四、运行结果
初始关键词:12 15 9 14 4 18 23 6
一阶:12 15 9 14 4 18 23 6
二阶:9 12 15 14 4 18 23 6
三阶:9 12 14 15 4 18 23 6
第四顺序:4 9 12 14 15 18 23 6
五阶:4 9 12 14 15 18 23 6
第六阶:4 9 12 14 15 18 23 6
第七阶:4 6 9 12 14 15 18 23
排序后:4 6 9 12 14 15 18 23
这就是本文的全部内容。希望对大家的学习有帮助,支持我们。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。