归并排序

归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide

and

Conquer的一个非常典型的应用。

将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。

若将两个有序表合并成一个有序表称为二路归并。

归并排序核心步骤

归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。

时间复杂度O(N*logN)

空间复杂度O(N)

NULL){perror(malloc失败!!!);return;}int

gap

但是这个代码是有非常严重的越界问题的只有有2的次方的数据的时候才不会越界

小雅兰在这里打印几组数据看得更加清楚

NULL){perror(malloc失败!!!);return;}//

....int

a[begin2];}}printf(\n);memcpy(a,

tmp,

clock();printf(InsertSort:%d\n,

end1

begin2);printf(SelectSort:%d\n,

end3

begin6);printf(BubbleSort:%d\n,

end7

begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);

所有排序源代码

NULL){perror(malloc失败!!!);return;}_MergeSort(a,

tmp);free(tmp);

}还可以这样写是进行了小区间优化的版本相对来说好一点但leetcode上面测试不了此效果

//直接插入排序

a[end];--end;}else{break;}}a[end

tmp;}

end){return;}//小区间优化if(end-begin110){InsertSort(abegin,end-begin1);return;}int

mid

NULL){perror(malloc失败!!!);return;}_MergeSort(a,

tmp);free(tmp);

returnSize){MergeSort(nums,numsSize);*returnSize

numsSize;return

但是这道题用直接插入排序、冒泡排序这种排序就过不了了会提示超出时间限制