|
在排序算法中快速排序的效率是非常高的，但是还有种排序算法的效率可以与之媲美，那就是归并排序；归并排序和快速排序有那么点异曲同工之妙，快速排序：是先把数组粗略的排序成两个子数组，然后递归再粗略分两个子数组，直到子数组里面只有一个元素，那么就自然排好序了，可以总结为先排序再递归；归并排序：先什么都不管，把数组分为两个子数组，一直递归把数组划分为两个子数组，直到数组里只有一个元素，这时候才开始排序，让两个数组间排好序，依次按照递归的返回来把两个数组进行排好序，到最后就可以把整个数组排好序；
算法分析
归并排序
是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
基本思路：
先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序；
基本步骤：
1、判断参数的有效性，也就是递归的出口；
2、首先什么都不管，直接把数组平分成两个子数组；
3、递归调用划分数组函数，最后划分到数组中只有一个元素，这也意味着数组是有序的了；
4、然后调用排序函数，把两个有序的数组合并成一个有序的数组；
5、排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，然后把临时数组中的元素都复制到实际的数组中；
实现代码
#include
#define LEN 12 // 宏定义数组的大小
static int tmp[LEN] = {0};// 设置临时数组
// 打印数组
void print_array(int *array)
{
int index = 0;
printf("\narray:\n");
for (; index < LEN; index++){
printf(" %d, ", *(array + index));
}
printf("\n");
}
// 把两个有序的数组排序成一个数组
void _mergeSort(int *array, int start, int middle, int end)
{
int first = start;
int second = middle + 1;
int index = start;
while ((first |