Java插入排序法

大家好，欢迎来到IT知识分享网。

本人学生党一枚。Java学习过程，写这个博客纯属当复习，有什么错误的地方请大家指出来在评论里指点指点我。谢谢

概念:

插入排序法是插入式排序法的一种。
基本思想是：把n个待排序的元素看成一个有序表和无序表。一开始有序表只包含一个元素，无序表中包含n-1个元素。排序过程中每次从无序表中取出第一个元素，把它依次与有序表中的元素进行比较。然后把它插入到有序表的适当位置，形成新的有序表。
通俗的讲：假设第一个元素是有序的，后面的元素往前插入，依次进行比较，小的往前挪，大的往后挪，找到合适的位置插入。打个形象的比方就是打扑克牌时的摆牌。

插入过程：

思路：

1：外层循环：因为第一个是有序的，所以不用参与插入，所以从arr[i] 开始。
2：设置插入的数由上面可得出 从 arr[i] 开始。
3：设置被插入数的下标，往前插所以是 i – 1。
4：内层循环：如果插入的数比被插入的数小，就要把被插入的数向后移，插入的数向前移 index–就退出了循环。
5：当不满足循环条件后就找到了合适的位置插入。

代码：

package com.test_1;

import java.util.Calendar;

public class Demo5_3 { 
   

    public static void main(String[] args) {

        //构建一个庞大的无序数组用于测试时间
        int len=10;
        int arr1 [] = new int [len];
        for(int i=0;i<len;i++){
            //让程序随机产生一个1~10000的数
            //Math.random()会产生一个0~1的数
            int t = (int)(Math.random()*len);
            arr1[i] = t;
        }

        //插入排序法
        InsertSort iSort = new InsertSort();
        iSort.sort(arr1);
    }

}


class InsertSort { 
   
        public void sort(int arr[])
        {
            for(int i =1; i<arr.length;i++)
            {
                //插入的数
                int insertVal = arr[i];
                //被插入的位置(准备和前一个数比较)
                int index = i-1;
                        //如果插入的数比被插入的数小
                        while(index>=0&&insertVal<arr[index])
                        {
                            //将把arr[index] 向后移动
                            arr[index+1]=arr[index];
                            //让index向前移动
                            index--;
                        }
                        //把插入的数放入合适位置
                arr[index+1]=insertVal;
            }

            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }

        }
}

效率：

优于冒泡排序法，优于选择排序法。低于快速排序法。详情自己测试就好。