专栏首页cwl_JavaC++经典算法题-合并排序法

C++经典算法题-合并排序法

40.Algorithm Gossip: 合并排序法

说明

之前所介绍的排序法都是在同一个阵列中的排序,考虑今日有两笔或两笔以上的资料,它可能是不同阵列中的资料,或是不同档案中的资料,如何为它们进行排序?

解法

可以使用合并排序法,合并排序法基本是将两笔已排序的资料合并并进行排序,如果所读入的资料尚未排序,可以先利用其它的排序方式来处理这两笔资料,然后再将排序好的这两笔资料合并。

有人问道,如果两笔资料本身就无排序顺序,何不将所有的资料读入,再一次进行排序?排序的精神是尽量利用资料已排序的部份,来加快排序的效率,小笔资料的 排序较为快速,如果小笔资料排序完成之后,再合并处理时,因为两笔资料都有排序了,所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率。

那么可不可以直接使用合并排序法本身来处理整个排序的动作?而不动用到其它的排序方式? 答案是肯定的,只要将所有的数字不断的分为两个等分,直到最后剩一个数字为止,然后再反过来不断的合并,就如下图所示:

不过基本上分割又会花去额外的时间,不如使用其它较好的排序法来排序小笔资料,再使用合并排序来的有效率。

下面这个程式范例,我们使用快速排序法来处理小笔资料排序,然后再使用合并排序法处理合并的动作。

代码示例

#include <stdio.h>
#include <stdlib.h> 
#include <time.h> 
#define MAX1 10
#define MAX2 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}


    int partition(int[], int, int); void quicksort(int[], int, int);
    void mergesort(int[], int, int[], int, int[]);

    int main(void) {
        int number1[MAX1] = {0}; int number2[MAX1] = {0};
        int number3[MAX1+MAX2] = {0}; int i, num;

        srand(time(NULL)); printf("排序前:");
        printf("\nnumber1[]:");
        for(i = 0; i < MAX1; i++) { number1[i] = rand() % 100; printf("%d ", number1[i]);
        }

        printf("\nnumber2[]:"); for(i = 0; i < MAX2; i++) {
            number2[i] = rand() % 100; printf("%d ", number2[i]);
        }

        // 先排序两笔资料
        quicksort(number1, 0, MAX1-1);
        quicksort(number2, 0, MAX2-1); printf("\n 排 序 后 :"); printf("\nnumber1[]:");
        for(i = 0; i < MAX1; i++) printf("%d ", number1[i]);
        printf("\nnumber2[]:"); for(i = 0; i < MAX2; i++)
            printf("%d ", number2[i]);

        // 合并排序
        mergesort(number1, MAX1, number2, MAX2, number3); printf("\n合并后:");
        for(i = 0; i < MAX1+MAX2; i++)
            printf("%d ", number3[i]);


        printf("\n"); return 0;
    }

    int partition(int number[], int left, int right) { int i, j, s;
        s = number[right]; i = left - 1;

        for(j = left; j < right; j++) { if(number[j] <= s) {
            i++;
            SWAP(number[i], number[j]);
        }
        }

        SWAP(number[i+1], number[right]); return i+1;
    }

    void quicksort(int number[], int left, int right) { int q;
        if(left < right) {
            q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right);
        }
    }

    void mergesort(int number1[], int M, int number2[], int N, int number3[]) { int i = 0, j = 0, k = 0;

        while(i < M && j < N) { if(number1[i] <= number2[j])
            number3[k++] = number1[i++];

        else

        }


        number3[k++] = number2[j++];

        while(i < M)
            number3[k++] = number1[i++];

        while(j < N)
            number3[k++] = number2[j++];
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++经典算法题-快速排序法(一)

    快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法...

    cwl_java
  • C++经典算法题-快速排序法(三)

    之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了 快速排序法的效率,它是来自演算法名书 Introduction to A...

    cwl_java
  • C++经典算法题-选择、插入、气泡排序

    选择排序(Selection sort)、插入排序(Insertion sort)与气泡排序(Bubble sort)这三个排序方式是初学排序所必须知道的三个基...

    cwl_java
  • GitHub超2.7万星,最全Python入门算法来了

    我们讨论机器学习的时候,其实很多时候都是在讨论算法。今天新智元向大家推荐一个好资源,用Python实现所有算法。该项目在Github上已经获得了超过2.7万星标...

    新智元
  • 算法之排序(上)

    排序算法有很多种,甚至有很多都完全没有听过,我们最常见,也最经典的就是:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

    信安本原
  • 数据结构与算法学习笔记之如何分析一个排序算法?

    现在IT这块找工作,不会几个算法都不好意思出门,排序算法恰巧是其中最简单的,我接触的第一个算法就是它,但是你知道怎么分析一个排序算法么?有很多时间复杂度相同的排...

    Dawnzhang
  • ElasticSearch权威指南学习(排序)

    GET /_search { "query" : { "filtered" : { "filter" : { ...

    老梁
  • 排序(Sort) 原

    排序是计算机程序设计中的一种重要操作。如果数据能够根据某种规则排序,就能大大挺高数据处理的算法效率。

    云飞扬
  • AI_第一部分 数据结构与算法(10.排序简介)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • (二十七)golang-排序和查找

    绝命生

扫码关注云+社区

领取腾讯云代金券