什么是归并排序?
归并排序简单来讲,就是将两个有序的序列整合到一起。
推荐教程:PHP视频教程
如何将两个有序的序列整合到一起呢?
那么我们假设,现在有 M={m1 ,m2,m3,....,mx}序列和 N = {n1,n2,n3,....,ny}序列,这两个序列已经是有序的序列,首先创建一个空序列 K = {},那么接着将 m1 和 n1 进行比较,加入 m1 < n1 那么将 m1 放入 K 序列中,然后 M 序列游标后移,即下一次将进行 m2 和 n1 的比较,直到全部比较完毕,并填入序列 K 中。
既然归并排序是整合有序序列,那么岂不是不能排序无序序列,这条件也太苛刻了点吧?
归并排序是建立在分治法的基础上进行操作的,也就是可以将一个完全无序的序列进行无线分割以达到有序序列,比如:现在有 M={m1 ,m2,m3,....,mx},M序列是完全无序的序列,那么此时可以将 M 序列分成若干个小序列——{m1,m2},{m3,m4}....{mx-1,mx};此时这些序列就是有序的,那么就可以通过归并操作进行排序,所以归并排序也可以排序无序序列,且速度仅次于快速排序,属于稳定排序。
如何分割序列?
上个问题已经提过,归并排序是建立在分治的基础上进行操作的,其中分治的体现就体现在分割序列上,比如:现在有M={m1 ,m2,m3,....,mx},第一次分割:M1 = {m1,m2,...,m(x+1)/2},M2 = {m(x+1)/2 +1,m(x+1)/2 +2,...,mx},第一次分割之后得到 M1 和 M2 序列,然后再分割 M1 和 M2 ,分割若干次之后得到 x/2 + x%2 个序列,然后再逐一进行归并操作。
该算法具体步骤:
1、规定首指针 left 和mid(left指向序列1的首元素,right 指向序列2的首元素)
2、比较 left 和 mid 的大小,将小的元素放入新建的空间中
3、重复步骤2,直到其中一个序列遍历完毕
4、将剩下的未加入新建空间中的元素直接复制粘贴进新建空间
该算法的核心步骤:
1、使用分治法(递归)分割序列
2、比较 left 和 mid 的大小 , 将小的元素的添加进入新建空间
讲述完毕,贴上代码:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 排序__归并排序 { class 归并 { public static int[] arr = { 6, 202, 301, 100, 38, 8, 1 ,-1,1000}; static void Main(string[] args) { Sort(arr, 0, arr.Length -1); foreach (var item in arr) { Console.Write(item + " "); } Console.ReadKey(); } public static void Sort(int []a,int left,int right) { if (left >= right) return; else { int mid = (left + right) / 2; //@1 Sort(a, left, mid); Sort(a, mid + 1, right); MergeSort(a, left, mid, right); } } public static void MergeSort(int []a,int left,int mid,int right) { int[] Arr = new int[right - left + 1]; int l = left, m = mid +1 , k = 0; //@2 while ( m <= right && l <= mid ) //@3 { if (a[l] > a[m]) Arr[k++] = a[m++]; else Arr[k++] = a[l++]; } while (m < right +1) //@4 { Arr[k++] = a[m++]; } while (l < mid +1 ) Arr[k++] = a[l++]; //@4 for (k = 0, l = left; l < right + 1; k++, l++) a[l] = Arr[k]; } } }
代码解读:
@1 :Sort()函数完成了序列的分割,每一次递归都将序列分成两半,直到不能分隔为止。
@2 :l 代表序列1的首元素,m 代表序列2的首元素,k代表新建数组Arr的已有元素个数
@3 :序列1的首元素和序列2的首元素进行比较,将小的放入 Arr 中,且序列游标后移,直到其中一个序列的元素遍比较完毕
@4 :在序列1 和序列2的比较过程中,可能出现序列1已经全部添加进了 Arr 中,但是序列2还没有,则将剩下的未比较的元素直接复制进入 Arr 中
总结:
以上代码并不是真正意义上的分割数组,只是做了一个逻辑分割,没有像其他代码一样将分割后的数组填入一个新的数组,那样做的话会对速度和内存产生一点影响,虽然微乎其微,但是总归是没这么好的,在归并操作上,需要注意的是参数不要越界(我当时就想了很久为什么 @2 上面的 m 要等于 mid +1 而不是 mid ,其实道理很简单,因为mid是属于左序列,从 mid+1 开始才属于右序列,将m = mid +1 改成 m = mid 不是不行,只是后面的代码也需要改,但是没有必要多做一次无用比较,这个问题我当时真是想了半天...),其实只要理清楚其中的逻辑关系,这样代码就能做到信手拈来。
以上是排序算法—归并排序【附代码】的详细内容。更多信息请关注PHP中文网其他相关文章!

PHP仍然流行的原因是其易用性、灵活性和强大的生态系统。1)易用性和简单语法使其成为初学者的首选。2)与web开发紧密结合,处理HTTP请求和数据库交互出色。3)庞大的生态系统提供了丰富的工具和库。4)活跃的社区和开源性质使其适应新需求和技术趋势。

PHP和Python都是高层次的编程语言,广泛应用于Web开发、数据处理和自动化任务。1.PHP常用于构建动态网站和内容管理系统,而Python常用于构建Web框架和数据科学。2.PHP使用echo输出内容,Python使用print。3.两者都支持面向对象编程,但语法和关键字不同。4.PHP支持弱类型转换,Python则更严格。5.PHP性能优化包括使用OPcache和异步编程,Python则使用cProfile和异步编程。

PHP主要是过程式编程,但也支持面向对象编程(OOP);Python支持多种范式,包括OOP、函数式和过程式编程。PHP适合web开发,Python适用于多种应用,如数据分析和机器学习。

PHP起源于1994年,由RasmusLerdorf开发,最初用于跟踪网站访问者,逐渐演变为服务器端脚本语言,广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发,1991年首次发布,强调代码可读性和简洁性,适用于科学计算、数据分析等领域。

PHP适合网页开发和快速原型开发,Python适用于数据科学和机器学习。1.PHP用于动态网页开发,语法简单,适合快速开发。2.Python语法简洁,适用于多领域,库生态系统强大。

PHP在现代化进程中仍然重要,因为它支持大量网站和应用,并通过框架适应开发需求。1.PHP7提升了性能并引入了新功能。2.现代框架如Laravel、Symfony和CodeIgniter简化开发,提高代码质量。3.性能优化和最佳实践进一步提升应用效率。

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

PHP类型提示提升代码质量和可读性。1)标量类型提示:自PHP7.0起,允许在函数参数中指定基本数据类型,如int、float等。2)返回类型提示:确保函数返回值类型的一致性。3)联合类型提示:自PHP8.0起,允许在函数参数或返回值中指定多个类型。4)可空类型提示:允许包含null值,处理可能返回空值的函数。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

ZendStudio 13.5.1 Mac
功能强大的PHP集成开发环境

记事本++7.3.1
好用且免费的代码编辑器

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

Dreamweaver CS6
视觉化网页开发工具