排序—-折半插入排序

排序—-折半插入排序折半插入排序(BinaryInsertionSort)是对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。排序思想:有一组数据待排序,排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据,第一次排序时默认Array[0]为有序数据,Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low,最后一…

大家好,欢迎来到IT知识分享网。

折半插入排序(Binary Insertion Sort)是对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。

排序思想:有一组数据待排序,排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据,第一次排序时默认Array[0]为有序数据,Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low,最后一个元素的位置为high。

 

遍历无序区间的所有元素,每次取无序区间的第一个元素Array[i],因为0~i-1是有序排列的,所以用中点m将其平分为两部分,然后将待排序数据同中间位置为m的数据进行比较,若待排序数据较大,则low~m-1分区的数据都比待排序数据小,反之,若待排序数据较小,则m+1~high分区的数据都比 待排序数据大,此时将low或high重新定义为新的合适分区的边界,对新的小分区重复上面操作。直到low和high 的前后顺序改变,此时high+1所处位置为待排序数据的合适位置。

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

稳定性:稳定。

#include<stdio.h>
#include<stdlib.h>

int *Array;              /*Array是一个int 型地址,指向数组的首地址。*/
int Count;               /*Count用来存储所要排序的数字的数目。*/

/*建立未排序数组*/
void CreateArray()
{
	int i;

    /*创建数组必须用常量分配,而我们事先并不知道要处理的数据个数,所以用malloc动态分配数组单元。*/
	Array = (int *)malloc(sizeof(int)*Count);   
	
	for (i = 0; i < Count; i++)
	{
		printf("Please enter an integer of NO.%d to sort:\n",i+1);
	    scanf("%d",&Array[i]);
	}
}

/*输出已排序数组*/
void Print()
{
	int i;
	for (i = 0; i < Count; i++)
	{
		printf(" %d ",Array[i]);
	}
	printf("\n");
}

/*折半插入排序升序排列*/
void BinaryInsertSortup()
{
	int i,j,x,m;      /*i,j均为循环变量,x用来存储当前待排序的数据,m充当比较区间的中点*/
	int low,high;     /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。
	                    high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/
	for (i = 1; i < Count; i++)
	{
		x = Array[i];
		low = 0;      /*第一次划分有序比较区间,比较区间的第一个元素所在位置为0*/
		high = i-1;   /*第一次划分有序比较区间,比较区间的最后一个元素所在位置为n-1*/
		/*比较查找Array[i]合适插入的位置*/
		while (low <= high)
		{
			m = (low + high)/2;
			if (x >= Array[m])
			{
				low = m+1;
			}
			else
			{
				high = m-1;
			}
		}
		/*确定好位置后,将位置之后的数据后移,插入待排序数据*/
		for (j = i-1;j > high; j--)
		{
			Array[j+1] = Array[j];
		}
		Array[j+1] = x;
	}

}

/*折半插入排序降序排列*/
void BinaryInsertSortdown()
{
	int i,j,x,m;      /*i,j均为循环变量,x用来存储当前待排序的数据,m充当比较区间的中点*/
	int low,high;     /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。
	                    high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/
	for (i = 1; i < Count; i++)
	{
		x = Array[i];
		low = 0;      /*第一次划分有序比较区间,比较区间的第一个元素所在位置为0*/
		high = i-1;   /*第一次划分有序比较区间,比较区间的最后一个元素所在位置为n-1*/
		/*比较查找Array[i]合适插入的位置*/
		while (low <= high)
		{
			m = (low + high)/2;
			if (x <= Array[m])
			{
				low = m+1;
			}
			else
			{
				high = m-1;
			}
		}
		/*确定好位置后,将位置之后的数据后移,插入待排序数据*/
		for (j = i-1;j > high; j--)
		{
			Array[j+1] = Array[j];
		}
		Array[j+1] = x;
	}

}

int main(void)
{
	int i;
	printf("Please enter the number of Numbers to sort:\n ");
	scanf("%d",&Count);
	CreateArray();      /*创建数组用来存储将要排序的数。*/

	/*插入排序法*/
	BinaryInsertSortup();         /*折半插入排序*/
	printf("升序排列\n");
	Print();
	BinaryInsertSortdown();         /*折半插入排序*/
	printf("降序排列\n");
	Print();

	return 0;
}

图示:以i=4时为例:

第一步

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

第二步

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

第三步:

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

第四步:

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

第五步:

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

第六步:

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

第七步:

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

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/14761.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信