二分插入法每次看都无法一次理解清楚,在这里做一次笔记加深下印象。
一、Java代码如下所示:
public static void main(String[] args) { int [] values = new int[]{3,8,7,6,1,9,12,2,5,11}; for(int i = 0 ; i < values.length ; i++){ System.err.print(values[i] + ","); } System.err.println(); sort(values); System.err.println(); for(int i = 0 ; i< values.length; i++){ System.err.print(values[i] + ","); } } public static void sort(int [] values){ for(int i = 0 ;i < values.length ; i++) //步骤1 int now = values[i]; int left = 0; int right = i -1; int center = 0; while(left <= right){ //步骤2 center = (left + right)/2; if(now < values[center]){ //步骤2.1 right = center -1; }else{ //步骤2.2 left = center + 1; } } for(int j = i-1 ;j >= left ; j--){ //步骤4 4.1 4.2 values[j+1] = values[j]; } if(left != i){ //步骤5 5.1 5.2 values[left] = now; } } }
输出结果:
3,8,7,6,1,9,12,2,5,11, 1,2,3,5,6,7,8,9,11,12,
二、简单举例说一下当I=4时代码执行过程 ,详细过程如下图所示:
在i = 0、1、2、3执行完以后,values的顺序就变成如下列表:
3, 6, 7, 8, 1, 9, 12, 2, 5, 11
此时当i=4初进循环时:
now = 1 ; left = 0 ; right = 3 ; center = 0;
left (1) <= right (3) 进入while循环:
center(1) = (left(0) + right(3))/2;
now(1) < values[center] (6)进入if:
right(2) = right(3) - 1;
left (1) <= right (2)进入while循环:
center(1) = (left(0) + right(2))/2;
now(1) < values[center] (6)进入if:
right(1) = right(2) - 1;
left (1) <= right (1)进入while循环:
center(0) = (left(0) + right(1))/2;
now(1) < values[center] (3)进入if:
right(0) = right(1) - 1;
left (0) <= right (0)进入while循环:
center(0) = (left(0) + right(1))/2;
now(1) < values[center] (3)进入if:
right(-1) = right(0) - 1;
left (0) <= right (-1)跳出while循环:
center = 0 ; left = 0 ; right=-1; now = 1;
j(3)=i(4)-1 >= left(0) 进入For循环:
values[j(3)+1] = values[j(3)];
valus = 3, 6, 7, 8, 8, 9, 12, 2, 5, 11;
j(2)=i(4)-1-1 >= left(0) 进入For循环:
values[j(2)+1] = values[j(2)];
valus = 3, 6, 7, 7, 8, 9, 12, 2, 5, 11;
j(1)=i(4)-1-1-1 >= left(0) 进入For循环:
values[j(1)+1] = values[j(1)];
valus = 3, 6, 6, 7, 8, 9, 12, 2, 5, 11;
j(0)=i(4)-1-1-1-1 >= left(0) 进入For循环:
values[j(0)+1] = values[j(0)];
valus = 3, 3, 6, 7, 8, 9, 12, 2, 5, 11;
i(4) != left(0) 进入if:
now=1 一直没变;
values[left(0)] =now(1)
valus = 1, 3, 6, 7, 8, 9, 12, 2, 5, 11
接下来进入当I=5的循环,过程同上。
三、执行流程分析说明:
1、对排序数组values进行从索引0进行递增循环,初入循环始终将左索引(left)设置为0,右索引(right)设置为当前索引向左移一位(i-1),并将当前索引(i)对应数组的值赋值给循环内局部变量now进行备份。
2、循环使用左索引(left)与右索引(right)进行比较,如果左索引(left)小于或等于右索引(right)时,取出左右索引之和的中间值索引(center)在values数组中的值(values[center])与当前索引(i)在values数组中的值(now<--values[i]-->)进行比较。
2.1、如果中间索引值(values[center])大于当前索引值(now<--values[i]-->)时,将得到的中间索引(center)向左移动一位重新计算出右索引(right=center-1),继续第2步进行左右索引比较、中间索引值与当前索引值比较。
2.2、如果中间索引值(values[center])小于或等于当前索引值(now<--values[i]-->)时,将得到的中间索引(center)向右移动一位重新计算出左索引(left=center+1),继续第2部进行左右索引比较、中间索引值与当前索引值比较。
3、直到左索引(left)已经向右移动超过了右索引(right)时就跳出循环,进入下一步。此时如果2.1或2.2步已经执行过,那么此时跳出循环后得到左索引(left),就是当前索引对应数组值将要插入到数组中的索引位置。
4、当前索引向左一位(i-1)循环递减得到的索引与第2步骤得到的左索引(left)进行比较。
4.1、如果当前索引左一位(i-1)循环递减的索引结果(i-1-n)大于或等于以上第2步骤得到的左索引时,将前者索引(i-n-1)对应的数组值赋值给该索引的右一位索引(i-1-n+1)对应的数组值。此时在数组中的(i-1-n)索引值和(i-1-n+1)索引值是相同的。接下来进入下一次第4步循环操作。
4.2、如果当前索引左一位(i-1)循环递减的索引结果(i-1-n)小于第三步得到的左索引时,跳出循环进入到下一步。
5、判断第3步获得到的左索引与当前索引进行比较。
5.1、如果不相同时,将第1步获取的now覆值给第3步获得到的左索引对应数组中的值。
5.2、如果相同时,进行下一次第2步循环。
相关推荐
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
常用算法,2分法插入排序的c语言实现。对初学者很有用。
使用二分方法实现插入排序
当你需要构建一个大的有序队列,用插入发太慢了,可以先用二分查找法,找到在队列要插入的位置,把数后移一下,然后放进去。比较效率,下面是java使用示例,需要的朋友可以参考下
Delphi直接插入法排序示例..rar
2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序 一.希尔(Shell)排序法(又称宿小增量排序,是1959年由D.L.Shell提出来的) /* Shell 排序法 */ #include void ...
c语言经典排序算法 常见经典排序算法 1.希尔排序 2.二分插入法 3.直接插入法 4.带哨兵的直接排序法 5.冒泡排序 6.选择排序 7.快速排序 8.堆排序
各宗排序方法C++实现,包含直接插入法,二分插入法,希尔插入法,-直接选择排序,堆选择排序,-冒泡法,-快速排序,归并算法等。掌握这些排序算法,可以轻松应对软件工程师面试
包含了所有主要排序算法: 1 插入类——插入排序(链接法,普通数组法,二分插入法)、希尔排序 2 选择类——直接选择排序、堆排序 3 分配类——基数排序 4 交换类——冒泡排序、快速排序 5 归并排序
编写程序构造一个有序表La,从键盘接收一个关键字key,用二分查找法在La 中查找key,若找到则提示查找成功并输出key所在的位置,否则提示没有找到信息。 2.编写程序实现Hash表的建立、删除、插入以及查找操作。 ...
/* * --插入排序-- * 假定这个数组的序是排好的,然后从头... * 如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。 * 该算法可以认为是插入排序的一个变种,称为二分查找排序。 */
常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是...
二分查找法(Binary Search) 二分搜索树基础 二分搜索树的节点插入 二分搜索树的查找 二分搜索树的遍历(深度优先遍历) 层序遍历(广度优先遍历) 删除最大值, 最小值 二分搜索树节点的删除 floor和ceil的实现 并查集 ...
C语言中常见的排序算法包括归并排序、选择排序、直接插入排序、希尔排序、冒泡排序、快速排序、堆排序以及顺序查找和二分查找。这些排序算法各有特点,在不同情况下有着不同的应用场景和性能表现。 归并排序(Merge...
在插入算法中,实际上是增量法,现在我们在寻找位置的时候增加效率,通过二分查找来选择。
� 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的...二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 � 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵......
本文实例讲述了C++二分查找(折半查找)算法。分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。 因此,折半查找...
查找表源码,其中包含两个独立的程序: (1)哈希(Hash)表操作测试程序 (2)二分查找法测试程序 用C语言编译器编译后可以直接运行,功能包括查找、插入、删除等操作。
二分法查找法以及和二叉树查找的联系,部分二分搜索和二叉查找树的相关题目: 插入位置;区间查找;旋转位置查找;二叉查找树的编码和解码;逆序数的解题方法和代码实现