| 数据结构之归并排序的实例详解 | 您所在的位置：网站首页 › 长治五一免费景点 › 数据结构之归并排序的实例详解 |
数据结构之归并排序的实例详解
|
数据结构之归并排序的实例详解
发布时间：2020-10-02 18:37:26
来源：脚本之家
阅读：65
作者：lqh
栏目：编程语言
归并排序 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并，得到完全有序的序列；即先使每个子序 列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列 再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。所以呢，我们总结一下归并排序 其实就只有两步： 分解:将有序序列不断地分裂，直到每个区间都只有一个数据为止. 合并:将两个区间合并为一个有序的区间，一直合并知道只有一个区间为止.
图是我偷来的，但是学习是认真的. 分解的过程我们很容易想明白的，用递归就可以.但是我们今天最主要的步骤是合并，你要将两个区间合并为一个有序的区间你会怎么思考呢？ 这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数 列为空，那直接将另一个数列的数据依次取出即可。 代码实现: //将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; }其实我们发现这种做法效率其实还是蛮高的，效率达到了O（N）.现在我们解决了合并的问题. 现在总的来看一下归并排序的做法,通过先递归的分解数列(将数列分解成只有一个元素的区间)，再合并数列就完成了归并排序。 代码实现 //将有二个有序数列a[first...mid]和a[mid...last]合并。 void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i |
【本文地址】