网站建设近义词,中国风网站怎么配色,福州服务专业公司网站建设,pa66用途障车做网站排序算法是数据结构与算法中最基本的算法之一#xff0c;其作用就是将一些可以比较大小的数据进行有规律的排序#xff0c;而想要实现这种排序就拥有很多种方法~
那么我将通过几篇文章#xff0c;将排序算法中各种算法细化的#xff0c;详尽的为大家呈现出来#xff1a; …排序算法是数据结构与算法中最基本的算法之一其作用就是将一些可以比较大小的数据进行有规律的排序而想要实现这种排序就拥有很多种方法~
那么我将通过几篇文章将排序算法中各种算法细化的详尽的为大家呈现出来 非线性时间比较类 插入类排序数据结构与算法之排序算法-插入排序-CSDN博客 直接插入排序 希尔排序 交换类排序数据结构与算法之排序算法-快速排序(分治)-CSDN博客 冒泡排序 冒泡排序-优化 快速排序(Hoare挖坑法前后指针法) 快速排序-优化 选择类排序数据结构与算法之排序算法-选择排序-CSDN博客 简单选择排序 堆排序 归并类排序[本篇] 归并排序 线性时间非比较类 非比较类排序数据结构与算法之排序算法-(计数,桶,基数排序)-CSDN博客 计数排序 桶排序 基数排序 一、归并排序 稳定性稳定 时间复杂度O(n logn) 额外空间复杂度O(n) 归并排序也是一种在实际应用中比较常用的排序算法这是因为它的速度和快速排序一样也是O(n logn)并且相较于快速排序归并排序还具有稳定性
但唯一的缺点就是归并排序并不是原地算法而是需要开辟一个和原数组一样大小的辅助数组所以归并排序的额外空间复杂度为O(n)
① 习题引入:合并排序的数组 首先为什么要使用这题作为习题引入呢我们先接着上面的话题研究研究归并排序
上面我们提到归并排序的时间复杂度为O(n logn)从这里就不难猜出归并排序的算法大概也是和快排类似是一种不断将数组分为两份的排序算法也就是分治
归并排序的基本思想取数组的开始位置为left结束位置为right不断对数组取中间下标mid使数组均匀的被分成两个新数组并继续对新数组进行如上操作。
直到left right(数组中只有一个元素)时我们认为此时这个数组为有序数组将它向上递归。按照这个思想我们后续递归回去的数组也都是有序的而如此便能够提到我们上面说的这道习题了合并排序的数组 思路提示
合并有序的数组想必对大家来说肯定非常简单的~毕竟我们之前在学习链表的时候就实现过类似的题目而合并有序链表应该是比合并有序数组要更加复杂一点点的。
我们只需要创建一个新的数组 arr 使他的长度等于两个数组之和然后遍历两个数组使用双指针的思想用cur1遍历 arr1用cur2遍历arr2将较小的元素放入arr中随后移动cur1/cur2。
(最后可能会有一个数组没被加入完记得处理一下就好) 代码示例
class Solution {public void merge(int[] A, int m, int[] B, int n) {int[] nums new int[m n];int cur1 0;int cur2 0;int i 0;while(cur1 m cur2 n){nums[i] A[cur1] B[cur2] ? A[cur1] : B[cur2];}while(cur1 m) nums[i] A[cur1];while(cur2 n) nums[i] B[cur2];for(i 0;i n m;i){A[i] nums[i];}}
}
② 归并排序
而上面我们又提到了将有序的数组向上递归排序后再递归这样多此递归下来我们就能够得到我们想要的有序数组。
这样就正好验证了归并排序的排序速度与其中数组的有序性并没有关系也就是说它是稳定的O(n logn)的排序~
⭐ 图示 代码示例 public static int[] arr;public int[] sortArray(int[] nums) {arr new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}public static void mergeSort(int[] array, int left, int right) {if (left right) {return;}int mid left (right - left) / 2;mergeSort(array, left, mid);mergeSort(array, mid 1, right);int cur1 left;int cur2 mid 1;int i 0;while (cur1 mid cur2 right) {arr[i] array[cur1] array[cur2] ? array[cur1] : array[cur2];}while (cur1 mid) {arr[i] array[cur1];}while (cur2 right) {arr[i] array[cur2];}for (i left; i right; i) {array[i] arr[i - left];}} 那么上次我们学习的快速排序优化版能跑多少ms呢能跑到 30多ms~ 而归并排序跑了 28ms再一次证明了它O(n logn)的速度是多么的稳定(内存消耗的多就是了)。
那么这篇关于归并排序的文章到这里就结束啦作者能力有限如果有哪里说的不够清楚或者不够准确还请各位在评论区多多指出我也会虚心学习的我们下次再见啦
