内部排序算法4（归并排序）

时间：2022-12-23 00:06:36

二路归并排序

思想

将两个有序表合成一个新的有序表就是二路归并。例如，在元素序列L中有两个已经排好序的有序顺序表 L[left],...,L[mid] 和 L[mid+1],...,L[right] ，它们可以归并成为一个有序表，仍然存放于 L[left],...,L[right] 中。
在归并排序中，用变量 i 和 j 分别做 L 中两个表的当前检测指针，用变量 k 做归并后结果表 L1 的当前存放指针。当 i 和 j 都在两个表的表长内变化时，根据相应的两个元素的排序码大小，依次把排序码小的元素放到结果表中；当 i 与 j 中有一个已经超出表长时，将另一个表中的剩余部分照抄到结果表中。

算法实现

非递归算法


内部排序算法4（归并排序）
图片来自：http://www.cnblogs.com/crx234/p/5858488.html 

//归并排序头文件
#pragma once
#include<iostream>

typedef int ElementType;

class Merge
{
public:
    Merge(int length);
void create();
void sort();
void print();
    ~Merge();

private:
    ElementType *elem;
int len;

void mergeHelp(ElementType *&L1, ElementType *&L2, int left, int mid, int right);
void mergepass(ElementType *&L1, ElementType *&L2, int l);
};

Merge::Merge(int length)
{
    len = length;
    elem = new ElementType[len];
}

inline void Merge::create()
{
std::cout << "please input the list: " << std::endl;
for (int i = 0; i < len; i++)
    {
        ElementType temp;
std::cin >> temp;
        elem[i] = temp;
    }
std::cout << "input successful" << std::endl;
}

inline void Merge::sort()  //归并排序，不断的增大块的大小，从1开始，一直到大于等于len
{
int count = 1;
    ElementType *L1 = new ElementType[len];
while (count < len)
    {
        mergepass(elem, L1, count);
        count *= 2;
        mergepass(L1, elem, count);
        count *= 2;
    }
}

inline void Merge::print()
{
for (int i = 0; i < len; i++)
    {
std::cout << elem[i] << " ";
    }
std::cout << std::endl;
}

Merge::~Merge()
{
delete[] elem;
}

inline void Merge::mergeHelp(ElementType *&L1, ElementType *&L2, int left, int mid, int right) //两个小块进行合并，left是左块的开始，mid是两块的分界线，right是右块的尽头
{
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right)
    {
if (L1[i] <= L1[j])
        {
            L2[k++] = L1[i++];
        }
else
        {
            L2[k++] = L1[j++];
        }
    }
while (i <= mid)
    {
        L2[k++] = L1[i++];
    }
while (j <= right)
    {
        L2[k++] = L1[j++];
    }
}

inline void Merge::mergepass(ElementType *&L1, ElementType *&L2, int l)  //l是归并排序中每个子排序表的初始长度
{
int i;
for (i = 0; i + 2 * l < len; i = i + 2 * l)
    {
        mergeHelp(L1, L2, i, i + l - 1, i + 2 * l - 1);
    } 
if (i + l <= len - 1)  //如果第二个表长不足l
    {
        mergeHelp(L1, L2, i, i + l - 1, len - 1);
    }
else   //如果只剩下一个表，直接复制就好
    {
for (int j = i; j < len; j++)
        {
            L2[j] = L1[j];
        }
    }
}
//归并排序main文件
using namespace std;
#include "MergeSort.h"
int main() {
    Merge m(10);
    m.create();
    m.sort();
    m.print();
system("pause");
}

结果


内部排序算法4（归并排序）

递归实现

图示


内部排序算法4（归并排序）
图片来自：百度百科 

//递归归并排序头文件
#pragma once
#include<iostream>

typedef int ElementType;

class Merge
{
public:
    Merge(int length);
void create();
void print();
void recursiveSort();
    ~Merge();

private:
    ElementType *elem;
int len;

void mergeHelp(ElementType *&L1, ElementType *&L2, int left, int mid, int right);
void recursiveSortHelp (int left, int right);
};

Merge::Merge(int length)
{
    len = length;
    elem = new ElementType[len];
}

inline void Merge::create()
{
std::cout << "please input the list: " << std::endl;
for (int i = 0; i < len; i++)
    {
        ElementType temp;
std::cin >> temp;
        elem[i] = temp;
    }
std::cout << "input successful" << std::endl;
}

inline void Merge::print()
{
for (int i = 0; i < len; i++)
    {
std::cout << elem[i] << " ";
    }
std::cout << std::endl;
}

inline void Merge::recursiveSort()
{
    recursiveSortHelp(0, len - 1);
}

inline void Merge::recursiveSortHelp(int left, int right)  //分治法
{   
    ElementType *temp = new ElementType[len];
if (left < right)
    {
int mid = (left + right) / 2;
        recursiveSortHelp(left, mid);   //处理左子串
        recursiveSortHelp(mid + 1, right);  //处理右子串
        mergeHelp(elem, temp, left, mid, right);
for (int i = left; i <= right; i++)
        {
            elem[i] = temp[i];
        }
    }
}

Merge::~Merge()
{
delete[] elem;
}

inline void Merge::mergeHelp(ElementType *&L1, ElementType *&L2, int left, int mid, int right) //每两个小块进行合并
{
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right)
    {
if (L1[i] <= L1[j])
        {
            L2[k++] = L1[i++];
        }
else
        {
            L2[k++] = L1[j++];
        }
    }
while (i <= mid)
    {
        L2[k++] = L1[i++];
    }
while (j <= right)
    {
        L2[k++] = L1[j++];
    }
}
//递归归并排序main文件，采用分治法
using namespace std;
#include "MergeSort.h"
int main() {
    Merge m(10);
    m.create();
    m.recursiveSort();
    m.print();
system("pause");
}

结果


内部排序算法4（归并排序）

算法分析

时间复杂度

MergePass做一趟二路归并排序调用MergeHelp函数 2ln 次，其中 l 是需要归并子序列的长度， n 是整个序列的长度。而MergeSort调用MergePass正好 ⌈log2n⌉ 次，而每次做MergeHelp要执行比较 O(l) 次，所以算法总的排序码比较次数为 O(nlog2n) 。不论元素初始排列如何买这个时间的代价是不变的。

空间复杂度

使用了一个与原待排序元素数组相同大小的辅助数组，空间代价为 O(n) 。

算法的稳定

归并排序是稳定的。

注：本文参考书籍《数据结构精讲与习题详解—考研辅导与答疑解惑》，殷人昆编著，清华大学出版社。
标签：

相关文章