插入排序的代码实现

插入排序是排序算法中较为基础的排序算法。本人对插入排序的理解为：

存在一个数组，数组中存放着N个无序数。

实现：

        将这一数组分为两部分，第一部分是有序的，第二部分是无序的。

        排序第一趟：将原数组中第一个数当做有序部分第一个数，将剩下的数组元素当做无序部分的元素，然后从无序部分中拿取第一个元素插入到有序部分中合适的位置构成新的有序部分，此时有序部分共有两个元素；

        排序第二趟：将第一趟排好的有序部分作为第二趟的初始有序部分，此时有序部分共有两个元素，然后从无序部分中取第一个元素插入到有序部分合适的位置，构成新的有序部分，此时有序部分共有三个元素；

        排序后面几趟以此类推，直到无序部分没有元素为止。

时间复杂度理解：

        假设将数组中的每一个数对应二维表中的每一列，那么这个列表有N列，排序的每一趟当做列表中的每一行，那么这个列表有N-1行。之所以只有N-1行是因为第一个元素是默认有序元素，当N-1个数字（其实就是最后一个元素）排序完毕整个排序就完成了。因此插入排序就够成了一张N*（N-1）的表格。由此可以看出从排序第一趟第一个数走到排序最后一趟（即N-1趟）最后一个数（第N个数），程序的时间复杂度为N^2-N.利用大O记法，可以记O(N^2),由此可知选择排序比较适用于数据量较小的双层循环。

以下是插入排序的java语言实现

public class sort02 {
    public static void main(String[] args) {
        int[] a={0,3,5,9,1,7,8,4,2};
        System.out.println("排序前：");
        show(a);
        System.out.println(" ");
        int[] b=sort(a);
        System.out.println("排序后");
        show(b);
    }

    private static int[] sort(int [] a) {
        for (int i = 0; i < a.length-1; i++) {//排的趟数
            for (int j = i; j >0; j--) {//每趟排的元素
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        return a;
    }

    public static void show(int[] a){
        for(int i=0;i

运行结果如下：

相关排序：

冒泡排序的代码实现_lixxkv的博客-CSDN博客

选择排序的代码实现_lixxkv的博客-CSDN博客

以上是本人对插入排序算法的个人理解，不喜勿喷，谢谢理解。