内部排序算法汇总<一>（二分排序）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

1.二分排序也叫折半插入排序，是直接插入排序的一种改进，查找插入位置的时候利用了二分查找算法，从而减少了比较和移动这两种操作的次数。实现代码如下：

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


/*****************************************************************

 *功能描述：二分排序（折半排序）算法

 *传入参数：num：需要排序的数组首地址， n:数组的元素

 *传出参数：num：排序后的数组首地址，传入参数和传出参数空间复用，降低空间复杂度

 *返回值： 无

 ****************************************************************/


void B_insert_sort(int *num, int n)
{
    int tmp, i, j, low, high, m;

    /*判断参数的合法性，当指针为空或者数组中只有一个元素时，直接返回*/
    if((num == NULL) || (n<2))
    {
        return;
    }

    /*把第一个节点当成有序表，将第二个节点插入到这个表中，    有序表
    更新为两个    节点的表，把后面的节点逐个插入到不断更新的有序表中*/
    for(i=1; i<n; i++)
    {
        tmp = num[i];
        low = 0;
        high = i-1;

        /*二分查找算法：当下界low大于上界时，能够确定插入元素的位置为high+1,因为上界的
        最后一次更新是tmp <= num[m],num[m]存放的是比tmp大并且最接近tmp的数，tmp插入到
        num[m]的位置是最适合的，此处的m=high+1*/
        while(low<=high)
        {
                m = (low+high)/2;
                if(tmp <= num[m])
                {
                    high = m - 1;
                }
                else
                {
                    low = m + 1;
                }
        }

        /*由于程序是将num[i]插入到含i个元素（num[0]--num[i-1]）的有序表中，前面已经将
        num[i]的值保存在临时变量中，在找到插入的位置后，将插入位置及后面的元素均往后移
        一位，把high+1位置腾出来放待插入元素num[i]*/
        for(j=i-1; j>=high+1; j--)
        {
            num[j+1] = num[j];
        }
        num[high+1] = tmp;
        /* 因为while退出条件为low>high，其变化量均为1，退出循环时必为low=high+1,每次查找
         完毕后，low总比high大一，num[low]总是存放第一个比tmp大的数,因此亦可以用下面的一段程序
         替代上面的代码
           for(j=i-1; j>=low; j--)           {               num[j+1] = num[j];           }           num[low] = tmp;
        */
    }

    return;
}

int main(void)
{
    int i;
    int num[5] = {5, 4, 3, 2, 1};

    printf("before:\n");
    for(i=0; i<5; i++)
    {
        printf("num[%d]:%d\n", i, num[i]);
    }

    B_insert_sort(num, 5);

    printf("after:\n");
    for(i=0; i<5; i++)
    {
        printf("num[%d]:%d\n", i, num[i]);
    }

    return 0;
}