美文网首页
归并算法

归并算法

作者: 锋芒不露大宝剑 | 来源:发表于2019-04-10 13:48 被阅读0次
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <time.h>
#include <sys/timeb.h>
#define MAX 20
using namespace std;
 
int* create_list(int len) {

    int* list = (int *)malloc(sizeof(int) * len);
    memset(list, 0, sizeof(int) * len);
    for (int i = 0; i < len; i++) {
        list[i] = rand() % 200;
    }
    return list;
}

void print_list(int list[], int len) {

    if (NULL == list || len <= 0) {
        return;
    }
    int line = 0;
    for (int i = 0; i < len; i++, line ++) {
        if (line > 9)
        {
            cout << endl;
            line = 0;
        }
        cout << list[i] << "  ";
    }
    cout << endl;
}

long getSysTime() {

    struct timeb tb;
    ftime(&tb);
    return tb.time * 1000 + tb.millitm;
}

// 合并算法 从小到大
void Merge(int list[], int start, int end, int mid, int* tmp) {

    int i_start = start;
    int i_end = mid;
    int j_start = mid + 1;
    int j_end = end;
    // 表示辅助空间有多少元素
    int length = 0;
    // 合并两个有序序列
    while (i_start <= i_end && j_start <= j_end) {
        if (list[i_start] < list[j_start]) {
            tmp[length++] = list[i_start++];
        } else {
            tmp[length++] = list[j_start++];
        }
    }
    // i序列
    while (i_start <= i_end) {
        tmp[length++] = list[i_start++];
    }
    // j序列
    while (j_start <= j_end) {
        tmp[length++] = list[j_start++];
    }
    // 辅助空间的数据赋值给原空间
    for (int i = 0; i < length; i++) {
        list[start + i] = tmp[i];
    }
}

void MergeSort(int list[], int start, int end, int* tmp) {

    if (start >= end) {
        return;
    }
    // 取中间点
    int mid = (start + end) / 2;
    // 分组
    /// 左半边
    MergeSort(list, start, mid, tmp);
    /// 右半边
    MergeSort(list, mid + 1, end, tmp);
    // 合并
    Merge(list, start, end, mid, tmp);
}

int main(int argc, char* argv[]) {

    srand((unsigned int)time(NULL));

    int *list = create_list(MAX);

    // 辅助空间
    int *tmp = (int *)malloc(sizeof(int) * MAX);
    print_list(list, MAX);
    MergeSort(list, 0, MAX - 1, tmp);
    print_list(list, MAX);
    // 释放
    free(tmp);
    free(list);
    return 0;
}

相关文章

  • 2018-06-30

    排序算法之归并排序 归并排序算法是排序算法中的经典算法之一,其核心思想是利用归并的思想实现的排序方法,该算法采用经...

  • 第三章:高级排序算法

    归并排序算法(mergeSort) 算法思想:Python使用函数实现: 自底向上的归并排序算法 算法思想:Pyt...

  • 排序算法之归并排序

    归并排序(Merge Sort) 归并排序是利用归并的思想实现排序的方式,该算法采用的是经典的分治算法 归并排序过...

  • C++中级算法第六天(归并算法)

    归并算法解释: 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Div...

  • 归并算法

    归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。归并算法的中心是归并两...

  • 归并排序

    归并排序 这个排序算法是建立在归并操作上的一种有效的排序算法,算法主要采用分治法,归并排序的算法复杂度为O(n*l...

  • iOS - 归并排序

    Demo_github 归并排序: 归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,算法主...

  • 数据结构--归并排序

    归并排序 (Merge Sort) 归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divid...

  • 归并排序

    图解排序算法(四)之归并排序 基本思想 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用...

  • 算法与数据结构(三)高级排序算法:O(nlogn)的算法:归并排

    O(nlogn)的算法 优化改进的算法要比笨的算法快太多。 归并排序:Merge Sort 然后从下向上逐层归并。...

网友评论

      本文标题:归并算法

      本文链接:https://www.haomeiwen.com/subject/yyyniqtx.html