精华内容
下载资源
问答
  • 归并排序稳定性分析

    2021-05-29 10:38:51
    归并排序稳不稳定关键要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中,如果 A[p…m]和 A[m+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把 A[p…q]中的元素放...

    归并排序稳不稳定关键要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中,如果 A[p…m]和 A[m+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把 A[p…q]中的元素放入 tmp 数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是一个稳定的排序算法

    def merge(lst1, lst2):  # 有序列表lst1 lst2 合并成lst3
        lst3 = []
        i1, i2 = 0, 0  # 追踪每个列表当前的位置
        n1, n2 = len(lst1), len(lst2)
        while i1 < n1 and i2 < n2:  # lst1 和lst2 都拥有更多元素
            if lst1[i1] < lst2[i2]:  # lst1 的第一个元素更小
                lst3.append(lst1[i1])  # 把这个小的追加到临时列表
                i1 = i1 + 1
            else:  # lst2 的第一个元素更小
                lst3.append(lst2[i2])
                i2 = i2 + 1
        if i1 == n1:
            for i in lst2[i2:]:
                lst3.append(i)
        else:
            for i in lst1[i1:]:
                lst3.append(i)
        return lst3
    
    
    def mergeSort(nums):
        n = len(nums)
        if n <= 1:
            return nums
        m = n // 2
        left = mergeSort(nums[:m])
        right = mergeSort(nums[m:])
        return merge(left, right)
    
    
    print(mergeSort([1, 3, 2, 4, 5, 7, 9,2]))
    
    

    总结

    • 先操作左半部分,再操作右半部分,归并排序就是稳定的
    展开全文
  • 归并排序 稳定

    2017-07-27 15:42:00
    速度仅次于快排,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列 转载于:https://www.cnblogs.com/zawjdbb/p/7245219.html

    速度仅次于快排,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列

    转载于:https://www.cnblogs.com/zawjdbb/p/7245219.html

    展开全文
  • 归并排序稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按...

    归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数。

    展开全文
  • 归并排序

    2016-07-05 20:17:59
    归并排序 ...归并排序算法是稳定的(参见随笔《常用排序算法稳定性分析》)。 【2】归并排序逻辑分析与代码实现 在分析归并排序的逻辑之前,让我们也利用一下分治法理念:先从基层做起(个人之

    归并排序

    【1】归并排序

    归并排序是建立在归并操作上的一种有效的排序算法。该算法也是采用分治法(Divide and Conquer)的一个非常典型的应用。

    归并排序的算法复杂度为O(N*logN)。

    归并排序算法是稳定的(参见随笔《常用排序算法稳定性分析》)。

    【2】归并排序逻辑分析与代码实现

    在分析归并排序的逻辑之前,让我们也利用一下分治法理念:先从基层做起(个人之拙见)。

    先考虑一个简单问题:如何将两个有序数列进行合并?(注意:已有序数列)

    好吧!其实,这个简单的问题会给我们很大的启迪。步骤整理如下:

    <1>只要把两个待合并数列的第一个数据进行比较,哪个小就先安置哪个,排序之后就在对应数列中跳过该数据索引(下标)。

    <2>重复以上过程,直至有一个数列已经完全安置(即已为空)。

    <3>再将另一个数列(未空数列)的所剩数据直接取出即可。

    (1)示例代码如下:

    #include<iostream><span style="color:#0000ff;">
    using namespace std;
    
    //将有序数组ar[]和br[]合并到cr[]中
    void MemeryArray(int a[], int n, int b[], int m, int c[])
    {
        int i, j, k;
    
        i = j = k = 0;
        while (i < n && j < m)
        {
            if (a[i] < b[j])
                c[k++] = a[i++];
            else
                c[k++] = b[j++]; 
        }
    
        while (i < n)
            c[k++] = a[i++];
    
        while (j < m)
            c[k++] = b[j++];
    }
    
    void  PrintArr(int ar[],int n)
    {
        for(int i = 0; i < n; ++i)
            cout<<ar[i]<<" ";
        cout<<endl;
    }
    
    void main()
    {
        int ar[5] = {12, 23, 34, 45, 56};
        int br[5] = {13, 24, 35, 46, 60};
        int cr[10];
        cout<<"数组ar为:"<<endl;
        PrintArr(ar, 5);
        cout<<"数组br为:"<<endl;
        PrintArr(ar, 5);
        MemeryArray(ar, 5, br, 5, cr);
        cout<<"合并后结果为:"<<endl;
        PrintArr(cr, 10);
    }
    
    /*
    数组ar为:
    12 23 34 45 56
    数组br为:
    12 23 34 45 56
    合并后结果为:
    12 13 23 24 34 35 45 46 56 60
    */</span>


    可以看出合并有序数列的效率是比较高的,完全可以达到O(n)。

    那么,解决了上面的合并有序数列问题之后,我们再来看归并排序。

    归并排序的基本思路就是先将待排序数组分成两组A,B,然后如果这两组组内的数据都是有序的,就可以利用上面的逻辑(合并有序数列逻辑)很方便的将这两个有序数组数据再进行合并排序。

    问题关键是如何让这两组组内数据有序呢?

    可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的两个小组就可以了。

    这样通过先递归的分解待排序数列,再合并数列就完成了归并排序的过程。实现归并排序。

    仔细想,仔细想,仔细想,先想明白这几句话,再看下面的代码。

    (2)归并排序实现及测试示例代码:

    #include<iostream>
    using namespace std;
    
    #define  MAXSIZE  10
    
    //将两个有序数列a[first...mid] 和 a[mid...last] 合并。
    void mergearray(int a[], int first, int mid, int last, int temp[])
    {
        int i = first, j = mid + 1;
        int m = mid, n = last;
        int k = 0;
    
        while (i <= m && j <= n)
        {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }
    
        while (i <= m)
            temp[k++] = a[i++];
    
        while (j <= n)
            temp[k++] = a[j++];
    
        for (i = 0; i < k; ++i)
            a[first + i] = temp[i];
    }
    void mergesort(int a[], int first, int last, int temp[])
    {
        if (first < last)
        {
            int mid = (first + last) / 2;
            mergesort(a, first, mid, temp);     //左边有序
            mergesort(a, mid + 1, last, temp);  //右边有序
            mergearray(a, first, mid, last, temp); //再将两个有序数列合并
        }
    }
    
    bool MergeSort(int a[], int n)
    {
        int *p = new int[n];
        if (p == NULL)
            return false;
        mergesort(a, 0, n - 1, p);
        delete[] p;
        return true;
    }
    
    void  PrintArr(int ar[],int n)
    {
        for(int i = 0; i < n; ++i)
            cout<<ar[i]<<" ";
        cout<<endl;
    }
    
    void main()
    {
        int ar[MAXSIZE] = {23, 34, 45, 78, 90, 12, 49, 92, 32, 19};
        PrintArr(ar, MAXSIZE);
        bool bValue = MergeSort(ar, MAXSIZE);
        if(!bValue)
        {
            cout<<"MergeSort  Failed!! "<<endl;
        }
        PrintArr(ar, MAXSIZE);
    }


    (3)另外一种代码实现:

    复制代码
     1 #include<iostream>
     2 #include<malloc.h>
     3 using namespace std;
     4 
     5 #define   MAXSIZE  10
     6 
     7 void  PrintArr(int ar[],int n)
     8 {
     9     for(int i = 0; i < n; ++i)
    10         cout<<ar[i]<<" ";
    11     cout<<endl;
    12 }
    13 
    14 static void merge(int ar[], int low, int mid, int high)  
    15 {  
    16     int i, k = 0;  
    17     //申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列   
    18     int *temp = (int *)malloc((high - low + 1)*sizeof(int));   
    19     int begin1 = low;  
    20     int end1 = mid;
    21 
    22     int begin2 = mid + 1;  
    23     int end2 = high;   
    24 
    25     //比较两个元素,选择相对小的元素放入到合并空间,并移动指针到下一位置   
    26     for (k = 0; begin1 <= end1 && begin2 <= end2;)    
    27     {  
    28         if(ar[begin1] < ar[begin2])  
    29             temp[k++] = ar[begin1++];  
    30         else  
    31             temp[k++] = ar[begin2++];    
    32     }   
    33 
    34     while(begin1 <= end1)  //若第一个序列有剩余,直接拷贝出来粘到合并序列尾   
    35         temp[k++] = ar[begin1++];  
    36     while(begin2 <= end2)  //若第二个序列有剩余,直接拷贝出来粘到合并序列尾   
    37         temp[k++] = ar[begin2++];  
    38 
    39     for (i = 0;i < k; i++)   //将排序好的序列拷贝回数组中  
    40     {
    41         ar[low+i] = temp[i]; 
    42     }
    43            
    44     free(temp);  
    45 }  
    46 void merge_sort(int ar[],int begin,int end)  
    47 {  
    48     int mid = 0;  
    49     if(begin < end)  
    50     {  
    51         mid = (begin + end) / 2;
    52         merge_sort(ar, begin, mid); 
    53         merge_sort(ar, mid + 1, end);
    54         merge(ar, begin, mid, end);  
    55     }  
    56 }  
    57 
    58 void  main()
    59 {
    60     int  ar[] = {12, 14, 54, 5, 6, 3, 9, 8, 47, 89};
    61     merge_sort(ar, 0, MAXSIZE-1);
    62     PrintArr(ar, MAXSIZE);
    63 }
    64 
    65 /*
    66 *3 5 6 8 9 12 14 47 54 89
    67  */
    复制代码

    推荐掌握第一种。第二种仅仅助于理解归并排序思想。当然,实现方式很多,那种好理解就使用那种,因人而异。

    Good Good Study, Day Day Up.

    顺序  选择  循环  坚持  总结 

    展开全文
  • 归并排序 算法原理 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法分析 排序的思想就是将元素无限拆分,直到无可...
  • 归并和归并排序

    千次阅读 2015-03-29 18:22:33
    归并排序:和快速排序的过程相反,它是两个递归调用(排序子文件)后是一个归并的过程。 快速排序时,先分解成两个子问题后是两个递归调用(排序子文件)的过程。归并操作 1 基本的两路归并 2 抽象原位归并 归并...
  • 排序大体分为两类:比较排序和非比较排序一 各个排序的基本实现1.直接插入排序和希尔排序//整体思路:往一段有序区间插入元素,end标记为有序区间的最后一个元素下标,要插入的元素下标为end+1此处就称tmp,先把他...
  • 在理解归并排序之前先要理解算法中一个非常重要的思想方法:分冶模式。算法导论中分冶策略定义:将原问题划分为n个规模较小,与原问题结构相似的子问题;递归解决这些子问题,然后再合并其结果,就得到原问题的解。...
  • 归并排序和基数排序

    2018-05-13 11:16:29
    目录归并排序归并排序思想归并排序代码基数排序 归并排序 归并排序思想 归并排序的思想:针对已排序好的两个或两个以上的文件,经由合并的方式,并将其组合为一个大的且已经排好序的文件。 时间复杂度: O(nlogn) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,101
精华内容 11,640
关键字:

归并排序的稳定性