当前位置:编程学习 > C/C++ >>

排序算法之归并排序

一、基本思想
归并排序,和快排一样同样采用了分治的思想,将两个(或以上)有序表合并成一个新的有序表。
 
归并排序步骤如下:
把N个记录看成 N个长度为 1 的有序子表;
进行两两归并使记录关键字有序,得到 N/2 个长度为 2 的有序子表; 
重复第2步直到所有记录归并成一个长度为N的有序表为止。
 
二、算法实现
下面是归并排序算法的递归实现:
 
#include <iostream>  
#include <malloc.h>  
using namespace std;  
  
// 合并两个有序部分  
void mergeArray(int a[], int first, int mid, int last, int temp[]) {  
    if (first >= last) {  
        return;  
    }  
    int i = first, j = mid + 1;  
    int k = first;  
    while (i <= mid && j <= last) {  
        if (a[i] > a[j]) {  
            temp[k++] = a[j++];  
        } else {  
            temp[k++] = a[i++];  
        }  
    }  
    while (i <= mid) {  
        temp[k++] = a[i++];  
    }  
    while (j <= last) {  
        temp[k++] = a[j++];  
    }  
  
    // 回写到原来数组中  
    for (k = first; k <= last; k++) {  
        a[k] = temp[k];  
    }  
}  
  
// 递归调用归并  
void mSort(int* a, int first, int last, int *temp) {  
    if (first < last) {  
        int mid = (first + last) >> 1;  
        mSort(a, first, mid, temp);  
        mSort(a, mid + 1, last, temp);  
        mergeArray(a, first, mid, last, temp);  
    }  
}  
  
// 归并排序算法  
void mergeSort(int *a, int len) {  
    int* temp = (int*) malloc(len * sizeof(int));  
    mSort(a, 0, len - 1, temp);  
    free(temp);  
}  
  
int main() {  
    int arr[] = { 213, 43, 43, 123, 45, 52, 67, 234, 452, 5, 67 };  
    int len = 11;  
  
    cout << "Before sorting:" << endl;  
    for (int i = 0; i < len; i++) {  
        cout << arr[i] << "\t";  
    }  
  
    mergeSort(arr, len);  
  
    cout << endl << "After merge sorting:" << endl;  
    for (int i = 0; i < len; i++) {  
        cout << arr[i] << "\t";  
    }  
    cout << endl;  
  
    return 0;  
}  

 

 
三、算法分析
归并排序最好、平均、最坏时间复杂度都是:O(n*log2(n)),
 
归并排序需要额外的存储空间,其空间复杂度为:O(n).
 
归并排序和快排、堆排序一样是一种高效的排序算法,在数据规模较大而且存储空间要求足够的情况下是非常好的选择。
 
四、算法改进
归并排序改进和优化的方向如下:
当问题分割很小到某个规模的时候停止递归,采用简单插入排序;
消除递归调用
消除反复回写
...
下面是改进的一个消除递归算法:
 
 
#include <iostream>  
#include <malloc.h>  
using namespace std;  
  
// 合并数组中连续的两个有序部分  
void mergeArray(int a[], int first, int mid, int last, int temp[]) {  
    int i = first, j = mid + 1;  
    int k = first;  
    while (i <= mid && j <= last) {  
        if (a[i] > a[j]) {  
            temp[k++] = a[j++];  
        } else {  
            temp[k++] = a[i++];  
        }  
    }  
    while (i <= mid) {  
        temp[k++] = a[i++];  
    }  
    while (j <= last) {  
        temp[k++] = a[j++];  
    }  
}  
  
// 根据设定的步长来顺序归并  
void mergeStep(int a[], int step, int len, int temp[]) {  
    int first, mid, last;  
    first = 0;  
    last = first + step + step - 1;  
    mid = first + step - 1;  
    while (last < len) {  
        mergeArray(a, first, mid, last, temp);  
        first = last + 1;  
        last = first + step + step - 1;  
        mid = first + step - 1;  
    }  
    // 末端注意数组边界  
    if (mid > len) {  
        for (int i = first; i < len; i++) {  
            temp[i] = a[i];  
        }  
    } else {  
        mergeArray(a, first, mid, len - 1, temp);  
    }  
}  
  
void mergeSort(int a[], int len) {  
  
    cout << "Before sorting:" << endl;  
    for (int i = 0; i < len; i++) {  
        cout << a[i] << "\t";  
    }  
    cout << endl;  
    //  
    int flag = 0; // 写入方向标识  
    int* temp = (int*) malloc(len * sizeof(int));  
    // 消除递归  
    for (int step = 1; step < len; step = step << 1) {  
        // 避免返易做图写  
        if (flag++ % 2) {  
            // flag初始为奇数,向a写入排序结果,执行后flag为偶数  
            mergeStep(temp, step, len, a);  
        } else {  
            // flag初始为偶数,向temp写入即可,执行后flag为奇数  
            mergeStep(a, step, len, temp);  
        }  
    }  
    // 若flag为奇数,则表明排序结果存在于temp中,需要回写  
    if (flag % 2) {  
        for (int i = 0; i < len; i++) {  
            a[i] = temp[i];  
        }  
    }  
    //  
    free(temp);  
    //  
    cout << "After merge sorting:" << endl;  
    for (int i = 0; i < len; i++) {  
        cout << a[i] << "\t";  
    }  
    cout << endl;  
  
}  
  
int main() {  
    int arr[17] = { 213, 67, 89, 10, 23, 9, 23, 45, 12, 456, 234, 67, 12, 0 };  
    int len = 17;  
    mergeSort(arr, len);  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,