C实现折半插入排序

短命女 2022-07-16 17:17 169阅读 0赞

算法思想：将排序的记录放入数组original\[1-n\]中，original\[1\]是有序的，再循环n-1次，将后面的n-1个记录一次插入有序数组的正确位置形成一个有序的数组，而折半插入的做法是将待插入的记录和排好的有序数列的中间记录做比较，选择插入有序数列的左子表或右子表，直到找到正确的插入位置。

时间复杂度：O(n^2)  
空间复杂度：O(1) (数组的第一位用来存待插入的记录)

算法特点：合理利用数组的特点，即通过下标查找元素，而链表则做不到。在处理数据多而无序时，效率明显高于直接插入排序。

#include<stdio.h>
    int* BInsertionSort(int original[],int length)
    {
        int i,j;
        int beginposition,endposition;//定义有序数列的起始位置和尾部位置
        int mid;//定义有序数列的中间位置
        for(i=2;i<=length;i++)//从数组的第二个数据开始处理
        {
            beginposition=1;
            endposition=i-1;
            original[0]=original[i];//将待插入的元素存到数组0号位置
            while(beginposition<=endposition)
            {
                mid =(beginposition+endposition)/2;
                if(original[i]<original[mid])//如果待插入的元素小于有序数列的中间位置的值
                        endposition=mid-1;//那么插入位置在前面的子表，改变尾部位置
                    else
                        beginposition=mid+1;//否则插入位置在后面的子表，改变起始位置
            }
            for(j=i-1;j>=endposition+1;j--)//插入位置为endposition+1
            {
                original[j+1]=original[j];//将插入位置后面的元素依次后移一位，腾出插入位置
            }
            original[endposition+1]=original[0];//将带插入的元素插入到正确的插入位置
        }
        return original;
    }
    int main()
    {
    
        int *original;
        int paixu[100]={
       0};
        original=new int[100];
        int i,n;
        paixu[0]=0;
        for(i=1;i<100;i++)
        {
            scanf("%d",&paixu[i]);
            if(getchar()=='\n')
                break;
            else
                continue;
        }
        n=i;
        original=BInsertionSort(paixu,n);
        printf("排序后的结果：\n");
    
        //输出排序后的数组
        for(i=1;i<=n;i++)
        {
            printf("%d ",original[i]);
        }
        printf("\n");
        delete []original;
        return 0;
    }

在CB下运行成功。  
![这里写图片描述][SouthEast]

注意事项：代码使用了new和delete，不过好像也没有使用的必要，如果按源码运行，请保存.cpp。

心得：数据结构是很重要的东西，以前从来没有重视，老师讲算法，我觉得挺简单的。没想到去实现却遇到了不少的困难，可能是C语言基础太差了。首先，int型数组的输入如何结束，我也不太明白，百度了getchar()的原理和作用，才得以解决。  
折半插入排序这些虽然简单，但是新手不要觉得简单想想就行了，编程需要动手，先要去草稿本画出数据的移动，位置的变动，循环的起始点结束点，这些不是想想能解决的，大神也是一点一点的积累才有熟练运用的技巧。共勉！

[SouthEast]: /images/20220709/eef7fe5ecfad4c4ab3190be0ea9adc3b.png