c语言数据结构 排序（三）

本篇博客主要讲解归并排序。

一.归并排序的递归实现

1.思路：第一步，通过递归将一组无序的数据划分为的单个数据，此时单个数据视为是有序的。

第二步，当一组数据的左右区间都是有序的时候可以进行归并，如之前做过的题合并两个有序数组的思路。

 

 2.代码实现如下：

先写一个归并排序的主函数，其功能是malloc一个新的数组，用于存储归并数组左右区间的数据。

 

再写一个归并排序的子函数，其功能是通过排序划分数组为单个有序区间，再进行归并排序。其作用：规避将全部功能写在一个函数，多次调用函数多次malloc空间，造成内存浪费并且不可控。

 

递归调用实现

 二.归并排序的时间复杂度和空间复杂度

时间复杂度为O(N*logN)

计算思路如下：由下图可知当把一组数据划分为单个有序区间后，将其进行归并，其实现过程的结构可类似于二叉树结构。每次将单个数据和另一个单个有序数据归并为两个有序数据，再将两组两个有序数据进行归并为四个有序数据，以此类推。每轮进行归并相当于遍历一遍数组，而一共有logN轮归并。

空间复杂度为O(N)

只是额外malloc了一个存储同样多数据的数组。

三.归并排序的非递归实现

1.思路：要想非递归实现，就要深度理解递归是怎样进行的。我们在递归当中重点完成的是将一组数据划分为单个有序区间，并且将其归并。在非递归中如何实现呢？是否需要借助栈和堆呢？借助栈和堆会使得代码实现复杂，有另一种简便想法可以实现。那就是通过gap这一变量来实现划分，在划分的过程中就完成归并。

在我实现过程中，还发现几点意外。会出现下标越界的情况。

1.第一组越界

2.第二组全部越界

3.第二组部分越界

 

根据以上的情况，当第一组越界时不再进行归并，保留下来。在最后进行归并。

当第二组全部越界时同样不再进行归并，保留下来。 再最后归并。

当第二组部分越界时要修正其截至数据的下标，进行归并。

 

2.代码实现

 

四.计数排序的实现

1.思路：一组数据大小比较集中的数组。创建一个新的数组，原数组数据大小进行相对处理后，其数值与新数组下标对应的新数组元素数据要加一，从新数组起始下标到结束下标开始遍历，如果其下标对应元素不为0，再进行相应处理，得出数字，元素对应数据是几，就将该数据打印几遍。

1-10的数

100-106

 

-1~3

 

 

2.代码实现：