插入排序加二分排序详细讲解（附代码）

插入排序：从字义上理解，这是一组不断进行插入的排序，正确! 插入排序其实就是一个插入+顺序部分排序的过程。下面举个例子给讲解一下（从小到大排序）

一个数组：int a[]={1,3,2,7,5,4,8} 是长度为7的数组， 在进行插入排序的过程中呢我们需要循环6次

默认：已排序数组{1}    未排序数组{3,2,7,5,4,8,}

第一次循环：插入a[1]  a[1]>a[0] 已排序数组 {1,3} 未排序数组{2,7,5,4,8}

第二次循环：插入a{2} a[2]<a[1] 向已排序数组中挪到a[1]位置和原a[1]位置交换，再和a[0]比较 a[1]>a[0]，位置保持

                       已排序数组{1,2,3} 未排序数组{7,5,4,8}

以此类推。最后得出有序数组，下面附核心代码

    public static void insertSort(int a[])
    {
        for (int i = 1; i < a.length; i++)
        {
            if (a[i]<a[i-1])
            {
                int temp=a[i];
                int j=i;
                while (j-1>0&&a[j-1]>temp)
                {
                    a[j]=a[j-1];
                    j--;
                }
                //while循环结束后，现在的J位置就是当前插入数字该待的地方！
                a[j]=temp;
            }
        }
    }

从上面得出，如果是一个完全有序的再进行排序，那么时间复杂度最佳：为O(N) ,最糟糕的是完全乱序，那么时间复杂度为 O(N^2);

    public static void halfSort(int a[])
    {
        int start;
        int end;
        int temp=0;
        int mid,j;
        
        for(int i=1;i<a.length;i++)
        {
            start=0;
            end=i-1;
            temp=a[i];

            while(start<=end)
            {
                mid=(start+end)/2;
                if (temp<a[mid])
                {
                    end=mid-1;
                }
                else 
                {
                    start=mid+1;
                }
            }
            
            //while循环完后，start=end+1,此时start为当前插入数字所待坑位！
            //把坑位给当前插入的数据挪出来
            for( j = i-1;j >= start;j-- )
            {
                a[j+1] = a[j];
            }
            //将当前插入数字挪入它该待的坑位
            a[start] = temp;
        }
    }

最后

以上就是欣喜可乐为你收集整理的插入排序加二分排序详细讲解（附代码）的全部内容，希望文章能够帮你解决插入排序加二分排序详细讲解（附代码）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。