数据结构-排序-二分法插入排序

数据结构-排序-二分法插入排序

1.算法思想

• 二分法插入排序的思想： 在找第 i 个记录的插入位置时，前 i -1 个记录已排序，将第 i 个记录的排序码与已排序的前 i - 1 个的中间位置记录的排序码作比较，如果第 i 个排序码小于中间记录的排序码，则在前部分继续用二分法进行查找，否则就在后半部分进行用二分法进行查找，直到左边界的排序码小于右边界的排序码，确定第 i 个记录的插入位置。

2.算法复杂度

• 执行时间：插入比较的次数少于最坏情况的直接插入排序，而多于最好情况的直接插入排序，时间复杂度O(n^2)
• 附加空间： 附加的一个空间
• 是否是稳定的排序方法： 是

3.算法实现

#include "stdio.h"

#define MAXSIZE 10
typedef int keytype;

/*二分法插入排序的C语言实现*/

typedef struct {
	keytype key;
}recordtyp;

typedef struct {
	int length;
	recordtyp r[MAXSIZE + 1];//多一个是储存的附加空间
}table;

table * binarysort(table * tab) {

	int i, j, left, right, mid;

	//从第2个到最后一个依次比较
	for (i = 2; i <= tab->length; i++)
	{
		tab->r[0] = tab->r[i];    //将待插入的值存储
		left = 1;                 //初始的左边界是第一个数据
		right = i - 1;           //初始的右边界是 i - 1

	 //当 left>right 时停止循环，查找结束
		while (left <= right)
		{
			mid = (left + right) / 2;//获得中间位置

			if (tab->r[0].key < tab->r[mid].key)
				right = mid - 1;   //如果小于中间位置记录的排序码，则更新右边界
			else
				left = mid + 1;   //如果大于中间位置记录的排序码，则更新左边界
		}
		//找到第 i 个记录合适的位置，从j = left 开始的元素依次右移出一个空位插入
		for (j = i - 1; j >= left; j--)
		{
			tab->r[j + 1] = tab->r[j];//从j = left 开始的元素依次右移出一个空位插入
		}

		tab->r[left] = tab->r[0];//将第 i 个记录插入left位置
	}

	return tab;
}

table * inputData(table * tab) {

	printf("please input the length:\n");
	scanf("%d", &tab->length);

	printf("please input the data:");
	for (int i = 1; i <= tab->length; i++)
	{
		scanf("%d", &tab->r[i].key);
	}
	return tab;
}

void show(table * tab) {

	printf("the result data:");

	for (int i = 1; i <= tab->length; i++)
	{
		printf("%d ", tab->r[i].key);
	}
}

void main() {
	table * tab = malloc(sizeof(table));
	tab = inputData(tab);
	tab = binarysort(tab);
	show(tab);
}

运行截图

欢迎大家关注我的博客：breeziness123
转载说明出处