排序算法之折半插入排序

1 、介绍。

将直接插入排序中寻找A[i] 的插入位置的方法改为采用折半比较，即可得到折半插入排序算法。在处理 A[i] 时， A[0] …… A[i-1] 已经按关键码值排好序。所谓折半比较，就是在插入 A[i] 时，取 A[i-1/2] 的关键码值与 A[i] 的关键码值进行比较，如果 A[i] 的关键码值小于 A[i-1/2] 的关键码值，则说明 A[i] 只能插入 A[0] 到 A[i-1/2] 之间，故可以在外汇返佣http://www.kaifx.cn/ A[0] 到 A[i-1/2-1] 之间继续使用折半比较；否则只能插入 A[i-1/2] 到 A[i-1] 之间，故可以在 A[i-1/2+1] 到 A[i-1] 之间继续使用折半比较。如此担负，直到最后能够确定插入的位置为止。一般在 A[k] 和 A[r] 之间采用折半，其中间结点为 A[k+r/2] ，经过一次比较即可排除一半记录，把可能插入的区间减小了一半，故称为折半。执行折半插入排序的前提是文件记录必须按顺序存储。  

折半插入排序是稳定排序，不需要额外内存，空间复杂度O(1) 。时间复杂度，最佳情况： O(n^2)   最差情况： O(n^2)   平均情况： O(n^2) 。

2 、步骤。

跟直接插入排序的步骤相似，只不过查找插入点的方法不一样。直接插入排序是从有序区的最后一个数依次向前找，而折半插入排序是通过折半的方式进行查找。

(1) 计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入 i 索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；

(2) 在相应的半个范围里面找插入的位置时，不断的用（ 1 ）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 ……. 快速的确定出第 i 个元素要插在什么地方；

(3) 确定位置之后，将整个序列后移，并将元素插入到相应位置。

3 、代码。

public static void main(String[] args) {

        System.out.println(“—— 开始 ——“);

        // 生成生成两份随机数组，其中用系统自带的方法进行排序，到时候进行验证。

        final int number = 100000;

        int[] sortArray = new int[number];

        int[] sortArrayCopy = new int[number];

        for (int i = 0; i < sortArray.length; i++) {

            sortArray[i] = (int) (Math.random() * number);

        }

        System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);// 数组复制

        Arrays.sort(sortArrayCopy);

        // 开始排序

        long startTime = System.currentTimeMillis();

        halveInsertSort(sortArray);// 折半插入排序

        System.out.println(” 花费时间： ” + (System.currentTimeMillis() – startTime));

        // 跟系统排序之后数组进行比较，查看是否排序成功。

        if (Arrays.equals(sortArray, sortArrayCopy)) {

            System.out.println(” 排序成功 “);

        } else {

            System.out.println(” 排序失败 “);

        }

        System.out.println(“—— 结束 ——“);

    }

// 折半插入排序 最佳情况： T(n) = O(n)    最坏情况： T(n) = O(n2)    平均情况： T(n) = O(n2)

private static void halveInsertSort(int[] array) {

    int flag;

    int low, middle, high;

    for (int i = 1; i < array.length; i++) {//n-1 轮

        flag = array[i];

        low = 0;

        high = i – 1;

        while (low <= high) {// 最后的情况就是 low==high==middle 的判断

            middle = (low + high) / 2;

            if (array[i] > array[middle]) {

                low = middle + 1;

            } else {

                high = middle – 1;

            }

        }

        for (int j = i; j > high + 1; j–) {

            array[j] = array[j – 1];

        }

        array[high + 1] = flag;

    }

}

public class InsertSort {

    /* 使用折半插入法进行排序 */

    public static void main(String[] args) {

        int array[]=new int[]{9,8,7,6,5,4,3,2,1};  // 把待排序的数存放在数组中

        int i,j,temp;

        int low,high,mid;

        for(i=1;i<array.length;i++){// 需要进行 n-1 趟插入排序

            temp=array[i];

            low=0;

            high=i-1;

            while(low<=high){  // 折半查找插入位置

                mid=(low+high)/2;

                if(array[mid]>temp){

                    high=mid-1;

                }else{

                    low=mid+1;

                }

            }

            for(j=i-1;j>=low;j–){   // 后移

                array[j+1]=array[j];

            }

            array[low]=temp;  // 插入

        }

        for(i=0;i<array.length;i++){

            System.out.print(array[i]+” “);

        }

    }

}

类型定义头文件

 #define MAXSIZE 20 /* 一个用作示例的小顺序表的最大长度 */

 typedef int InfoType; /* 定义其它数据项的类型 */

 typedef int KeyType; /* 定义关键字类型为整型 */

 typedef struct

 {

   KeyType key; /* 关键字项 */

   InfoType otherinfo; /* 其它数据项，具体类型在主程中定义 */

 }RedType; /* 记录类型 */

 typedef struct

 {

   RedType r[MAXSIZE+1]; /* r[0] 闲置或用作哨兵单元 */

   int length; /* 顺序表长度 */

 }SqList; /* 顺序表类型 */

函数文件

void BinInsertSort(SqList *L)

/* 折半插入排序 */

{

    int i,j,mid,low,high;

    DataType t;

    for(i=1;i<L->length;i++)        /* 前 i 个元素已经有序，从第 i+1 个元素开始与前 i 个的有序的关键字比较 */

    {

        t=L->data[i+1];             /* 取出第 i+1 个元素，即待排序的元素 */

        low=1,high=i;

        while(low<=high)            /* 利用折半查找思想寻找当前元素的合适位置 */

        {

            mid=(low+high)/2;

            if(L->data[mid].key>t.key)

                high=mid-1;

            else

                low=mid+1;

        }

        for(j=i;j>=low;j–)     /* 移动元素，空出要插入的位置 */

            L->data[j+1]=L->data[j];

        L->data[low]=t;         /* 将当前元素插入合适的位置 */    

    }

}

主程序

 #define LT(a,b) ((a)<(b))

 #define N 8

 void print(SqList L)

 {

   int i;

   for(i=1;i<=L.length;i++)

     printf(“(%d,%d)”,L.r[i].key,L.r[i].otherinfo);

   printf(“\n”);

 }

 void main()

 {

   RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};

   SqList l;

   int i;

   for(i=0;i<N;i++) /* 给 l1.r 赋值 */

     l1.r[i+1]=d[i];

   l.length=N;

   printf(” 排序前 :\n”);

   print(l);

   BInsertSort(&l);

   printf(” 折半插入排序后 :\n”);

   print(l);

 }