Java二分法排序,java排序的几种方法,Java经典排序算法之二分插入排序详解

Java二分法排序,java排序的几种方法,Java经典排序算法之二分插入排序详解

本文主要详细介绍了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的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: