vlambda博客
学习文章列表

数据结构的学习可以分为八个模块：1.绪论，2.线性表，3.栈和队列，4.串，5.树与二叉树，6.图，7.查找，8.排序。

排序部分可分为：

归并排序

归并排序与上述基于交换、选择等排序的思想不—样，"归并"的含义是将两个或两个以上的有序表组合成—个新的有序表。假定待排序表含有 n 个记录，则可将其视为 n 个有序的子表，每个子表的长度为 1，然后两两归并，得到个长度为 2 或1的有序表;继续两两归并……如此重复，直到合并成一个长度为 n 的有序表为止，这种排序方法称为 2 路归并排序。

下图所示为 2 路归并排序的一个例子，经过三趟归并后合并成了有序序列。

Merge()的功能是将前后相邻的两个有序表归并为一个有序表。设 两段有序表 A[low...mid]、A[mid+1…high]存放在同一顺序表中的相邻位置，先将它们复制到辅助数组B中。每次从对应 B 中的两个段取出一个记录进行关键字的比较，将较小者放入 A 中，当数组 B 中有一段的下标超出其对应的表长(即该段的所有元素都已复制到 A 中)时，将另一段中的剩余部分直接复制到 A 中。算法如下∶

int *B=(int *)malloc((n+1)*sizeof(int)); //辅助数组B void Merge(int A[],int low,int mid,int high){    //表A的两段 A[low...mid]和 A[mid+1...high]各自有序，将它们合并成一个有序表 for(int k=low; k<=high; k++)        B[k]=A[k];    //将 A中所有元素复制到 B 中 for(i=low,j=mid+1,k=i;i<=mid&&j<=high; k++){        if(B[i]<=B[j])    // 比较 B 的左右两段中的元素             A[k] =B[i++];    //将较小值复制到 A中 else A[k]=B[ ++];  } //for while(i<=mid) A[k++]=B[i++]; //若第一个表未检测完，复制  while (j<=high) A[k++]=B[j++]; //若第二个表未检测完，复制}

代码中，最后两个 while 循环只有一个会执行。

一趟归并排序的操作是，调用次算法 merge ()，将L[1…n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为 2h的有序段，整个归并排序需要进行趟。

递归形式的 2 路归并排序算法是基于分治的，其过程如下。

分解∶将含有 n个元素的待排序表分成各含 n/2 个元素的子表，采用 2 路归并排序算法对两个子表递归地进行排序。

合并∶ 合并两个已排序的子表得到排序结果。

void MergeSort(int A[],int low,int high) { if(low<high){        int mid=(low+high)/2;    //从中间划分两个子序列        MergeSort (A,low,mid);    //对左侧子序列进行递归排序         MergeSort (A,mid+1, high);    //对右侧子序列进行递归排序        Merge (A,low,mid, high);    //归并 } //if}

2 路归并排序算法的性能分析如下∶

空间效率∶ Merge ()操作中，辅助空间刚好为 n个单元，所以算法的空间复杂度为 O(n)。

时间效率∶ 每趟归并的时间复杂度为 O(n)，共需进行 趟归并，所以算法的时间复杂度为O(nlog₂n)。

稳定性：由于Merge()操作不会改变相同关键字记录的相对次序，所以 2 路归并排序算法是一种稳定的排序方法。

注∶ 一般而言，对于 N个元素进行k路归并排序时，排序的趟数 m 满足K^m=N，从而 m = log_kN，又考虑到 m为整数，所以 m=。这和前面的2 路归并是一致的。