折半插入排序顺序结构

水深无声 2022-07-16 13:41 130阅读 0赞

2016年7月28日08:21:18
        折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置
        找到要插入的位置后,将相应的元素插入到该位置即可;
        假设所给的数据为:[67,53,73,21]
        第一趟排序:初始的状态为:[67,|53,73,21]
                    t = 53,在有序子集中min = 0,max = 0;->mid = (min+max)/2 = 0
                    将53与L->data[mid]进行比较->发现53<67;更新有序子集的查找范围:max = mid-1 = -1;
                    ___________________________________________________________________________________
                        注意:假设[67,|67,73,21]
                        t = 67,在有序子集中min = 0,max = 0;->mid = (min+max)/2 = 0
                        将67与67进行比较,发现相等,那么为了排序的稳定性,排序前第二位置的67,在第一个位置前面,
                        排序后它也应该在第一个的前面,
                    _____________________________________________________________________________________
                    发现max<min这时就不能继续查找了,需要查找的位置已经找到,即为min,将min到有序子集
                    的元素向后移动->[67,|67,73,21]
                    将元素插入到min所在的位置:->[53,|67,73,21]
                    同时有序子集的个数增加一个->[53,67|73,21]
        第二趟排序:初始的状态为:[53,67|73,21]
                    t = 73,在有序子集中min = 0,max = 1;->mid = (min + max )/2 = 0;
                    将73与L->data[mid]进行比较->发现73>53;更新有序子集的查找范围:min = mid+1 = 1;中间mid = (min+max)/2 = 1
                    将73与L->data[mid]进行比较->发现73>67;更新有序子集的查找范围:min = mid+1 = 2;发现max<min
                    这时就不用再继续查找了,需要查找的位置已经找到,即为min = 2;
                    这时不用移动有序表表中的元素了,直接将元素插入到它原来的位置;
                    同时有序表子集的个数增加一个->[53,67,73|21]
        第三趟排序:初始的状态为:[53,67,73|21]
                    ______________________________________________________________________________________
                        注意:假设[53,67,73|67]
                        在有序子集中min = 0,max = 2;->mid = (min+max)/2 =1
                        将67和67比较,发现相等,那么那么为了排序的稳定性,排序前第二位置的67,在第一个位置前面,
                        排序后它也应该在第一个的前面,[53,67,73|73]->[53,67,67,73],即令min = mid+1
    
                    ______________________________________________________________________________________
                    t = 21;在有序子集中min = 0,max = 2;->mid = (min + max )/2 = 1;
                    将21与L->data[mid]进行比较->发现21<67;更新有序子集的查找范围:max = mid-1 = 0;中间mid = (min+max)/2 = 0;
                    将21与L->data[mid]进行比较->发现21<53;更新有序子集的查找范围:max = mid-1 = -1;发现max<min
                    这时就不用再继续查找了,需要查找的位置已经找到,即为min = 0;
                    将min及其有序表后面的所有元素都往后移动一个元素的位置;
                    [53,67,73|21]->[53,67,73|73]->[53,67,67|73]->[53,53,67|73]
                    最后将当前的元素插入到min所在的位置;
                    同时有序表子集的个数增加一个->[53,67,73,21|]
                    当未排序的子集中元素为空,算法执行结束;

#include<stdio.h>
    #include<stdlib.h>
    #define MAXISIZE 100
    #define random(x)(rand()%x)
    
    
    //顺序表结构体类型
    typedef struct 
    {
        int data[MAXISIZE];
        int length;
    }SeqList;
    
    //函数前置声明
    void initSeqList(SeqList * S);
    void seqListAssign(SeqList * S);
    void traverseSeqList(SeqList * S);
    void binInsertSort(SeqList * S);
    
    //折半插入排序
    void binInsertSort(SeqList * S)
    {
        int i,j;
        int min,max,mid;
        int tempVal;
        for( i = 1;i<S->length;i++)
        {
            tempVal = S->data[i];
            min = 0;
            max = i-1;
            mid = (min+max)/2;
            while(min<=max)
            {
                if(tempVal<S->data[mid])
                {
                    max = mid-1;
                    mid = (min+max)/2;
                }
                else if(tempVal>=S->data[mid])
                {
                    min = mid+1;
                    mid = (min+max)/2;
                }
                /*else 
                {
                    min = mid +1;
                    break;
                }*/
            }
            for(j = i-1;j>= min;j--)
            {
                /*
                    S->data[i] = S->data[i-1];
                    S->data[i-1] = S->data[i-2];
                    ...
                    S->data[min+1] = S->data[min];
                */
                S->data[j+1] = S->data[j];
            }
            S->data[min] = tempVal; 
            /*for( j = 0;j<=i-1&&min<=max;j++)
            {
                min = j;
                max = i-1;
                mid = (min+max)/2;
                if(tempVal<S->data[mid])
                {
                    max = mid-1;
                }
                else if(tempVal>S->data[mid])
                {
                    min = mid+1;
                }
    
            }*/
            //S->data[min] = tempVal; 
        }
        return;
    }
    
    //初始化顺序表
    void initSeqList(SeqList * S)
    {
        S->length = 0;
        return ;
    }
    
    //给顺序表赋值
    void seqListAssign(SeqList * S)
    {
        int i;
        for(i = 0;i<MAXISIZE;i++)
        {
            S->data[i] = random(100);
        }
        S->length = MAXISIZE;
        return;
    }
    
    //将顺序表中的元素遍历输出
    void traverseSeqList(SeqList * S)
    {
        int i;
        for( i = 0;i<S->length;i++)
        {
            printf("%-6d",S->data[i]);
        }
        printf("\n");
        return ;
    }
    
    //主函数
    int main(void)
    {
        SeqList S;
        initSeqList(&S);
        seqListAssign(&S);
        printf("产生的随机数据为:\n");
        traverseSeqList(&S);
        binInsertSort(&S);
        printf("排序后数据为:\n");
        traverseSeqList(&S);
        return 0;
    }