插入排序(java实现)

插入排序(java实现)

基础思路:      

      1.将整个数组分为两个分区，left有序区，和right无序区
      2.左分区的数跟右分区一个一个比较，小于左分区，就左分区比较的那个值向后挪动
      3.循环结束证明右分区的值大于左分区，此时leftindex+1才是插入的下标位置

动图演示:

 代码如下:

 public void insert(int nums[]){
        for (int j = 1; j =0 && nums[leftindex]>right){
//            向后挪动,为插入让出位置
                nums[leftindex+1]=nums[leftindex];
//             有序列表向左移动,继续比较
                leftindex--;
            }
//            1,-1,2,4
//            leftindex是要跟右分区比较值的下标,,但是由于要往左边移动,此时+1才是插入的下标
//            优化,如果=j证明插入的位置就是当前位置
            if (leftindex+1!=j){
                nums[leftindex+1]=right;
            }
        }
//        System.out.println(Arrays.toString(nums));
    }

注：上图中right保存了值，因为下面向后挪动会把值给挤掉

优化：当要插入的位置就是当前位置就不要插入

测试:

    int a[] = new int[80000];
        for (int i = 0; i