合并排序在有些资料或书籍中又叫归并排序。合并排序算法的基本过程如下： 分解：把待排序的n个元素分解成两组，每组n/2个元素。如果n为奇数则一组(n – 1)/2个元素，另一组1 + (n – 1) / 2 ； 排序：用合并排序法递归的对上一步分解成的两个组进行排序； 合并：把上一步排序好的两组合并在一起。 第一次接触此排序算法时重点要理解上述过程的第二步，这里面存在一个递归思想。如果您对递归还不熟悉的话，请先学习递归的基本概念，然后再来看本算法。 假定有一组待排序整数：[7，3，2，6] 现在我们用合并排序来对这4个数进行模拟排序，让大家对该排序算法有一个更加直观的认识。 第1步，把原数组分解成两组：[7，3] [2，6] 第2步，用合并排序对前一步分解出来的两组进行排序，这一步又分为如下几步： 首先对[7，3]这一组再次利用合并排序算法： 第2.1步，把[7，3]分解成两组[7] [3] 第2.2步，在上一步分解出来的两步都只有一个元素，所以每一组都是已经排好序了的。因此我们不需要再次利用合并排序算法分别对这两组排序。 第2.3步，合并[7] [3]这两组得到结果[3, 7] 然后对[2，6]这一组再次利用合并排序算法： 第2.4步，把[2，6]分解成两组[2] [6] 第2.5步，在上一步分解出来的两步都只有一个元素，所以每一组都是已经排好序了的。因此我们不需要再次利用合并排序算法分别对这两组排序。 第2.6步，合并[2] [6]这两组得到结果[2, 6] 第3步，对已排序要的[3，7] [2，6]合并在一起形成[2，3，6，7] 如果上面这些文字说明还不够清晰，那么请看下面用c语言实现的合并排序算法，代码最能说明问题了^_^ void merge_sort(int a[], int p, int r) { if(p < r) { int q = (p + r) / 2; //分解成两组 merge_sort(a, p, q); //递归的对前一组排序 merge_sort(a, q + 1, r); //递归的对后一组排序 merge(a, p, q, r); //合并结果 } } merge_sort(int a[], int p, int r)函数的功能就是对数组a中的下标为p到下标为r这r – p + 1个连续的元素进行合并排序。从merge_sort()的代码我们可以很清晰的看到递归过程，以及合并排序的思想。下面我们再来看merge()函数如何把两个已经排好序的数组合并在一起形成一个排好序的结果。这个函数代码稍微有点多，但合并的思想却相当简单，所以这里就没有添加注释，您一定可以看懂的！ void merge(int a[], int p, int q, int r) { int i, j, k; int *tmp = (int *)malloc((r – p + 1) * sizeof(int)); i = p; j = q + 1; k = 0; while(i <= q && j <= r) { if(a[i] < a[j]) { tmp[k] = a[i++]; } else { tmp[k] = a[j++]; } k++; } while(i <= q) { tmp[k++] = a[i++]; } while(j <= r) { tmp[k++] = a[j++]; } for (i = 0; i < k; i++) { a[p + i] = tmp[i]; } free tmp; }

评论