插入排序法（Java实现） |
您所在的位置：网站首页 › 从小到大进行排序 › 插入排序法（Java实现） |
插入排序法（Java实现）
|
插入法排序
※ 插入法排序原理 利用插入法对无序数组排序时，我们其实是将数组R划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。 插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。 ※ 插入实例算法分析 {3 -1 0 -8 2 1} 这是要进行插入排序的数组 {3 -1 0 -8 2 1} -1 先把-1(数组的第二个位置)拿出来当做要进行往左边插入的值， 但是把-1插入到左的什么位置需要通过程序找出来 (左边的值依次和这个值-1作比较得出) {3 3 0 -8 2 1} -1 拿第一个位置的值3和-1比较，发现比-1大，那么就把第一个位置 的值3赋给第二个位置,结果如左边所示 {-1 3 0 -8 2 1} -1 这个时候第一个位置 就有可能是我们要找的插入的位置，进一步发现第一种位置前面 没有值了，那么就果断把-1插入到第一个位置，结果如左边所示， 好了本次循环结束 {-1 3 0 -8 2 1} 0 这次把0(数组的第三个位置)拿出来当做要进行往左边插入的值， 但是把0插入到左的什么位置需要通过程序找出来 (左边的值依次和这个值0作比较得出) {-1 3 3 -8 2 1} 0 拿第二个位置的值3和0比较，发现比0大，那么就把第二个位置 的值3赋给第三个位置,结果如左边所示 {-1 0 3 -8 2 1} 0 这个时候第二个位置 就有可能是我们要找的插入的位置，进一步发现第一个位置的值-1 比0小，那么就果断确定第二个位置就是我们要找的插入位置， 然后把0插入到第二个位置，结果如左边所示， 好了本次循环结束 {-1 0 3 -8 2 1} -8 这次把-8(数组的第四个位置)拿出来当做要进行往左边插入的值， 但是把-8插入到左的什么位置需要通过程序找出来 (左边的值依次和这个值-8作比较得出) {-1 0 3 3 2 1} -8 拿第三个位置的值3和-8比较，发现比-8大，那么就把第三个位置 的值3赋给第四个位置,结果如左边所示 {-1 0 0 3 2 1} -8 拿第二个位置的值0和-8比较，发现比-8大，那么就把第二个位置 的值0赋给第三个位置,结果如左边所示 {-1 -1 0 3 2 1} -8 拿第一个位置的值-1和-8比较，发现比-8大，那么就把第一个位置 的值-1赋给第二个位置,结果如左边所示 {-8 -1 0 3 2 1} -8 这个时候第一个位置 就有可能是我们要找的插入的位置，进一步发现第一种位置前面 没有值了，那么就果断把-8插入到第一个位置，结果如左边所示， 好了本次循环结束 {-8 -1 0 3 2 1} 2 这次把2(数组的第五个位置)拿出来当做要进行往左边插入的值， 但是把2插入到左的什么位置需要通过程序找出来 (左边的值依次和这个值2作比较得出) {-8 -1 0 3 3 1} 2 拿第四个位置的值3和2比较，发现比2大，那么就把第四个位置 的值3赋给第五个位置,结果如左边所示 {-8 -1 0 2 3 1} 2 这个时候第四个位置就有可能是我们要找的插入的位置, 拿第三个位置的值0和2比较，发现比2小， 那么就果断把2插入到第四个位置(再往前就不用比较了,因为顺序已经是排好的), 结果如左边所示 {-8 -1 0 2 3 1} 1 这次把1(数组的第六个位置)拿出来当做要进行往左边插入的值， 但是把1插入到左的什么位置需要通过程序找出来 (左边的值依次和这个值1作比较得出) {-8 -1 0 2 3 3} 1 拿第五个位置的值3和1比较，发现比1大，那么就把第五个位置 的值3赋给第六个位置,结果如左边所示 {-8 -1 0 2 2 3} 1 拿第四个位置的值2和1比较，发现比1大，那么就把第四个位置 的值2赋给第五个位置,结果如左边所示 {-8 -1 0 1 2 3} 1 这个时候第四个位置就有可能是我们要找的插入的位置, 拿第三个位置的值0和1比较，发现比1小， 那么就果断把1插入到第四个位置(再往前就不用比较了,因为顺序已经是排好的), 结果如左边所示 最后插入排序已完成。。。。 ※ 实现代码如下： package com.test.insertsort; /* * 插入排序算法： * 1、以数组的某一位作为分隔位，比如index=1，假设左面的都是有序的. * * 2、将index位的数据拿出来，放到临时变量里，这时index位置就空出来了. * * 3、从leftindex=index-1开始将左面的数据与当前index位的数据（即temp）进行比较，如果array[leftindex]>temp, * 则将array[leftindex]后移一位，即array[leftindex+1]=array[leftindex],此时leftindex就空出来了. * * 4、再用index-2(即leftindex=leftindex-1)位的数据和temp比，重复步骤3， * 直到找到temp){//当比到最左边或者遇到比temp小的数据时，结束循环 array[leftindex+1] = array[leftindex]; leftindex--; } array[leftindex+1] = temp;//把temp放到空位上 } } public static void main(String[] args){ int[] array = {38,65,97,76,13,27,49}; InsertSort is = new InsertSort(array); System.out.println("排序前的数据为："); is.display(); is.doInsertSort(); System.out.println("排序后的数据为："); is.display(); } } 自己思考所写： package com.briup.Abstract; import java.util.Arrays; public class Test { public static void main(String[] args) { int[] array={12,73,45,69,35}; int i,j,temp; for(i=1;i=0;j--) { /* * 第二个for循环 * 将排序对象temp与已排序数组比较 * 当temp比最近左边的数大时（按从小到大循序排列时） * 直接结束本次循环，进行下一个数排序 * 否则比左边这个数小时将这个数后移，腾出这个数的位置 */ if (temp > array[j]) { break; }else{ array[j+1] = array[j]; } } array[j+1]=temp; } System.out.println(Arrays.toString(array)); } } 三种排序汇总： package com.briup.Abstract; import java.util.Arrays; public class A { public int[] array; public A(int[] array){ this.array=array; } //冒泡排序 public void test1() { for(int i=1;i |
图解：根据其原理，我们把该无序数列看成两个部分，我们不难看出图中，首先我们把第一位3看成是有序数列，剩下的作为无序数列，因为要把后面的无序数列中的数插入到前面有序数列，所以依次把后面的数抽出，在前面找到合适位置插入。如图，先抽出44，与前面比较，比3大放在3后面，再抽出38，与前面比较，比44小，比3大，所以插入到3后面。依次类推，直到最后的一个数也插入到前面的有序数列中。
【本文地址】
今日新闻 |
推荐新闻 |