C语言中归并排序的算法实现，能否改写成长尾词？

本文共计1577个文字，预计阅读时间需要7分钟。

目录前言

一、归并排序

1.1 基本思想

1.2 算法思想

1.3 程序设计思想

1.4 程序实现

1.5 归并排序的特性总结

前言本节将为大家介绍常见的排序算法之一——归并排序。作为典型的分治算法，归并排序以其稳定性和高效的性能在多种场景中得到应用。

一、归并排序

1.1 基本思想

归并排序的基本思想是将待排序的数组分成若干个长度为1的子数组，然后将相邻的子数组进行合并，每次合并后的数组长度加倍，直到合并成整个数组。

1.2 算法思想算法采用递归方式实现，将大数组递归分解为小数组，再进行合并。

1.3 程序设计思想程序设计上，需要实现两个主要功能：分解和合并。分解是将数组分解成子数组，合并是将子数组合并成有序数组。

1.4 程序实现通过实现合并函数和归并排序函数，将上述设计思想转化为代码。

1.5 归并排序的特性总结归并排序是一种稳定的排序算法，时间复杂度为O(nlogn)，适用于大规模数据排序。

目录

• 前言
• 一、归并排序
• 1.1 基本思想
• 1.2 算法思想
• 1.3 程序设计思想
• 1.4 程序实现
• 1.5 归并排序的特性总结

前言

本期为大家带来的是常见排序算法中的归并排序，博主在这里先分享归并排序的递归算法，包您一看就会，快来试试吧~

一、归并排序

1.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 （Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序 列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

1.2 算法思想

到这里，我们可以得到一条结论，两个有序的子序列可以合成一个新的有序子序列，通过递归，我们两个新的有序序列也可以组成新的有序数列，最终实现排序的目的。有些朋友就会问了，这个我懂，关键是咋实现有序数列，其实非常的简单，分割递归至每个子序列只有一个元素时，是不是就有序啦，然后就可以合成有两个元素有序的列表嘛，再合成4个，8个……

1.3 程序设计思想

定义一个tmp数组，可以是动态开辟的(malloc)，用于临时存放合并后的有序数据，定义_MergeSort()函数，用于分解，合并数据（递归实现），参数有，待处理数组，数据区间（数组下标），tmp数组。

• 判断区间是否存在，区间不存在以及只有一个元素的情况结束程序。
• 分割区间：mid=(left+right)/2;递归左右区间，分割递归至每个子序列只有一个元素。
• 每两个子序列一组，循环遍历每一个元素，if比较两个子序列各元素的大小，取大或取小，放入tmp数组，tmp[index++]=子序列++；直到有一个子序列遍历完，循环结束。
• 循环判断是子序列是否遍历完毕，未遍历完毕的子序列剩余元素直接给到tmp数组。将tmp数组的对应的元素拷贝回原数组（已有序）。

1.4 程序实现

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>//动态开辟空间的函数的头文件 void _MergeSort(int *a,int left,int right,int *tmp) { //区间不存在以及只有一个元素的情况结束程序 if (left>=right) { return; } int mid = (left + right) / 2; //假设[left,mid],[mid+1,right]有序，那么我们就可以归并了 //递归使左右区间有序 //分割递归至每个子序列只有一个元素 _MergeSort(a,left,mid,tmp); _MergeSort(a, mid+1,right, tmp); //归并 int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int index = left; while (begin1<=end1&&begin2<=end2)//有一个子序列遍历完，循环结束 { if (a[begin1] < a[begin2])//升序，取小 { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } //判断子序列是否遍历完，未遍历完毕的子序列剩余元素直接给到tmp数组 while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2<=end2) { tmp[index++] = a[begin2++]; } //拷贝回去 for (int i=left;i<=right;++i) { a[i] = tmp[i]; } } //归并排序 void MergeSort(int *a,int n) { int* tmp=(int*)malloc(sizeof(int)*n);//动态开辟与待排序数组大小相等的一片连续的空间 _MergeSort(a,0,n-1,tmp);//子函数实现归并 free(tmp);//释放动态开辟的空间 } //打印 void Print(int* a, int n) { for (int i=0;i<n;++i) { printf("%d ",a[i]); } } int main() { int a[] = {10,6,7,1,3,9,4,2}; MergeSort(a,sizeof(a)/sizeof(a[0])); Print(a,sizeof(a)/sizeof(a[0])); return 0; }

1.5 归并排序的特性总结

• 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
• 2. 时间复杂度：O(N*logN)
• 3. 空间复杂度：O(N)
• 4. 稳定性：稳定

到此这篇关于C语言常见排序算法归并排序的文章就介绍到这了,更多相关C语言归并排序内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！