强化面试中常用的算法 - 排序

目录

1 回顾
2 课程内容
3 排序算法
      3.1 冒泡排序
      3.2 插入排序
      3.3 归并排序
      3.4 快速排序
      3.5 拓扑排序

一 回顾

      前两次总结了常用的数据结构和复杂的数据结构。它们是学好算法的基石，只有把它们的性质牢牢掌握了，才能在算法中游刃有余。
      接下来的会总结一些在面试中、工作中常用到的算法，通过分析经典的例题，来达到巩固知识的效果。

二 课程内容

      算法的学习其实是一个提高思维能力的过程。无论是在面试，还是在实际的生活、工作中，我们都会碰到一些从未经历的问题，通常我们会按照已经拥有的经验来推敲它们，我们会罗列出各种方法来讨论它们的可行性、风险性，最后选择最佳的解决办法。
      我们学习算法是一样的，如何应对算法面试？
      1.遇到新问题不要慌张，先想出最直观的解法；
      2.直观解法大多数情况下不是最优的，却可以帮你打通思路；
      3.理清解决问题的各个步骤后，根据问题核心来优化某些步骤即可。
      这次总结的是排序算法。

三 排序算法

      排序算法我们肯定都是听过的，关于排序算法，我觉得有以下几种需要掌握。
基本的排序算法【简单直接助你迅速写出没有bug的代码】

• 冒泡排序 / Bubble Sort
• 插入排序 / Insertion Sort

常考的排序算法【解决绝大部分涉及排序问题的关键】

• 归并排序 / Merge Sort
• 快速排序 / Quick Sort
• 拓扑排序 / Togological Sort

其他的排序算法【掌握好它的解题思路能开阔解题思路】

• 堆排序 / Heap Sort
• 桶排序 / Bucket Sort

      在这些排序算法中，冒泡排序和插入排序是最基础的，不要小看它们，因为这两种算法的思想简单，直接。面试官有时候就喜欢拿它来考察你的基础知识，并且看看你能不能快速的写出，没有bug代码。在面试中，归并排序、快速排序和拓扑排序的思想是解决绝大部分涉及排序问题的关键。

3.1 冒泡排序

冒泡排序的算法思想：
      给定一个数组，我们把数组里的元素统统倒到水池中，这些元素将通过相互之间的比较，按照大小顺序，一个一个像气泡一样浮出水面。具体的实现方法是：
      1.每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换；
      2.直到这一轮当中最大或最小的元素被放置在数组的尾部；
      3.然后，不断地重复这个过程，直到所有元素都排好位置。
      可以看到，元素相互比较的过程就是冒泡排序的核心操作。

例题：
      给定数组[2,1,7,9,5,8]，要求按照从左到右、从小到大的顺序进行排序。

解题思路：
      我们可以从左到右依次冒泡，把较大的数往右边挪动就可以了。
流程：
      1.首先，指针指向第一个数，比较第一个数和第二个数的大小。如果前者大于后者，两两交换。
      2.接下来，指针往后移动，接着比较，直到第一轮比较结束。
      3.接着第二轮，重复一二操作。
      4.最后排序完成。

核心代码：

void sort(int[]	nums){boolean	hasChange = true;for	(int i = 0;	i < nums.length	- 1	&& hasChange;i++){hasChange =	false;for(int	j =	0;j < nums.length -	1 -	i;j++){if(nums[j] > nums[j	+ 1]){swap(nums,j,j +	1);hasChange =	true;}}}
}

冒泡排序算法分析：

空间复杂度：O(1)
      假设数组的元素个数是n，整个排序的过程中，直接在给定的数组里进行元素的两两交换。所以空间复杂度是O(1)。

时间复杂度：O(n²)
‣ 情景⼀：给定的数组按照顺序已经排好
      只需要进⾏n - 1次的⽐较，两两交换次数为0，时间复杂度是O(n)，这是最好的情况。

‣ 情景⼆：给定的数组按照逆序排列
      需要进⾏n(n - 1) / 2次⽐较，时间复杂度是O(n²)，这是最坏的情况。

‣ 情景三：给定的数组杂乱⽆章
      在这种情况下，平均时间复杂度是O(n²)。

3.2 插入排序

与冒泡排序对⽐
      在冒泡排序中，经过每⼀轮的排序处理后，数组后端的数是排好序的；
      在插⼊排序中，经过每⼀轮的排序处理后，数组前端的数都是排好序的。

插⼊排序的算法思想
      不断地将尚未排好序的数插⼊到已经排好序的部分。

例题：
      对数组[2,1,7,9,5,8]进行插入排序，通过具体的操作来更好地理解它的算法思想。

解题思路：
      1.首先，将数组分为左右两个部分，左边是已经排好的部分，右边是还没排好的部分。
      2.一开始左边只有一个元素，也就是arr[0]，然后我们对右边的元素一个一个遍历，与左边比较。
      3.右边的元素与左边的进行比较，从后到前比，直到排序完毕。

核心代码：

void sort(int[]	nums){for(int	i =	1,j,urrent;	i <	nums.length;i++){current	=	nums[i];for(j =	i -	1;j	>= 0 &&	nums[j]	> current;j--){nums[j + 1]	= nums[j];}nums[j + 1]	= current;}
}

插入排序算法分析：

空间复杂度：O(1)
      假设数组的元素个数是n，整个排序的过程中，直接在给定的数组⾥进⾏元素的两两交换。所以空间复杂度为O(1)。

时间复杂度：O(n²)
‣ 情景⼀：给定的数组按照顺序已经排好
      只需要进⾏n - 1次的⽐较，两两交换次数为0，时间复杂度是O(n)，这是最好的情况。
‣ 情景⼆：给定的数组按照逆序排列
      需要进⾏n(n - 1) / 2次⽐较，时间复杂度是O(n²)，这是最坏的情况。
‣ 情景三：给定的数组杂乱⽆章
      在这种情况下，平均时间复杂度是O(n²)。

在这里建议大家去看一下LeetCode第147题。

3.3 归并排序

      归并排序的核心思想是分治。

分治的思想
      归并排序的核⼼思想是分治，把⼀个复杂问题拆分成若⼲个⼦问题来求解。然后把子问题分治成更小的问题，直到问题可以简单的直接求解。那么原问题的解，就是子问题解的合并。

归并排序的算法思想
      把数组从中间划分成两个⼦数组；
      ⼀直递归地把⼦数组划分成更⼩的⼦数组，直到⼦数组⾥⾯只有⼀个元素；
      依次按照递归的返回顺序，不断地合并排好序的⼦数组，直到最后把整个数组的顺序排好。

归并排序的主体函数

void sort(int[]	A,int lo,int hi){if(lo >= hi) return;int mid	= lo + (hi - lo) / 2;sort(A,	lo,	mid);sort(A,	mid	+ 1, hi);merge(A,lo,	mid,hi);
}

merge

void merge(int[] nums,int lo,int mid,int hi){int[] copy = nums.clone();int	k =	lo,i = lo,j = mid +	1;while(k	<= hi){if (i >	mid){nums[k++] =	copy[j++];}else if(j > hi){nums[k++] =	copy[i++];}else if(copy[j] < copy[i]){nums[k++] = copy[j++];}else{nums[k++] =	copy[i++];}}
}

例题
      如何利⽤归并排序算法对数组[2, 1, 7, 9, 5, 8]进⾏排序？

解题思路：

      分治如下：

      接下来，递归的合并子数组，首先合并[1]、[2]为[1,2]，然后合并[1,2]，7为[1,2,7]，接下来就是右边，以此类推，最后排序完成。

分治完如何实现排序呢？
      分治之后每次合并都是左右两个数组，我们可以依次遍历两个数组，将其按大小排到一个新数组中，然后重复进行，要知道的是，每次使用的左右两个数组都是排好序的。

归并排序算法分析：
时间复杂度：T(n)
      归并算法是⼀个不断递归的过程，假设数组的元素个数是n，我们把这个规模为n的问题，分成两个规模为n/2的子问题，每个子问题的时间复杂度就是T(n/2)，那么两个子问题的复杂度就是2*T(n/2)，当两个子问题都被解决，也就是两个子数组都排序完了，我们需要将它们合并，合并的复杂度是多少呢？很简单，一共有n个元素，每次都要进行最多（n-1）次的比较，所以合并的复杂度是O(n)。
      所以时间复杂度是T(n)的函数：T(n) = 2*T(n/2) + O(n)

怎么解这个公式呢

      对于规模为n的问题，⼀共要进⾏log(n)层的⼤⼩切分；每⼀层的合并复杂度都是O(n)；所以整体的复杂度就是O(nlogn)。

空间复杂度：O(n)

      由于合并n个元素需要分配⼀个⼤⼩为n的额外数组，合并完成之后，这个数组的空间就会被释放。所以算法的空间复杂度就是O(n)。

      归并算法是一个稳定的算法，归并排序的思想很重要，其中对两个有序数组合并的操作，在很多面试题里都有用到，建议大家一定要把这个算法练熟。

3.4 快速排序

快速排序的算法思想

      快速排序也采⽤了分治的思想；
      把原始的数组筛选成较⼩和较⼤的两个⼦数组，然后递归地排序两个⼦数组；
      在分成较⼩和较⼤的两个⼦数组过程中，如何选定⼀个基准值尤为关键。

      打个比方：现在要把班里的所有同学，按照高矮顺序排成一排，老师先随机的挑选同学A，然后让所有同学和A同学比高矮，比A矮的站在A的左边，比A高的站在A的右边。接下来，老师分别在左边和右边的同学里，选择了同学B和同学C，然后不断的筛选和排列下去。

快速排序的主体函数

void sort(int[]	nums,int lo,int	hi){if(lo >= hi) return;int	p = partition(nums,lo,hi);sort(nums, lo, p - 1);sort(nums, p + 1, hi);
}

partition函数

int partition(int[]	nums,int lo,int	hi){swap(nums,randRange(lo,hi),hi);int	i,j;for	(i = lo,j = lo;j < hi;j++){if(nums[j] <= nums[hi]){swap(nums,i++,j);}}swap(nums,i,j);return	i;
}

快速排序算法分析：

最优情况下的时间复杂度

      T(n) = 2*T(n/2) + O(n)

O(n)是怎么得出来的呢？

      把规模⼤⼩为n的问题分解成n/2的两个⼦问题；
      和基准值进⾏n-1次⽐较，n-1次⽐较的复杂度就是O(n)；
      所以快速排序的复杂度也是O(nlogn)。

最复杂的情况

      每次在选择基准值的时候；
      都不幸选择了⼦数组⾥的最⼤或最⼩值；
      其中⼀个⼦数组⻓度为1；
      另⼀个⻓度只⽐⽗数组少1。

空间复杂度：O(logn)

      和归并排序不同，快速排序在每次递归的过程中；
      只需要开辟O(1)的存储空间来完成交换操作实现直接对数组的修改；
      ⽽递归次数为logn，所以它的整体空间复杂度完全取决于压堆栈的次数。

3.5 拓扑排序

应⽤场合
      拓扑排序就是要将图论⾥的顶点按照相连的性质进⾏排序

前提
      必须是有向图
      图⾥没有环

算法思想
      ⽤图的数据结构去描述问题，然后利⽤⼴度优先搜索或深度优先搜索进⾏拓扑排序。

例题
      有⼀个学⽣想要修完5⻔课程的学分，这5⻔课程分别⽤1、2、3、4、5来表示，现在已知学习这些课程有如下的要求：
      •课程2和4依赖于课程1
      •课程3依赖于课程2和4
      •课程4依赖于课程1和2
      •课程5依赖于课程3和4
      那么这个学⽣应该按照怎样的顺序来学习这5⻔课程呢？

解题思路：
      我们可以把这五门课程看成是一个图里的五个顶点，用有向线段按照它们的相互关系连起来，于是得到下图：

      首先可以看到，这个有向图里没有环，无论从哪个顶点出发都不会回到那个顶点，并且，这个图里并没有孤岛出现，因此我们可以对它进行拓扑排序。

过程：
      1.一开始对每个顶点统计它们各自的前驱，也就是入度；
      2.然后选择一个没有前驱，也就是入度为0的顶点，在这里是顶点1；
      3.将找到的顶点输出，同时删除它的有向边，并更新顶点的入读。
      4.接下来重复一二三步骤直到结束。

核心代码：

void sort(){Queue<Integer> q = new LinkedList();for(int	v =	0;v	< V; v++){if(indegree[v] == 0) q.add(v);}while(!q.isEmpty()){int	v = q.poll();print(v);for(int	u =	0;u < adj[v].length; u++){if	(--indegree[u] == 0){q.add(u);}}}
}

拓扑排序算法分析

时间复杂度：O(n)
      统计顶点的⼊度需要O(n)的时间；
      接下来每个顶点被遍历⼀次，同样需要O(n)的时间。