归并排序算法总结

归并排序

//"mergeSort.h"
#pragma once
#ifndef MERGESORT_MERGESORT_H
#define MERGESORT_MERGESORT_H
#include<algorithm>
void mergeSort(int arr[], int n);
void merge(int arr[], int l, int r);

//对arr[l, mid]、arr[mid+1, r]两个区间进行归并
void __merge(int arr[], int l, int mid, int r);
#endif

//"mergeSort.cpp"
#include "mergeSort.h"

void mergeSort(int arr[], int n)
{
	merge(arr, 0, n - 1);
}

void merge(int arr[], int l, int r)
{
	if (l >= r)
		return;
	int mid = l + (r - l) / 2;
	merge(arr, l, mid);
	merge(arr, mid + 1, r);
	__merge(arr, l, mid, r);
}

void __merge(int arr[], int l, int mid, int r)
{
	int *aux = new int[r - l + 1]; //需要开辟一个辅助空间
	for (int i = l; i <= r; ++i)
		aux[i - l] = arr[i];
	//arr[l, mid], arr[mid+1, r]
	int i = l, j = mid + 1; //要格外注意这些地方的下标问题
	for (int k = l; k <= r; ++k)
	{
		if (i > mid)
		{
			arr[k] = aux[j-l];
			++j;
		}
		else if (j > r)
		{
			arr[k] = aux[i-l];
			++i;
		}
		else if (arr[i] < arr[j])
		{
			arr[k] = aux[i-l];
			++i;
		}
		else
		{
			arr[k] = aux[j - l];
			++j;
		}
	}
}