加载中……
C/C++实现归并排序

归并排序

归并排序和快速排序有类似之处,同样采用分治法,不同的是,归并排序不选取基准值,采用递归方式直接将数据分为两个区间,再进行排序合并。需要注意的是,排序实际是从最小单位,即分区大小为1时开始的。

时间复杂度

因为都是从中间划分区间,且无基准值。归并排序时间复杂度较稳定

O(nlogn)

步骤

  1. 对半划分区间
  2. 递归,直到分区大小为1
  3. 依次合并区间

以本次代码的数据为例,原始数据为:

10, 15, 14, 85, 45, 62, 312, 47, 51, 84, 99, 78, 41

第一次划分区间后为:

10, 15, 14, 85, 45, 62
312, 47, 51, 84, 99, 78, 41

左分区第二次划分:

10, 15, 14
85, 45, 62

左分区第三次划分:

10
15, 14
85
45, 62

左分区第四次划分:

10
15
14
85
45
62

随后合并分区得到:

10
14, 15
85
45, 62

再次合并:

10, 14, 15
45, 62, 85

直到完成合并

代码实现

/*归并排序*/

#include <iostream>
using namespace std;


int *Merge( int *arr1, int len1, int *arr2, int len2 ) //从小到大合并值
{
    int *arr3 = new int[len1 + len2];
    int p1 = 0, p2 = 0, p3 = 0;

    while ( p1 < len1 && p2 < len2 )
    {
        if ( p1 < len1 && arr1[p1] <= arr2[p2] )
        {
            arr3[p3++] = arr1[p1++];
        }
        else
        {
            arr3[p3++] = arr2[p2++];
        }
    }

    //收尾处理
    while ( p1 < len1 )
    {
        arr3[p3++] = arr1[p1++];
    }

    while ( p2 < len2 )
    { 
        arr3[p3++] = arr2[p2++]; 
    } 
    return arr3; 
} 
void MergeSort( int *arr, int len )
{ 
    int *arr1 = new int[len / 2]; 
    int *arr2 = new int[len - len / 2]; 
    if ( len > 1 )
    {
        for ( int i = 0; i < len / 2; i++ )
        {
            arr1[i] = arr[i];
        }

        MergeSort( arr1, len / 2 );//分治递归

        for ( int i = 0; i < len - len / 2; i++ )
        {
            arr2[i] = arr[len / 2 + i];
        }

        MergeSort( arr2, len - len / 2 );//分治递归
        int *date = Merge( arr1, len / 2, arr2, len - len / 2 );

        for ( int i = 0; i < len; i++ )
        {
            arr[i] = date[i];
        }

        delete date;
    }
}

int main()
{
    int arr[] = {10, 15, 14, 85, 45, 62, 312, 47, 51, 84, 99, 78, 41};
    int len = sizeof( arr ) / sizeof( arr[0] );
    MergeSort( arr, len );
    int i = 0;

    while ( i < len )
    {
        cout << arr[i++] << endl;
    }

    return 0;
}

执行结果

版权声明: 若无特殊说明,文章均为原创,版权归本文作者所有,转载请保留出处和此说明!
本文链接: C/C++实现归并排序
本文作者: Jan.
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇