欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 18:25:23
...

折半插入思路:

        在插入A[i]时,A[0],A[1],······A[i-1]已经按排序码升序排好了,在A[k]和A[r]之间采用折半,中间结点为A[k+(r-k)/2]。

        折半:经过一次比较,可以排除一半的记录。把可能插入的区间减少了一半。

        时间复杂度插入排序------折半插入排序。进行遍历的数量级是n,进行比较的数量级是插入排序------折半插入排序

#include<stdio.h>
#include<assert.h>
typedef int ElemType;
struct ForSort
{
	ElemType elem;
};

void BinaryInsertionSort(ForSort *arr,int n)
{
	assert(arr != NULL);
	assert(n > 0);

	int i, k, r;
	ForSort temp;
	for (i = 1; i < n; ++i)
	{

		temp = arr[i];
		k = 0;
		r = i - 1;
		while (k <= r)	//区域左右下标:相遇或者错过
		{
			int m;
			m = k + (r - k) / 2;	/*中间坐标*/
			if(temp.elem<arr[m].elem)
			{
				r = m - 1;		/*在前半部分继续找插入位置*/
			}
			else
			{
				k = m + 1;		/*在后半部分继续找插入位置*/
			}
		}
		
		/*找到了插入位置k*/
		for (r = i; r > k; r--)
		{
			arr[r] = arr[r - 1];
		}
		arr[k] = temp;
	}
}

int main()
{
	ForSort arr[] = { 98,78,76,65,54,32,12 };
	int n = sizeof(arr) / sizeof(ForSort);
	BinaryInsertionSort(arr, n);
	for (int i = 0; i < n; i++)
		printf("%-4d", arr[i].elem);
	return 0;
}
插入排序------折半插入排序
本程序在VS2017下运行通过