归并排序

归并排序相关知识

• 归并排序

  归并排序 这里使用的语言是PHP，但是语言都是相通的，用别的语言也可以实现，可以参考这里自行实现别的语言版本 /** * 归并排序 */ function mergeSort(&$arr) { $arr_len = count($arr); if ($arr_len <= 0) { return []; } merge_sort($arr, 0, $arr_len - 1); } //递归调用对arr[l...r]的范围进行排序 function merge_sort(&$arr, $l, $r) { if ($l >= $r) { return; } $mid = intval(($l + $r) / 2); merge_sort($arr, $l, $mid); merge_s
• 算法 | 归并排序

  归并排序 归并排序算法的核心就是 “归并”，将两个有序的数列合并，形成更大的有序数组。 归并排序的原理 上面说了，归并排序的核心就是“归并”。如果排序一个数组，那么将数组从中间分成前后两部分，对前后两部分分别进行排序，然后再将排序好的合并在一起，那么这样整个数组就会成为更大的有序数组。例如下面示图： 归并排序使用的思想是分治思想，即是分而治之。将复杂问题分解成两个或者多个规模相同或类似的子问题，然后继续细化，当子问题足够简单，能够被求解，那么复杂的问题也就
• 算法排序-归并排序

  　　Java系统提供的Arrays.sort函数。对于基础类型，底层使用快速排序。对于非基础类型，底层使用归并排序。请问是为什么？ 　　答：这是考虑到排序算法的稳定性。对于基础类型，相同值是无差别的，排序前后相同值的相对位置并不重要，所以选择更为高效的快速排序，尽管它是不稳定的排序算法；而对于非基础类型，排序前后相等实例的相对位置不宜改变，所以选择稳定的归并排序。 在JDK的源码中也使用了归并排序，可见归并排序的重要性。我们一起来看看归并排序吧　 　　 归并排序　　 复杂度
• java归并排序

  概述归并排序与快速排序相同，同样是借鉴二叉树的思想，时间复杂度O(n),与快速排序一样是大量数据排序的最优方式之一。思路分析归并排序是将目标数组分成左右两个数组，左右两个数组必须是有序的，然后对这两个数组合并从而实现排序。对于任意的数组都可以将所有的数据分成若干个数组，每个数组中都只有一个元素，然后两两合并。（因此，归并排序的内存开销会比快速排序多）代码实现  private void mergeSort(int[] array, int left, int right) {        if (left >= right) {            return;

归并排序相关课程

• JavaScript版数据结构与算法 轻松解决前端算法面试 从求职角度，在面试前建立自己的算法技术体系。本课程带你用JS语言解决LeetCode上的经典算法题，对每一道题都进行线上测试，每题都有时间/空间复杂度分析。结合前端实际开发情景，带你掌握数据结构与算法。

  讲师：lewis 中级 1582人正在学习

• 算法与数据结构体系课 慕课网算法名师Liuyubobobo，5年集大成之作 从0到工作5年，算法与数据结构系统解决方案

  进阶 1702人正在学习

• 算法与数据结构（C++版） 面试/评级前的算法复习技能包 任何时候学习算法都不晚，而且越早越好，这么多年，你听说过技术过时，什么时候听说过算法过时，不仅没有过时，因为机器学习、大数据的要求，算法变得越来越重要了

  讲师：liuyubobobo 中级 10486人正在学习

归并排序相关教程

• 3. 快速排序过程 在介绍完归并排序之后，我们一起来看一下快速排序的实现步骤具体是什么样的吧。同样地，和之前介绍归并排序时一样，这里我们假设待排序的序列为 [9,2,11,7,12,5]，我们按照从小到大的序列进行排序。
• 1. 快速排序算法原理 快速排序算法是基于这样的思想：从待排序的列表选择一个基准数，然后将列表中比该基准数大的放到该数的右边，比该基准数小的值放到该基准数的左边；接下来执行递归操作，对基准数左边的待排序列表执行前面同样的操作，直到左边的列表有序，对于基准数右边的待排序列表也执行前面同样的操作，直到右边的列表有序。此时，整个列表有序。即对于输入的数组 nums[left:right]：分解：以 nums[p] 为基准将 nums[left: right] 划分为三部分: nums[left:p-1]，nums[p] 和 a[p+1:right]，使得 nums[left:p-1] 中任何一个元素小于等于 nums[p]， 而 nums[p+1:right] 中任何一个元素大于等于 nums[p]；递归求解：通过递归调用快速排序算法分别对 nums[left:p -1] 和 nums[p+1:right] 进行排序；合并：由于对 nums[left:p-1] 和 nums[p+1:right] 的排序是就地进行的，所以在 nums[left:p-1] 和 nums[p+1:right] 都已排好序后，不需要执行任何计算，nums[left:right] 就已经排好序了；下面是算法示意图：快速排序算法示意图
• 2. 什么是快速排序？ 快速排序（Quick Sort），是计算机科学与技术领域中非常经典的一种排序算法，应用分治思想进行排序。快速排序由于其时间复杂度优于大部分的排序算法，因而命名为快速排序。快速排序实现的核心思想就是在待排序序列中选择一个基准值，然后将小于基准值的数字放在基准值左边，大于基准值的数字放在基准值右边，然后左右两边递归排序，整个排序过程中最关键部分就是寻找基准值在待排序序列中的索引位置。
• 2.1 快速排序步骤 快速排序算法的核心是分治算法，所谓分治（Divide and Conquer）就是将一个复杂的问题分成两个或者多个相同或者相似的子问题，再把这些子问题分成多个相同或者相似的子问题，直到子问题能够被简单求解，把子问题的解合起来就是原始问题的解。快排的分治思维在于将大的数组拆分为两个需要排序的左右子数组，再对子数组套用相同算法，直到子树组只有一个数字，一个数字的数组本身就是有序的，构成了原子问题的解。快排的核心步骤拆分为：（1）选择基准：对于数组 A，选择一个数字作为基准值（pivot），习惯选择数组第一个元素作为 pivot；（2）构造分区：定义 left 和 right 左右指针，将小于基准的元素移动到左边，将大于基准的元素移动到右边；（3）递归求解：对于基准左边的数组 A1、基准右边的数组 A2 重复第一步和第二步，直到所有的子树组已经满足排序性质（子数组为空或者子树组只有一个元素）。快速排序的算法实现代码以及解析，示例： public void quicksort(int[] A,int left, int right) { //1. 递归终止条件，如果不构成数组结束算法 if(left > right) return; int i, j, t, pivot; //2. 选择第一个元素作为pivot pivot = A[left]; i = left; j = right; while(i != j) { //3.1 这里要注意顺序，必须先从右边开始找到第一个比pivot小的数 while(A[j] >= pivot && i < j) j--; //3.2 然后从左边找到第一个比pivot大的数字 while(A[i] <= pivot && i < j) i++; //3.3 交换两个数在数组中的位置 if(i < j) { t = A[i]; A[i] = A[j]; A[j] = t; } } //4. 最终将基准数归位 A[left] = A[i]; A[i] = pivot; //递归处理左边的分数组 quicksort(A,left, i-1); //递归处理右边的分数组 quicksort(A,i+1, right); }
• 4. 实例测试快速排序代码 上面的函数中我们已经做了详细的注释，和前面第二张图描述的过程是一致的。接下来我们来对该方法进行测试：PS C:\Users\spyinx\Desktop\学习教程\慕课网教程\算法慕课教程\code> pythonPython 3.8.2 (tags/v3.8.2:7b3ab59, Feb 25 2020, 22:45:29) [MSC v.1916 32 bit (Intel)] on win32Type "help", "copyright", "credits" or "license" for more information.>>> from sort_algorithms import get_num_position>>> nums = [10, 2, 16, 8, 4, 17, 12, 11]>>> get_num_position(nums, 0, len(nums) - 1) 3>>> nums [4, 2, 8, 10, 16, 17, 12, 11]可以看到，代码确实实现了我们想要的结果，将比 10 小的全部移动到了左边，比 10 大的全部移动到了右边。接下来就是实现快速排序算法。从第一张图中很明显可以看到快排算法是一个递归的过程，因此我们用递归完成快排算法，代码如下：# 代码位置：sort_algorithms.pydef quick_sort(nums, start, end): """ 快速排序算法 """ if start >= end: return pos = get_num_position(nums, start, end) # 左边递归下去，直到排好序 quick_sort(nums, start, pos - 1) # 右边递归下去，直到排好序 quick_sort(nums, pos + 1, end)对于递归方法，后面会详细介绍到。这里一定要注意，使用递归过程一定要先写终止条件，不然函数无穷递归下去，就会导致堆栈溢出错误。接下来我们测试这个快排算法：>>> from sort_algorithms import quick_sort>>> nums = [8, 7, 9, 6, 11, 3, 12, 20, 9, 5, 1, 10]>>> quick_sort(nums, 0, len(nums) - 1)>>> nums[1, 3, 5, 6, 7, 8, 9, 9, 10, 11, 12, 20] 可以看到上面的代码实现了我们想要的排序效果。接下来我们分析下快排算法，它被人们研究的最多，提出了许多改进和优化的方案，我们简单聊一下快排算法的优化方案。
• 5.3 排序 关于排序中间操作，有下面几个常用方法：sorted()：产生一个新流，其中按照自然顺序排序；sorted(Comparator com)：产生一个新流，其中按照比较器顺序排序。请查看如下实例：1258运行结果：1 8 9 10 12 20上面实例中，我们调用sorted()方法对集合元素进行了从小到大的自然排序，那么如果想要实现从大到小排序，任何实现呢？此时就要用到sorted(Comparator com)方法定制排序，查看如下实例：1259运行结果：201210981实例中，sorted()方法接收的参数是一个函数式接口Comparator，因此使用Lambda表达式创建函数式接口实例即可，Lambda体调用整型的比较方法，对返回的整型值做一个取反即可。

归并排序相关搜索

g area gamma函数 gcc 下载 generic genymotion gesture getattribute getchar getdocument getelementbyid getelementsbytagname getmonth getproperty gets getty git clone git pull git push f git 命令 git 使用

查看更多慕课网实用课程