折半插入排序

    添加时间:2013-6-1 点击量:

        只有比别人更早、更勤奋地尽力，才干尝到成功的滋味。              ------麦克马斯特大学训言      



       记得之前总结过插入排序，有爱好的可以看看。


       若是在最错杂的景象下，所要排序的全部数列是逆序的，当第 i-1 趟须要将 第 i 个元素插入前面的 0~ i -1 个元素的序列傍边的时辰，它老是会从第 i -1 个元素开端，逐个斗劲每个元素的大小，直到找到响应的地位。


       这个算法中涓滴没有推敲当要插入第 i 个元素时前面的 0~~ i -1 序列是有序的这个特点。今天要总结的这个算法就充沛的哄骗了这一点。


     


    算法的根蒂根基过程：


       1）策画 0 ~ i-1 的中心点，用 i 索引处的元素与中心值进行斗劲，若是 i 索引处的元素大，申明要插入的这个元素应当在中心值和刚参加i索引之间，反之，就是在刚开端的地位 到中心值的地位，如许很简单的完成了折半；


       2）在响应的半个局限里面找插入的地位时，络续的用（1）步调缩小局限，不绝的折半，局限依次缩小为 1/2  1/4  1/8 .......快速的断定出第 i  个元素要插在什么处所；


       3）断定地位之后，将全部序列后移，并将元素插入到响应地位。


     


    算法实现：



    import java.util.;

    

    public class BinaryInsertSort {

            private static int[] Sort（int[] arr） {

                int i， j;

                //保存中心插入的值

            int Note = 0;

                //将待排序的数列保存起来

            int[] array = arr;

            System.out.println（    开端排序：）;

                for （i = 1; i < array.length; i++） {

                    int low = 0;

                    int high = i - 1;

                Note     = array[i];

                    //络续的折半

                while （low <= high） {

                        //找出中心值

                    int mid = （low + high） / 2;

                        //若是大于中心值

                    if （array[i] > array[mid]） {

                            //在大于中心值的那项目组查找

                        low = mid+1;

                    }     else

                        //在小于中心值的那项目组查找

                        high = mid-1;

                }

                  //将整体数组向后移

                for （ j=i; j > low; j--） {

                    array[j]     = array[j - 1];

                }

                 //插入到指定的地位

                array[low] = Note;

                System.out.println（Arrays.toString（array））;

            }

            System.out.println（    排序之后：）;

            System.out.println（Arrays.toString（array））;

                return array;

        }

    

            public static void main（String[] args） {

            Random random     = new Random（）;

                int[] array = new int[10];

                for （int i = 0; i < 10; i++） {

                array[i]     = Math.abs（random.nextInt（） ％ 100）;

            }

            System.out.println（    排序之前：）;

            System.out.println（Arrays.toString（array））;            

            BinaryInsertSort.Sort（array）;

        }

    }


     


     输出截图：



    算法解析：


       1）时候错杂度：


       折半插入排序比直接插入排序明显削减了关键字之间的斗劲次数，然则移动次数是没有改变。所以，折半插入排序和插入排序的时候错杂度雷同都是O（N^2），在削减了斗劲次数方面它确切相当优良，所以该算法仍然比直接插入排序好。


       2）空间错杂度：


       折半插入排序和插入排序一样只须要一个多余的缓存数据单位来放第 i 个元素，所以空间错杂度是O（1），因为排序前2个相等的数在序列的前后地位次序和排序后它们两个的前后地位次序雷同，所以它是一个稳定排序。 


     

    读书，不要想着实用，更不要有功利心。读书只为了自身的修养。邂逅一本好书如同邂逅一位知己，邂逅一个完美之人。有时心生敬意，有时怦然心动。仿佛你心底埋藏多年的话，作者替你说了出来，你们在时光深处倾心相遇的一瞬间，情投意合，心旷神怡。
    分享到：