C/C++语言重温------排序之归并排序

#include

using namespace std;

// 模板获取数组长度的方法
template 

int getSize(T(&input)[N]) {
	return sizeof(input) / sizeof(T);
}

// 定义数组长度为全局变量
int arr_length = 0;

// 输出数组
void display_arr(int *arr) 
{

	for (int i = 0; i < arr_length; i++)
	{
		cout << "arr[" << i << "]:" << arr[i] << endl;
	}
}



// 归并排序递归函数主体
void merge_sort_recursive(int arr[], int arrCopy[], int start, int end) {
	

	if (start >= end)
		return;

	int len = end - start, mid = (len >> 1) + start;
	// 左半边数组起止位置
	int leftStart = start, leftEnd = mid;
	// 左半边数组起止位置
	int rightStart = mid + 1, rightEnd = end;

	// 左半边数组排序
	merge_sort_recursive(arr, arrCopy, leftStart, leftEnd);
	// 右半边数组排序
	merge_sort_recursive(arr, arrCopy, rightStart, rightEnd);

	int k = start;

	// 先比较两个数组，进行排序
	while (leftStart <= leftEnd && rightStart <= rightEnd) 
	{
		arrCopy[k++] = arr[leftStart] < arr[rightStart] ? arr[leftStart++] : arr[rightStart++];
	}

	// 接着将左边剩余元素或右边剩余元素放到数组尾部
	while (leftStart <= leftEnd)
	{
		arrCopy[k++] = arr[leftStart++];
	}

	while (rightStart <= rightEnd)
	{
		arrCopy[k++] = arr[rightStart++];
	}

	// 将排序好的数组复制给原数组
	for (k = start; k <= end; k++)
		arr[k] = arrCopy[k];
}


void merge_sort(int arr[], const int len) {

	// 开辟存放数组的空间
	int* arrCopy = (int*)malloc(len * sizeof(arr[0]));

	// 递归函数排序
	merge_sort_recursive(arr, arrCopy, 0, len - 1);
}


int main(int argc, char const *argv[])
{
	int arr[]  = { 5, 6, 1, 9, 2, 4, 3, 7, 10, 8 };

	arr_length = getSize(arr);

	display_arr(arr);
	
	// 归并排序
	merge_sort(arr, arr_length);

	display_arr(arr);

	return 0;
}