文章目录

一、直接插入排序

二、折半插入排序

三、希尔排序

一、 直接插入排序




/*直接插入排序*/

void InsertSort(int A[],int n){
   
	int i,j;
	for(i=2;i<=n;i++){
   
		A[0]=A[i];
		for(j=i-1;A[0]<A[j];j--)
			A[j+1]=A[j];
		A[j+1]=A[0];
	}
}

二、折半插入排序





两者之间可能的不同之处是元素之间的比较次数

/*折半插入排序*/

void BInsertSort(int A[],int n)
{
   
	int i,j;
	int low,high,mid;
	for(i=2;i<=n;i++)
	{
   
		A[0]=A[i];
		low=1;high=i-1;
		while(low<=high){
   
			mid=(low+high)/2;
			if(A[mid]>A[0])
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;j--)
			A[j+1]=A[j];
		A[high+1]=A[0];
	}
}

三、希尔排序

希尔排序组内排序是直接插入排序

/*希尔排序*/

void ShellSort(int A[],int n)
{
   
	for(int dk=n/2;dk>=1;dk=dk/2)
	{
   
		for(int i=dk+1;i<=n;++i)
			if(A[i]<A[i-dk]){
   
				A[0]=A[i];
				for(int j=i-dk;j>0&&A[0]<A[j];j-=dk)
					A[j+dk]=A[j];
				A[j+dk]=A[0];
			}
	}
}