1. 归并排序
1. 算法介绍
归并排序采用的分治思想，其核心工作流程如下：
- 将数据分为左右两部分
- 对左右两部分进行排序
- 对已经排序好的左右两部分进行合并
具体操作示意图如下：
通过分解图可知，归并排序采用的是一种将大问题转化为小问题的思路，且每个问题解决方法是一样，这就很容易让我们想到递归。
若是用递归解决该问题，我们就需要知道递归公式、终止条件。
- 终止条件：显而易见，当数据分无可分之时，递归停止。即
data_start >= data_end。 - 递归公式：
mergesort(start, end)=merge(``merge_sort(start, mid),merge_sort(mid, end)``)。
我们将上述公式翻译为代码：
void sort(int *arr, int *tmp, const int &start, const int &end){if (start < end){int middle = (start + end) / 2;sort(arr, tmp, start, middle);sort(arr, tmp, middle + 1, end);merge(arr, tmp, start, middle, end);}}
至此，我们已经搞定了数据分割，那么如何对数据进行排序及合并呢？
核心思想为：准备一个临时数组，同时对数据部分的左右两部分进行遍历，若是左侧数据较小，则将其放入临时数组中，左侧指针后移，反之将右侧数据放入数组并将右侧指针后移，待其中一部分遍历完成后，将另一部分的内容按顺序拷贝到临时数组中即可。
下面时操作示意图：
具体代码如下：
void merge(int *arr, int *tmp, const int &start, const int &mid, const int &end){int left_start = start;int left_end = mid;int right_start = mid + 1;int right_end = end;int i = start;int j = right_start;int t = 0;while (i <= left_end && j <= right_end){if (arr[i] <= arr[j]){tmp[t++] = arr[i++];}else{tmp[t++] = arr[j++];}}while (i <= left_end){tmp[t++] = arr[i++];}while (j <= right_end){tmp[t++] = arr[j++];}t = 0;while(left_start <= right_end){arr[left_start++] = tmp[t++];}}
1.2 算法分析
- 是否为原地排序算法：否。
- 是否为稳定排序算法：是。
时间复杂度：通过上述代码我们可以看到，归并排序的时间复杂度与数据有序度毫无关系，因此其时间复杂度非常稳定，最好、最坏、平均时间复杂度均为
。上述结果是如何推断出来的呢？<br /> 假设n个元素进行归并排序的时间为，而在一次归并排序中会对两个子串进行归并排序，因此其中一个子串进行归并排序的时间为。通过分析merge函数，合并两段数据的时间复杂度为，因此我们就得到了以下公式：<br /> <br /> 那么如何求解呢？我们将进行均分，可以得到如下公式：<br />
T(n) = 2T(n / 2) + n= 2(2T(n / 4) + n / 2)) +n = 4(T(n / 4)) + 2n= 4(2T(n / 8) + n / 4) + 2n = 8(T(n / 8)) + 3n= (2 ^ K)(T(n / (2 ^ k))) + kn
通过可知，，则，则，因此。
空间复杂度：归并排序执行过程中的空间消耗由两部分组成，一部分为临时数组，另一部分为递归入栈。前一部分的空间复杂度为
，后一部分为
，因此最终结果为。
2. 快速排序
2.1 算法介绍
快速排序与归并排序一样，采用的也是分治思想，但实现原理却有很大的不同。
快速排序核心思想：在一组数据中任意选择一个值作为分区点（pivot）
- 将比pivot值小的数字放在pivot左侧
- 将比pivot值大的数组放在pivot右侧
- 将左右子序列作为数据（不包含分区点）重复执行上述三个步骤，直到左右子序列只剩一个值为止
那么现在有几个问题：
- 虽说任意选取值作为分区点，那么在实际使用过程中，具体应该如何选择呢？
- 如何完成分区点对原始数据的分割呢？
首先回答第一个问题：在实际过程中，我们一般选择原始数据的最后一个元素作为分区点。
接着回答第二个问题：学过归并排序之后，我们很容易就能想到，我们可以申请两个临时数组，将比pivot小的数字放到第一个数组，将比pivot大的数字放到第二个数组，之后再按照顺序合并数组即可，具体操作示意图如下：
这是一种很简单的分区做法，但是我们发现这样做会耗费大量的内存空间，那么有没有改进的方法呢？当然有！下面我将思路写成了伪代码。
int partition(arr, begin, end){povit := arrr[end]i := beginj := endfor j := begin to end do{if (arr[j] < povit){swap arr[i] with arr[j]i := i+1}}swap arr[i] with arr[end]return i}
改进后的分区方法有一点像选择排序。我们使用两个指针i,j，使用i将数据分为已处理部分和未处理部分，使用j遍历原始数据。初始时，i,j都指向第一个数据，然后比较j元素与povit元素的大小，若j小于povit元素，则交换i,j元素，同时i,j后移，反之则只有j后移，直到j遍历到n-1个数据时跳出循环，此时i即是分区点所在的位置，将i,povit数据交换即可。
下面我们看一张图，加深一下理解：
注意：第五步中j会指向最后一个元素，此处仅仅是因为for循环结束后，会将j偏移至此。
下面我们看一下具体代码：
void quick_sort(int *arr, const int begin, const int end){if (begin >= end){return;}int q = parition(arr, begin, end);quick_sort(arr, begin, q - 1);quick_sort(arr, q + 1, end);}int parition(int *arr, const int begin, const int end){int deal_pos = begin; // 已处理区域的待插入位置int undeal_pos = deal_pos; // 未处理区域的位置int pivot = arr[end]; // 选择的分割点数值int tmp = 0;for (; undeal_pos < end; ++undeal_pos){if (arr[undeal_pos] < pivot){tmp = arr[undeal_pos];arr[undeal_pos] = arr[deal_pos];arr[deal_pos] = tmp;deal_pos += 1;}}tmp = arr[end];arr[end] = arr[deal_pos];arr[deal_pos] = tmp;return deal_pos;}
2.2 算法分析
- 是否是稳定排序算法：否
- 是否是原地排序算法：是
时间复杂度分析：
最好时间复杂度：
。分区点选择非常好，每次都能平分数据。此时快速排序算法为归并算法，因此时间复杂度为。
最坏时间复杂度：
。数据原本就是有序的，仅有某一部分分区有数据，因此需要进行次分区操作，每次分区需要扫描次数据，因此时间复杂度为。
平均时间复杂度：
。
- 空间复杂度分析：。
- 最好空间复杂度：
- 最坏空间复杂度：
- 平均空间复杂度：
3. 快速排序与归并排序区别
分析两种排序算法执行过程，我们发现两种算法是反的。
递归排序是由下到上的，在将数据分割完成之后，才会进行数据排序、合并。而快速排序是由上到下的，在将数据排序之后，才会进行分割。
4. 如何在时间复杂度为
假设我们有一组数据时，找到一组数据中的第K大元素？5,1,2,3,6,7，排好序之后数据为7,6,5,3,2,1，我们认为第2大元素为6。
我们可以想到使用快速排序中的分区方法来进行这一过程：
将数据的最后一个数据作为povit，通过分区方法，将数据分为arr[begin, i]、povit、arr[i +1, end]三部分，此时我们就可以说下标为i的元素是原始数据中第i+1大的元素。因此：
- 最好空间复杂度：
- 若是
K=i+1，则说明找到了直接返回即可； - 若是
K>i+1，则说明要找的元素在右半分区； - 若是
K>i+1，则说明要找的元素在左半分区； - 若是遇到2、3情况，则递归分区所在的半区，直到情况1满足位置。
下面我们分析一下时间复杂度：
第一次分区要遍历的元素为
个，第二次分区要遍历的元素为
个，第三次为
，直到最后遍历的元素个数为1为止，加起来之后遍历的总次数为
，因此时间复杂度为。
当然上述只是平均情况下的，若数据是有序的，则每次要遍历的元素个数为
，此时最终的时间复杂度为，当然这也是最差时间复杂度。
5. 合并日志问题
若当前有十个日志文件，每个日志文件大小为300M。已知每个文件的日志都是按照时间戳从小到大排列的，若现在日志所在的电脑只有1G内存，如何完成日志文件的合并？
思路解析：可以参考归并算法的合并算法，归并排序中的合并算法为两路合并，我们这里采用多路合并的方式。
具体做法：申请一个大小为10的数组，从10个文件中分别取出第一条日志，拿出时间戳最小的一条日志存入最终日志文件中，然后从时间戳最小的日志所在的文件取出第二条日志放入数组，再次比较，以此类推，知道所有文件都合并存入最终日志文件为止。
若有收获，就点个赞吧
0 人点赞
