首页 > 其他分享 >【C语言】深入解析归并排序

【C语言】深入解析归并排序

时间:2024-07-19 12:25:58浏览次数:22  
标签:归并 int arr C语言 数组 排序 left

文章目录


在这里插入图片描述

在C语言编程中,归并排序是一种高效且稳定的排序算法。它采用分治法将问题分解成更小的子问题进行解决,然后合并结果。本文将详细介绍归并排序算法,包括其定义、实现、优化方法和性能分析,帮助读者深入理解这一经典算法。

什么是归并排序?

归并排序(Merge Sort)是一种基于比较的排序算法。它将待排序的数组分成两个子数组,分别对这两个子数组进行排序,然后将已排序的子数组合并成一个有序数组。归并排序的核心思想是“分而治之”,即将一个大问题分解成若干个小问题逐一解决。

归并排序的基本实现

以下是归并排序的基本实现代码:

#include <stdio.h>
#include <stdlib.h>

// 合并两个子数组的函数
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    // 拷贝数据到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 重新合并数组 L[] 和 R[] 到 arr[]
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = left; // 初始化合并后数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝 L[] 中的剩余元素(如果有)
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 拷贝 R[] 中的剩余元素(如果有)
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    // 释放临时数组
    free(L);
    free(R);
}

// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 递归排序两个子数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并已排序的子数组
        merge(arr, left, mid, right);
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("未排序的数组: \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("排序后的数组: \n");
    printArray(arr, arr_size);
    return 0;
}
代码解释
  1. 合并函数merge

    • 将两个已排序的子数组合并成一个有序数组。
    • 创建两个临时数组LR,分别存储左半部分和右半部分的元素。
    • 比较LR中的元素,按顺序将较小的元素放入原数组中。
    • 处理剩余的元素。
  2. 归并排序函数mergeSort

    • 递归地将数组分成两半,直到每个子数组只有一个元素。
    • 调用merge函数合并已排序的子数组。
  3. 打印数组函数printArray

    • 遍历数组并打印每个元素,便于查看排序结果。
  4. 主函数main

    • 初始化一个整数数组并计算其大小。
    • 调用mergeSort函数对数组进行排序。
    • 打印排序前后的数组。
归并排序的优化

归并排序的基本实现已经相对高效,但仍有一些优化方法可以进一步提升性能:

  1. 优化内存分配

    • 可以在一次归并排序中使用一个临时数组,避免在每次合并时频繁分配和释放内存。

    优化代码示例:

    void merge(int arr[], int left, int mid, int right, int temp[]) {
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }
    
    void mergeSort(int arr[], int left, int right, int temp[]) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }
    
    int main() {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int arr_size = sizeof(arr) / sizeof(arr[0]);
        int *temp = (int *)malloc(arr_size * sizeof(int));
    
        printf("未排序的数组: \n");
        printArray(arr, arr_size);
    
        mergeSort(arr, 0, arr_size - 1, temp);
    
        printf("排序后的数组: \n");
        printArray(arr, arr_size);
    
        free(temp);
        return 0;
    }
    
  2. 小数组插入排序

    • 对于较小的子数组,可以使用插入排序替代归并排序,以减少递归调用的开销。

    优化代码示例:

    void insertionSort(int arr[], int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    void mergeSort(int arr[], int left, int right, int temp[]) {
        if (right - left <= 10) {
            insertionSort(arr, left, right);
        } else {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }
    
    int main() {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int arr_size = sizeof(arr) / sizeof(arr[0]);
        int *temp = (int *)malloc(arr_size * sizeof(int));
    
        printf("未排序的数组: \n");
        printArray(arr, arr_size);
    
        mergeSort(arr, 0, arr_size - 1, temp);
    
        printf("排序后的数组: \n");
        printArray(arr, arr_size);
    
        free(temp);
        return 0;
    }
    
归并排序的性能分析

归并排序的时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn),这是因为每次将数组对半分裂需要 O ( log ⁡ n ) O(\log n) O(logn)次,而每次合并两个子数组的操作需要 O ( n ) O(n) O(n)时间。因此,归并排序在处理大型数据集时表现良好。

归并排序的空间复杂度为 O ( n ) O(n) O(n),因为它需要额外的空间来存储临时数组。这也是归并排序的一大缺点,相较于一些原地排序算法(如快速排序)。

归并排序是一个稳定的排序算法,因为相同元素的相对位置不会改变。

归并排序的实际应用

归并排序由于其高效性和稳定性,在以下几种情况下非常有用:

  1. 大型数据集
    • 归并排序在处理大型数据集时表现出色,特别是在数据需要稳定排序的情况下。

2

. 外部排序

  • 在处理超大数据集时,归并排序适合用于外部排序(即需要使用外部存储器的排序)。
  1. 并行计算
    • 归并排序的分治特性使其非常适合并行计算,可以通过多线程或分布式计算进一步提高性能。
结论

归并排序是C语言中一种高效且稳定的排序算法,其基于分治法的思想使其在处理大型数据集时表现出色。尽管归并排序需要额外的空间,但通过合理的优化方法,可以在实际应用中达到良好的性能。通过本文的介绍,希望读者能够深入理解归并排序算法,并在实际编程中灵活应用。

标签:归并,int,arr,C语言,数组,排序,left
From: https://blog.csdn.net/Easonmax/article/details/140435954

相关文章

  • c语言(7.19)
    今天学习了常见函数(math,time)常见函数(math)#include<stdio.h>#include<math.h>intmain(){   doubleres1=pow(2,3);   printf("%lf\n",res1);   doubleres2=sqrt(8);   printf("%lf\n",res2);      doubleres3=ceil(12.3);  ......
  • c语言篇章first小结写٩(•̤̀ᵕ•̤́๑)ᵒᵏᵎᵎᵎᵎ
    c语言篇章first小结写(第一次搞图片有点不自然)1.C语⾔是什么?⼈和⼈交流使⽤的是⾃然语⾔,如:汉语、英语、⽇语那⼈和计算机是怎么交流的呢?使⽤计算机语⾔。⽬前已知已经有上千种计算机语⾔,⼈们是通过计算机语⾔写的程序,给计算机下达指令,让计算机⼯作的。C语⾔就是众多......
  • 从零开始学Java(超详细韩顺平老师笔记梳理)05——数组(语法,赋值机制,拷贝反转)、排序(冒泡排
    文章目录前言一、数组1.基础语法1)介绍2)使用(动态、静态初始化语法与使用)3)注意事项和细节2.数组赋值机制(ArryAssign)3.数组拷贝4.数组反转(reserve)5.数组的扩容与缩减二、排序三、查找四、二维数组(TwoDimensionalArry)1.快速入门2.使用3.案例:打印一个10行的......
  • C语言面试题
    C语言面试题通常涵盖了C语言的各种概念和技术,从基础知识到高级主题都有可能涉及。以下是一些常见的C语言面试题示例,这些问题可以帮助你准备面试,无论是针对初级还是高级程序员:基础知识C语言的预处理器做了什么?描述预处理器的工作,包括宏定义、条件编译和头文件包含。解......
  • 如何书写C语言
    前言本篇随笔摘自CPrimerPlus(第六版)中文版,纯搬运学习记录使用第1步:定义程序的目标在动手写程序之前,要在脑中有清晰的思路。想要程序去做什么首先自己要明确自己想做什么,思考你的程序需要哪些信息,要进行哪些计算和控制,以及程序应该要报告什么信息。在这一步骤中,不涉及具体的......
  • C语言指针笔记
    该笔记整理自阮一峰老师的《C语言教程》和部分网上资料什么是指针指针就是一个代表某个内存地址的值声明和初始化指针变量inta=10;//声明一个指针变量p,并将a的地址赋给pint*p=&a;//输出p的值(地址值)printf("%p",p);//输出p所指向的值printf("%d",*p);这......
  • 嵌入式学习——C语言字符数组及其函数
    目录一、字符数组    1、定义    2、初始化                    3、引用字符数组元素二、字符串和字符串结束的标志三、字符数组的输入输出        1、字符串的输入:scanf    2、注意事项四、字符串处理函数......
  • 【C语言】结构体,枚举,联合超详解!!!
    目录结构体结构体声明结构体成员的访问结构体自引用 结构体变量定义,初始化,传参 结构体内存对齐 位段枚举联合(共用体)结构体结构体声明1.概念1.结构体是一些值的集合,这些值称为成员变量。2.结构体的每个成员可以是不同类型的变量。3.数组:一组相同类型......
  • 拓扑排序 + 习题
    P4017最大食物链计数 题目链接:https://www.luogu.com.cn/problem/P4017题意:给你一个食物网,求出这个最大食物链的数量最大食物链定义为左端不会捕食其他捕食者,最右端不会被捕食.解释看例子第1行nm表示生物种类n和吃和被吃的关系m接下来m行AB表示A被B吃.........
  • C语言 指针方法 输入10个整数,将其中最小的数与第一个数对换,把最大的数与最后一个数对
    输入10个整数,将其中最小的数与第一个数对换,把最大的数与最后一个数对换。写3个函数:第一个:输入10个数;第二个:进行处理;第三个:输出10个数。#include<stdio.h>voidinputNumbers(int*arr){printf("Enter10integers:");for(inti=0;i<10;i++){......