插入排序2------折半插入排序

算法思想：（看完这个，看程序应该能看懂）

假设：A序列无序，B序列有序（升序），从A序列依次取出元素（x）与B序列位于中间位置的元素(temp)进行大小比较.

      1.如果x>temp，则取temp与序列末尾之间的中间元素进行比较，

      2.如果x<temp，则取序列首部与temp之间的中间元素进行比较，

      3.在1、2步骤间循环比较。每一次比较后都缩小了元素在B序列中的比较区间，最终确定插入位置。

      4.结果1：直到找到一元素比它次小，则插入其后。

程序实例

#include<stdio.h>

//arr2[]为以排好序的序列，K2为已排好序列的元素个数 
void dichotomy(int arr1[],int arr2[],int k1,int k2)
{
	int i,j,temp,mid;
	int head=0;//将头标志元素序号置为序列头 
	int tail=k2-1; //将尾标志元素序号置为序列末 
	for(i=0;i<k1;i++)
	{
		
		while(head<=tail) //当头标志小于等于尾标志时表示还没找到合适的插入位置， 
		{
			mid=(head+tail)/2;//取头尾标志中间的那个元素 
			if(arr1[i]<arr2[mid]) //因为 arr1[i]<arr2[mid]，所以arr1[i]元素应该head-mid中继续查找，所以改变tail=mid-1;; 
			{
				tail=mid-1;
			}
			else if(arr1[i]>arr2[mid])//因为 arr1[i]>arr2[mid]，所以arr1[i]元素应该mid-tail中继续查找，所以改变head=mid+1; 
			{
				head=mid+1;	
			}
			else// arr1[i]==arr2[mid],跳出循环,元素将插到mid后面，这里修改了tail的值为mid，是因为方便程序。 
			{
				tail=mid;
				break;
			}
		}
		
		for(j=k2;j>tail+1;j--)//将tail后的元素后移， 
		{
			arr2[j]=arr2[j-1];
		} 
		arr2[tail+1]=arr1[i];//插入元素 
		k2++; //已排好序列元素个数+1 
		head=0;//头标志变为0； 
		tail=k2-1;//为标志指向序列末 
	} 
	
	//输出已排好的序列的arr2[] 
	for(i=0;i<k2;i++)
	{
		printf("%d ",arr2[i]);
	} 
} 

//在原始数组上进行排序操作
void dichotomy2(int arr[],int k)
{
	int i,j,temp,mid;
	for(i=1;i<k;i++) 
	{
		int head=0;//将头标志元素序号置为序列头 
		int tail=i-1; //将尾标志指向带比较元素前的元素位置 
		while(head<=tail) //当头标志小于等于尾标志时表示还没找到合适的插入位置， 
		{
			mid=(head+tail)/2;//取头尾标志中间的那个元素 
			if(arr[i]<arr[mid]) //因为 arr1[i]<arr2[mid]，所以arr1[i]元素应该head-mid中继续查找，所以改变tail=mid-1;; 
			{
				tail=mid-1;
			}
			else if(arr[i]>arr[mid])//因为 arr1[i]>arr2[mid]，所以arr1[i]元素应该mid-tail中继续查找，所以改变head=mid+1; 
			{
				head=mid+1;	
			}
                        else{  //arr1[i]==arr2[mid]结束循环，插入到该位置后。
                              tail=mid;
                                break;
                        }
		}
		temp=arr[i];//需要把待插入的元素存起来 

		for(j=i;j>tail+1;j--)//将tail后的元素后移， 
		{
			arr[j]=arr[j-1];
		} 
		arr[tail+1]=temp;//插入元素 
	} 
	//输出已排好的序列的arr2[] 
	for(i=0;i<k;i++)
	{
		printf("%d ",arr[i]);
	} 
} 


int main(){
	int arr1[10]={10,7,8,6,5,4,2,3,1,9};
	int arr2[50];
	arr2[0]=1;
	arr2[1]=2;
	arr2[2]=4;
	//dichotomy(arr1,arr2,10,3);//两个数组的排序操作
	dichotomy2(arr1,10); //在原始数组上进行排序操作
}

算法分析：

时间复杂度：O(n^2)

空间复杂度：O(1)

最好情况为：O(nlog2 n)

最后

以上就是能干毛衣为你收集整理的插入排序2------折半插入排序的全部内容，希望文章能够帮你解决插入排序2------折半插入排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。