数据结构与算法 ——快速排序

归并排序

一、概念

基础概念：归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

通俗理解：

1. 首先先将一个数组按长度大小进行等分成两个小数组（mid = (left + right) / 2）
2. 然后在递归的把这两个子数组进行等分，直到等分出来的数组长度为1
3. 再一次向上对等分的数组进行排序，直到整个数组有序

二、代码及过程

/**
*
*归并排序
*Date:2019年5月2日
*
***/
#include <stdio.h>
#include <stdlib.h>

// 合并子序列
void mergeArr(int *a,int left,int right,int mid){
	int i,j;
	int k = 0;
	int *temp = (int *)malloc(sizeof(int) * (right - left + 1));

	for(i = left,j = mid + 1; i <= mid && j <= right;){
		a[i] > a[j] ? temp[k++] = a[j++] : temp[k++] = a[i++];
	}

	while(i <= mid){
		temp[k++] = a[i++];
	}

	while(j <= right){
		temp[k++] = a[j++];
	}

	// 将temp中的数据覆盖到原数组中
	for(i = 0; i < k; i++){
		a[left + i] = temp[i];
	}
}

// 归并排序
void mergeSort(int *a,int left,int right){
	if(a == NULL || left >= right){
		return;
	}

	int mid = (left + right) / 2;
	mergeSort(a,left,mid);
	mergeSort(a,mid+1,right);
	// 合并子序列
	mergeArr(a,left,right,mid);
}

void show(int *a,int n){
	int i;
	for(i = 0; i < n; i++){
		printf("%3d",a[i]);
	}
}

void main(){
	int a[] = {21,25,49,25,16,-8,10};
	int n = sizeof(a) / sizeof(a[0]);
	printf("\n排序前：\n");
	show(a,n);
	// 归并排序
	mergeSort(a,0,n-1);
	printf("\n排序后：\n");
	show(a,n);
	printf("\n");
}

三、复杂度

平均时间复杂度： O(nlogn)
空间复杂度： O(n)