排序之归并排序的算法思想及实现代码

排序之归并排序的算法思想及实现代码

文章目录

• • 归并排序
  • • 归并排序的基本思想
    • 归并排序的实现代码
    • 归并排序的性能分析
  • 完整代码

---

归并排序 归并排序的基本思想

归并排序与前面讲到的基于交换、选择等排序的思想不一样，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。

二路归并的基本思想：
假定待排序表含有 n n n 个记录，可将其视为 n n n 个有序的子表，每个子表的长度为1，然后两两归并，得到 ⌈ n / 2 ⌉ lceil n/2 rceil ⌈n/2⌉个长度为2或1的有序表；再两两归并……如此重读，直到合并成一个长度为 n n n 的有序表为止。
这种排序方法称为2路归并排序。

2路归并排序的例子：

---

归并排序的实现代码

归并排序的实现需要两个算法，一个是按 l e n len len做一趟两两归并，另一个是归并排序。

M e r g e ( ) Merge() Merge()的功能是将前后相邻的两个有序表归并为一个有序表。
设两段有序表 L . d a t a [ l o w . . . m i d ] L.data[low...mid] L.data[low...mid]、 L . d a t a [ m i d + 1... h i g h ] L.data[mid+1...high] L.data[mid+1...high]存在放同一顺序表中的相邻位置，先将它们复制到辅助数组 B [ ] B[] B[]中。每次从对应B中的两个段取出一个记录进行关键字的比较，较小者放入 L . d a t a [ ] L.data[] L.data[]中，当数组 B [ ] B[] B[]中有一段的下标超出其对应的表长（即该段元素已经完全复制到 L . d a t a [ ] L.data[] L.data[]中）时，将另一端中的剩余部分直接复制到 L . d a t a [ ] L.data[] L.data[]中。

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

归并排序（递归）：

//归并排序
void MergeSort(SeqList &L, int low, int high){
    if(low 
 
归并排序的性能分析 
空间复杂度
 
由于辅助空间占用 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个单元，故归并排序的空间复杂度为 
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         )
        
       
       
        O(n)
       
      
     O(n)。
 
时间复杂度
 
每趟归并的时间复杂度为 
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)，总共需要进行 
    
     
      
       
        ⌈
       
       
        l
       
       
        o
       
       
        
         g
        
        
         2
        
       
       
        n
       
       
        ⌉
       
      
      
       lceil log_2n rceil
      
     
    ⌈log2​n⌉趟归并，所以算法的时间复杂度为 
     
      
       
        
         O
        
        
         (
        
        
         n
        
        
         l
        
        
         o
        
        
         
          g
         
         
          2
         
        
        
         n
        
        
         )
        
       
       
        O(nlog_2n)
       
      
     O(nlog2​n)。
 
稳定性
 
由于
    
     
      
       
        M
       
       
        e
       
       
        r
       
       
        g
       
       
        e
       
       
        (
       
       
        )
       
      
      
       Merge()
      
     
    Merge() *** 作不会改变相同关键字记录的相对次序，故二路归并排序算法是一种稳定的排序方法。
 
 
完整代码 
#include
using namespace std;

#define maxSize 20
typedef struct{
    int data[maxSize];
    int n;
}SeqList;

void PrintList(SeqList L){
    for(int i=0; i>n;
    for(int i=0; i>L.data[i];
    }
    L.n = n;
    cout< 
运行结果：
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5611255.html