折半插入排序法---排序算法(二)

╰+哭是因爲堅強的太久メ 2022-09-17 13:18 142阅读 0赞

#     #

# 1.排序原理 #

折半插入排序法是对直接插入排序法的改进，直接插入排序法([http://blog.csdn.net/whzhaochao/article/details/12953741][http_blog.csdn.net_whzhaochao_article_details_12953741])，是在前面已排好序的序列中顺序查找要插入的位置，折半插入排序法则是用二查找法找到要插入的位置，然后插入。

# 2.代码 #

#include <stdio.h>
    
    void printArray(int a[],int size){  
        printf("数组为：[%d] ",a[0]);  
        for (int i=1;i<size;i++)  
        {  
            printf(" %d ",a[i]);  
        }  
        printf("\n");  
    }
    
    void main()
    {
    	//a[0]为监视哨  
        int a[8]={0,38,65,97,76,13,27,49};  
    
        for (int i=2;i<=7;i++)  
        {  
            printf(" i=%d  ",i);  
            printArray(a,8);  
    //将要插入的数放监视哨
    		a[0]=a[i];
    		int low=1,high=i-1;
    //while循环用二分查找法找到要插入的位置为 high+1
    		while(low<=high){
    			int m=(low+high)/2;
    			if (a[0]<a[m])
    			{
    				high=m-1;
    			}else{
    				low=m+1;
    			}
    		}
    
    		printf("\n%d要插入%d位置",a[0],a[high+1]);
    		if (i-1>=high+1)
    		{
    			printf("\n%d到%d,要向前移一位\n",a[high+1],a[i-1]);
    		}
    	
    //将 high+1到i-1位置数据移到 high+2到i位置		
    		for (int j=i-1;j>=high+1;--j)
    		{
    			a[j+1]=a[j];
    		}
    // high+1插入要插入的数据
    		a[high+1]=a[0];
    
        }  
        printf("结果 ");  
        printArray(a,8);  
    
    }

# 3结果 #

i=2  数组为：[0]  38  65  97  76  13  27  49
    
    65要插入65位置 i=3  数组为：[65]  38  65  97  76  13  27  49
    
    97要插入97位置 i=4  数组为：[97]  38  65  97  76  13  27  49
    
    76要插入97位置
    97到97,要向前移一位
     i=5  数组为：[76]  38  65  76  97  13  27  49
    
    13要插入38位置
    38到97,要向前移一位
     i=6  数组为：[13]  13  38  65  76  97  27  49
    
    27要插入38位置
    38到97,要向前移一位
     i=7  数组为：[27]  13  27  38  65  76  97  49
    
    49要插入65位置
    65到97,要向前移一位
    结果 数组为：[49]  13  27  38  49  65  76  97

[http_blog.csdn.net_whzhaochao_article_details_12953741]: http://blog.csdn.net/whzhaochao/article/details/12953741