归并排序

归并排序将两个有序的序列合并成一个有序的序列。如何得到两个有序的序列，把数据不停的拆分，拆到每个序列只有一个数据。所以归并排序用到了递归思想。

代码

#include <stdio.h>
#include <stdlib.h>//两个有序的序列合并成一个有序的序列
void Merge(int *a, int start, int mid, int end)
{int LeftLen = mid - start + 1;int RightLen = end - mid;int *L = (int *)malloc(sizeof(int) * LeftLen);int *R = (int *)malloc(sizeof(int) * RightLen);int i, k, j;for (i = 0, k = start; i < LeftLen; i++, k++){L[i] = a[k];}for (j = 0; j < RightLen; j++, k++){R[j] = a[k];}for (i = 0, j = 0, k = start; i < LeftLen && j < RightLen; k++){if (L[i] < R[j]){a[k] = L[i++];}else{a[k] = R[j++];}}if (j < RightLen){for (; j < RightLen; j++, k++){a[k] = R[j];}}if (i < LeftLen){for (; i < LeftLen; i++, k++){a[k] = L[i];}}
}void MergeSort(int *a, int start, int end)
{if (start >= end){return;}int mid = (start + end) / 2;MergeSort(a, start, mid);            //拆分，拆成数组只有1个元素MergeSort(a, mid + 1, end);Merge(a, start, mid, end);
}int main()
{int i;//int array[] = {4, 2, 7, 9, 0, 6, 2, 1, 8, 3};int array[10000] = {0};srand(time(NULL));for (i = 0; i < 10000; i++){array[i] = rand() % 1000 + 1;}MergeSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);for (i = 0; i < sizeof(array) / sizeof(array[0]); i++){printf("%d ", array[i]);}printf("\n");return 0;
}

更多视频、文章、嵌入式学习资料，微信关注 【学益得智能硬件】