归并排序

若将两个有序表合并成一个有序表，称为2-路归并。

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

#include<iostream>
using namespace std;
void Merge(int[], int, int[], int, int, int)  
void MergeSort(int numbers[], int length, int temp[], int begin, int end)
{
	//1. 同样判断传入的参数是否有效
	if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
		throw new exception("Invalid input.");
	
	//2. 作为递归的结束条件，开始下标和结束下标相等时，说明子序列中只有一个元素，看作有序的
	if (end - begin == 0)
		return;

	//3. 定义中间变量，将数组分半【如果有7个元素，下标0-6，则middle=3，数组分为长度为4和3的两段】
	int middle = ((end - begin) / 2 ) + begin;
	//4. 递归，先递归左半边，再递归右半边，将左右子序列不断分为长度为1的子序列才停止递归
	MergeSort(numbers, length, temp, begin, middle);
	MergeSort(numbers, length, temp, middle + 1, end);
	//5. 再慢慢归并
	Merge(numbers, length, temp, begin, end, middle);
}

void Merge(int numbers[], int length, int temp[], int begin, int end, int middle)
{
	//1. 判断是否有不符合要求的参数传入，有则抛出错误
	if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
		throw new exception("Invalid input.");

	//2. 将原序列从中分开
	int leftIndex = begin;		//左边序列的开始（左边序列的结尾是middle）
	int rightIndex = middle + 1;//右边序列的开始（右边序列的结尾是end）
	int tempIndex = begin;		//辅助数组的下标
	//3. 当左右子序列尚未到头时，循环
	while (leftIndex <= middle && rightIndex <= end)
	{
		//4. 两两对比判断，谁大谁就放入辅助数组，同时指针后移
		if (numbers[leftIndex] < numbers[rightIndex])
			temp[tempIndex] = numbers[leftIndex++];
		else
			temp[tempIndex] = numbers[rightIndex++];
		//5. 辅助数组下标++
		++tempIndex;
	}

	//6. 当左边或右边子序列尚未到头时，直接放入辅助数组
	while (leftIndex <= middle)
		temp[tempIndex++] = numbers[leftIndex++];

	while (rightIndex <= end)
		temp[tempIndex++] = numbers[rightIndex++];

	//7. 再将辅助数组中已经有序的元素覆盖掉原数组中无序的元素，使原数组变成部分有序
	for (int i = begin; i <= end; ++i)
		numbers[i] = temp[i];
}

int main(int arvc, char* argv[])
{
	const int length = 9;
	int nums[length] = { 18, 7, 23, 3, 9, 32, 10 , 99, 0};
	int *temp = new int[length];

	MergeSort(nums, length, temp, 0, 8);

	for (int i = 0; i < length; i++)
		cout << nums[i] << "  ";

	delete[] temp;
	temp = nullptr;
	cout << endl;
	return 0;
}

希尔排序

希尔排序是对插入排序的一个改进，区别在于，希尔排序可以说是一个不断分组的排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

 //希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap>1)
	{
		//每次对gap折半操作
		gap = gap / 2;
		//单趟排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}
                                          

刷题巩固

三角形最大周长
最大间距
排序数组