算法——插入排序

时间:2021-03-04 11:10:25

   插入排序是最简单的排序算法之一,保证从位置0到p上的元素为已排序状态。

算法——插入排序

上图的p=1是指数据的下标,移动的位置是从位置p往左边移动

看例子: 

public void insetSort(){
        int[] a = {34,8,64,51,32,21};
        System.out.println(Arrays.toString(a));
        int j;
        for (int p = 1; p < a.length ; p++) {
            int tmp = a[p];//记录p位置上的值
            for (j = p; j > 0 && tmp < a[j-1] ; j --) {//循环并比较大于p位置上的值,然后与之调换位置
                a[j] = a[j-1];
            }
            a[j] = tmp;
        }
        System.out.println(Arrays.toString(a));
    }

以p=4趟来结合代码说明:

public void insetSort(){
        int[] a = {8,34,51,64,32,21};//p=4趟之前的数据顺序
        System.out.println(Arrays.toString(a));
        int j;
        for (int p = 1; p < a.length ; p++) {
            int tmp = a[p];//从这里开始说明,这列的tmp等于32,
            //拿32与前面排序好的数组进行比较,
           //第一次比较与交换后的数组是:8,34,51,64,64,21
          //第二次比较与交换后的数组是:8,34,51,51,64,21
         //第三次比较与交换后的数组是:8,34,34,51,64,21
        //第四次发现小于当前下标元素(这里的下标元素是第一个34)了就直接退出循环,然后把p值赋值给当前下标的元素,得出的数组是:8,32,34,51,64,21
       //
            for (j = p; j > 0 && tmp < a[j-1] ; j --) {
                a[j] = a[j-1];
            }
            a[j] = tmp;
        }
        System.out.println(Arrays.toString(a));
    }