C语言-数据结构-插入排序及优化-源代码

た入场券 2022-07-11 04:29 197阅读 0赞

**1. 插入排序的定义及复杂度**

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。其时间复杂度为O(n^2)。

**2. 源代码**

运行结果如下图所示。

![Center][]

#include<stdio.h>
    
    void insertsort(int a[], int n)
    {
        int i, j, temp, c1=0;
        for(i=1;i<n;i++)
        {
            if(a[i]<a[i-1])//如果后面出现比前面小的数字
            {
                temp=a[i];
                for(j=i-1;temp<a[j]&&j>=0;j--)//把前面的数字移动，挪出一个合适的位置给a[i]
                {
                    c1++;
                    a[j+1]=a[j];
                }
                a[j+1]=temp;
            }
        }
        printf("总计数据交换%d次\n\n", c1);
    }
    
    int main(void)
    {
        int i;
        int a[10]={1,2,0,3,4,5,6,7,9,8};
        printf("排序前：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        insertsort(a, 10);
        printf("排序后：");
        for(i=0;i<10;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n\n\n");
        return 0;
    }

**3. 折半插入排序**

折半插入排序又叫二分插入排序，其思想是，对于前部分已经排序好的数组，进行折半查找（查找合适的插入位置），这样可以减少比较的次数，但是数据交换的次数并没有减少，所以其时间复杂度仍为O(n^2).

源代码如下：

#include<stdio.h>
    void BInsertSort(int *a, int n)
    {
    	int i, j, m, high, low, temp;//m为折半的中间点下标， low为查找的下边界， high为查找的上边界
    	
    	//从i=1开始，寻找a[i]应该插入的位置，循环结束后，low的值就是a[i]应该放置的位置
    	for(i=1; i<n; i++)
    	{	high=i-1;
    		low=0;
    		while(high>=low)
    		{
    			m=(high+low)/2;
    			if(a[i]>=a[m])//如果a[i]大于等于a[m]，则a[i]应该插入a[m]的右半部分
    			{
    				low=m+1;
    			}
    			else//相反则应插入a[m]的左半部分
    			{
    				high=m-1;
    			}
    		}
    		temp=a[i];//备份a[i]
    		
    		//给a[i]腾位置
    		for(j=i-1; j>=low;j--)//数据交换，将a[low]及之后的数据都向后移动一位，腾出a[low]的位置给a[i]
    		{
    			a[j+1]=a[j];
    		}
    		//a[j+1]=temp;
    		a[low]=temp;
    	}
    }
    
    int main(void)  
    {  
        int i;  
        int a[10]={2,1,0,3,4,5,6,7,9,8};  
        printf("排序前：");  
        for(i=0;i<10;i++)  
        {  
            printf("%d",a[i]);  
        }  
        printf("\n\n\n");  
        BInsertSort(a, 10);  
        printf("排序后：");  
        for(i=0;i<10;i++)  
        {  
            printf("%d",a[i]);  
        }  
        printf("\n\n\n");  
        return 0;  
    }

[Center]: /images/20220711/d10fadd293cd4ddda80bfb3778acbc75.png