[C++知识库]C++，合并区间

#include<iostream>
using namespace std;
typedef struct
{
	int min;//区间的最小值(interval minimum
	int max;//区间最大值(interval maximum)
}section;
void Sort(section sect[],int length)//对区间进行排序(sort intervals)
{
	if (length <= 1)
		return;
	//使用哈希排序（use hash sort)
	int d = length / 2;
	for (; d > 0; d = d / 2)
	{
		for (int i = d; i < length; ++i)
		{
			section temp = sect[i];
			int j = i - d;
			for (; j >= 0 && sect[j].min > temp.min; sect[j + d] = sect[j], j = j - d);
			sect[j + d] = temp;
		}
	}
}
void Output(section sect[],int length)
{
	if (length <= 0)
		return;
	
	for (int i = 0; i < length; ++i)
	{
		cout << "[" << sect[i].min << "," << sect[i].max << "]" << "\t";
	}
}
void Merge(section sect[], int &length)
{
	if (length <= 1)
		return;
	int count = 0;//记录区间减少的长度（reduced length of recording interval)
	for (int i = 0; i < length-count-1;)
	//所有元素的都有前移了，真正要用的数组长度也应改变
	//第三第四位数据一样避免死循环所以，在用的长度减一
	{
		if (sect[i].max < sect[i + 1].min)//证明没交集（prove no intersection)
		{
			cout << "[" << sect[i].min << "," 
				<< sect[i].max << "]  [" 
				<< sect[i + 1].min << "," 
				<< sect[i + 1].max << "]无交集" << endl;
			++i;
		}
		else
		{
			cout << "[" << sect[i].min << ","
				<< sect[i].max << "]  ["
				<< sect[i + 1].min << ","
				<< sect[i + 1].max << "]有交集" << endl;
			sect[i].min = sect[i].min < sect[i + 1].min ? sect[i].min : sect[i + 1].min;
			sect[i].max = sect[i].max < sect[i + 1].max ? sect[i + 1].max : sect[i].max;
			//合并区间后相当于区间个数减少一个，数组往前移
			++count;
			for (int j = i + 1; j < length - count;sect[j]=sect[j+1], ++j);//不能跳到j=3因为这样会将j=4的数据赋予j=3的位置有越界

		}
		
	}
	length = length - count;
}
int main()
{
	section sect[4] =
	{
		1,3,
		10,16,
		8,10,
		15,18
	};
	int length = 4;
	Sort(sect, length);
	Merge(sect, length);
	Output(sect, length);
}