财政局网站建设方案,知名的设计公司网站,跨境电商建站工具,网站登录按钮点击没反应什么原因前言 算法是程序的灵魂#xff0c;一个优秀的程序是可以在海量的数据中#xff0c;仍保持高效计算。目前各大厂的面试要求也越来越高#xff0c;算法肯定会要去。如果你不想去大厂#xff0c;只想去小公司#xff0c;或许并不需要要求算法。但是你永远只能当一个代码工人一个优秀的程序是可以在海量的数据中仍保持高效计算。目前各大厂的面试要求也越来越高算法肯定会要去。如果你不想去大厂只想去小公司或许并不需要要求算法。但是你永远只能当一个代码工人也就是跟搬砖的没区别。可能一两年后你就会被淘汰。 如果不想永远当个代码工人就在业余时间学学数据结构和算法。 今天就来分享一个朋友阿里四面挂了的排序算法题912. 排序数组, 排序数组这道题本身是没有规定使用什么排序算法的但面试官指定需要使用归并排序算法来解答肯定是有他道理的。
我们知道排序算法有很多大致有如下几种 其中归并排序应该是使用得最多的几种之一Java中Arrays.sort()采用了一种名为TimSort的排序算法就是归并排序的优化版本。归并排序自身的优点有二首先是因为它的平均时间复杂度低为O(N*logN)其次它是稳定的排序即相等元素的顺序不会改变除了这两点优点之外其蕴含的分治思想是可以用来解决我们许多算法问题的这也是面试官为什么要指定归并排序的原因。好了废话不多说我们接下来具体看看归并排序算法是如何实现的吧。
归并排序递归版
归并排序MERGE-SORT是利用归并的思想实现的排序方法该算法采用经典的分治策略即分为两步分与治。
1. 分先递归分解数组成子数组
2. 治将分阶段得到的子数组按顺序合并
我们来具体看看例子假设我们现在给定一个数组[63271354]我们需要使用归并算法对其排序其大致过程如下图所示 分阶段可以理解为就是递归拆分子序列的过程递归的深度为log2n。而治的阶段则是将两个子序列进行排序的过程我们通过图解看看治阶段最后一步中是如何将[2367]和[1345]这两个数组合并的。 图中左边是复制的临时数组而右边是原数组我们将左右指针对应的值进行大小比较将较小的那个数放入原数组中然后将相应的指针右移。比如第一步中我们比较左边指针L指向的2和右指针R指向的1R指向的1小则把1放入原数组中的第一个位置中然后R指针向右移动。后面再继续直到左边临时数组的元素都按序覆盖了右边的原数组。最后我们通过上图再结合源码来看看吧
class Solution {public int[] sortArray(int[] nums) {sort(0, nums.length - 1, nums);return nums;}// 分递归二分private void sort(int l, int r, int[] nums) {if (l r) return;int mid (l r) / 2;sort(l, mid, nums);sort(mid 1, r, nums);merge(l, mid, r, nums);}// 治将nums[l...mid]和nums[mid1...r]两部分进行归并private void merge(int l, int mid, int r, int[] nums) {int[] aux Arrays.copyOfRange(nums, l, r 1);int lp l, rp mid 1;for (int i lp; i r; i ) {if (lp mid) { // 如果左半部分元素已经全部处理完毕nums[i] aux[rp - l];rp ;} else if (rp r) { // 如果右半部分元素已经全部处理完毕nums[i] aux[lp - l];lp ;} else if (aux[lp-l] aux[rp - l]) { // 左半部分所指元素 右半部分所指元素nums[i] aux[rp - l];rp ;} else { // 左半部分所指元素 右半部分所指元素nums[i] aux[lp - l];lp ;}}}
}
复制代码
我们可以看到分阶段的时间复杂度是logN而合并阶段的时间复杂度是N所以归并算法的时间复杂度是O(N*logN)因为每次合并都需要对应范围内的数组所以其空间复杂度是O(N);
归并排序迭代版
上面的归并排序是通过递归二分的方法进行数组切分的其实我们也可以通过迭代的方法来完成分这步看下图 其因为数组所以我们直接通过迭代从1开始合并其中sz就是合并的长度这种方法也可以称为自底向上的归并其具体的代码如下
class Solution {public int[] sortArray(int[] nums) {int n nums.length;// sz 1,2,4,8 ... 排序for (int sz 1; sz n; sz * 2) {// 对 arr[i...isz-1] 和 arr[isz...i2*sz-1] 进行归并for (int i 0; i n - sz; i 2*sz ) {merge(i, i sz - 1, Math.min(iszsz-1, n-1), nums);}}return nums;}// 和递归版一样private void merge(int l, int mid, int r, int[] nums) {int[] aux Arrays.copyOfRange(nums, l, r 1);int lp l, rp mid 1;for (int i lp; i r; i ) {if (lp mid) {nums[i] aux[rp - l];rp ;} else if (rp r) {nums[i] aux[lp - l];lp ;} else if (aux[lp-l] aux[rp - l]) {nums[i] aux[rp - l];rp ;} else {nums[i] aux[lp - l];lp ;}}}
}
复制代码
总结
归并排序是一种十分高效的排序算法其时间复杂度为O(N*logN)。归并排序的最好最坏的平均时间复杂度均为O(nlogn)排序后相等的元素的顺序不会改变所以也是一种稳定的排序算法。归并排序被应用在许多地方其java中Arrays.sort()采用了一种名为TimSort的排序算法其就是归并排序的优化版本。
