归并排序

最近在做链表算法题时，涉及到了归并排序，索性重新研究一下各种排序方法及其复杂度。

排序中比较复杂一点的是归并排序，思想时比较容易理解的，但是代码写起来没那么容易，该排序方法涉及到了分解和合并两个思想，其实是应用了分治的思想进行排序。

首先是对两个有序序列的合并，注意：合并的前提是：两个数组序列是有序的

 1 void Merge(int SR[],int TR[],int i,int m,int n)
 2 {
 3     //k是新序列的下表，从0开始递增；first是SR数组中前半序列的下表，从0开始，last是SR数组中后半序列的开始，从m+1开始
 4     int k,first,last;  
 5     k = i;
 6     first = i;
 7     last = m+1;
 8     while (first<=m&&last<=n)
 9     {
10         if (SR[first] < SR[last])
11         {
12             TR[k++] = SR[first++];
13         }else
14         {
15             TR[k++] = SR[last++];
16         }
17     }
18     //将某个有序数组的剩下没排完的有序列一次复制到新数组TR的后面
19     while (first <=m)
20     {
21         TR[k++] = SR[first++];
22     }
23     while (last <=n)
24     {
25         TR[k++] = SR[last++];
26     }
27 }

下面开始对一个无序数组进行分解，一直分解到只有一个元素了，此时认为他有序，再利用上面对有序数组的合并思想，从而完成归并排序。

 1 void Msort(int SR[],int TR1[],int s,int t)
 2 {
 3     int SR2[MAXSIZE+1];  //用于存放不同的有序序列对
 4     int m;
 5     if (s==t)   //递归终止的边界条件
 6     {
 7         TR1[s] = SR[s];
 8     }else
 9     {
10         m = (s+t)/2;
11         Msort(SR,SR2,s,m);
12         Msort(SR,SR2,m+1,t);
13         Merge(SR2,TR1,s,m,t);
14     }
15 }

调用归并排序算法

void MergeSort(SqList *L) { Msort(L->r,L->r,0,L->length-1); }

顺序表数据结构：

1 #define MAXSIZE 100
2 struct SqList 
3 {
4     int r[MAXSIZE-1];
5     int length;
6 };

主函数

 1 int main()
 2 {    
 3     struct SqList l = {{20,12,45,32,11},5};
 4     MergeSort(&l);
 5     for (int i =0;i<l.length;i++)
 6     {
 7         cout << l.r[i] << " ";
 8     }    
 9     system("pause");
10     return 0;
11 }

结果：

复杂度分析：

归并排序的效率还是比较高的，设一个数组长度为n的序列，使用归并排序，将序列一直分解到只剩一个元素构成一个完全二叉树，根据完全二叉树的性质，有n个节点的完全二叉树，它的深度或高度为lgn+1，二叉树的时间复杂度与树的深度有关，所以时间复杂度为O(log2)。一趟归并需要将SR[1]~SR[n]中相邻长度为h的有序序列进行两两归并，并将结果放到TR[1]~TR[n]中，这需要将待排序列中所有的记录扫描一遍，因此耗费O(n)的时间，因此，总的时间复杂度为O(nlogn)。

在归并过程中需要与原始记录序列同样数量的存储空间，存放归并结果以及递归时的深度为logn，因此空间复杂度为O(n+logn)。