【3】算法排序 （折半插入排序） （二分查找）

二分查找

思想:

时间复杂度: O(log2n)

// 二分查找
// 基础版
int BinarySearch(int * a, int l, int h, int find)
{
        // a一定是有序的
        while(l<=h) {
                int mid = (l+h)/2;
                if (a[mid]==find) {
                        return mid;
                } else if (find < a[mid]) {
                        h = mid - 1;
                } else {
                        l = mid + 1;
                }
        }
        return -1;
}

// 递归法
int BinarySearch2(int * a, int l, int h, int find)
{
        // if not while
        if(l<=h) {
                int mid = (l+h)/2;
                if (a[mid]==find) {
                        return mid;
                } else if (find < a[mid]) {
                        return BinarySearch2(a, l, mid-1, find);
                } else {
                        return BinarySearch2(a, mid+1, h, find);
                }
        }
        return -1;
}

int main()
{
        int a[10] ={1,4,5,6,7,8,12,15,33,39};
        BInsertSort(a, 10);
        int find = BinarySearch(a, 0, 10, 12);
        printf("find=%d
", find);

        int find2 = BinarySearch2(a, 0, 10, 12);
        printf("find2=%d
", find2);
        return 0;
}

折半插入排序（二分排序）

思想：　　

　　  在插入第i个元素时，对前面0 ~ i-1元素进行折半，先跟他们中间的那个元素比较，
         如果小了，则对前半再进行折半，否则对后半部分进行折半处理，直到left>right,然后
         再把第i个元素与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

总结：比较已排序的序列中位数，不必像直接插入排序那样逐一比较，这个中位数将已排序的的部分再进行折半，再进行比较

时间复杂度:

　　O(n^2)

和直接插入排序相比较，折半插入排序仅仅是减少了比较的次数，而移动总次数并没有发生改变。这个比较次数大概是
O(nlogn)
，移动次数没有改变，所以其复杂度和直接插入排序是一样的
O(N^{2})

折半插入排序其实是在直接插入排序的基础上，
结合了二分查找法的思想，顺序的二分查找替代了直接插入排序中遍历查找的过程，
从而更快的能够确定待插入元素的位置，但是由于移动次数并没有发生改变，所以两者的时间复杂度相同。折半插入排序是稳定的，其时间复杂度为O(N^{2})

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print(int * a, int n, int i)
{
        printf("  %d: ", i);
        int j;
        for(j=0; j<n; j++) {
                printf("%d ", a[j]);
        }
        printf("
");
}

void BInsertSort(int * a, int n)
{
        int i, j, l, h, mid, tmp;
        // i=1 元素从第二个开始插入
        // i<n 下标从0开始 最后一个元素下标是n-1
        for(i=1; i<n; i++) {
                l=0;
                h=i-1;
                tmp=a[i]; // 将被插入的元素，即乱序队列的第一个元素
                while(l<=h) {
                        mid=(l+h)/2;
                        if(a[mid]>tmp) {
                                h=mid-1;
                        } else {
                                l=mid+1;
                        }
                }

                for(j=i; j>l; j--) {
                        a[j]=a[j-1];
                }

                a[l]=tmp;
                print(a, n, i);
        }
}

void main()

        int a[8] = {21,3,7,9,39,20,8,4};
        BInsertSort(a,8);
}
~