[Java]为啥笔试面试经常手写排序算法
手撕排序算法在IT开发类职位校招中出现的频率非常的高。
普通小公司一般让你写一个简单排序，具体是什么排序也不关心，能写出一个就行；一二线大公司考查的一般是高级排序，而且会随机指定。
我们选择了最常见的两种冒泡排序算法进行讲解，一种是普通冒泡排序，另一种是冒泡的高级算法——快速排序。
大家按照自己校招的目标层次可能认领。
在开始之前，先解答一类同学的问题：这个问题有什么难的？对数组排序，一句代码就搞定
Arrays.sort()；
这就是没理解这道题考察的意图，不是考察你java API的使用，而是看看你的思维和代码编程能力。
开发工程师的主要工作就是处理各种逻辑。
比如给你一个真实的工作需求，让你把一个数据作排序，但是相同的数只保留两个，或者给一个字符串按第个字母进行排序。
只会使用API或者粘贴复制是远远不够的，
而排序算法是逻辑最直接的，最好表达，也是行数较少的思维考查，所以笔试面试里见面的次数就比较多。
01-冒泡排序
冒泡是最简单的一种排序，但是一定要理解“冒泡”的含义。
有时候让面试者写一个冒泡排序，但是他给的却是选择排序。冒泡排序有如下几个要点
1. 冒泡是数据a相邻的两个数进行比较，比如前面的数比后面的数大，那么就发生交换。
if(a[j] > a[j +1]){
int temp = a[j +1];
a[j+1] = a[j]
a[j] = temp;
}
2. 第一轮从第1个数开始两两比较，一轮下来，最大的数冒泡到了数组最后，但是前面的数还是无序的（正常情况下）
for(int j = 0 ; j < a.size-1 ; j ++){
//1中的代码
}
3. 然后对每轮进行一次冒泡，轮数是固定的，是数组长度-1，得到外循环
for(int i = 0; i< a.size -1 ; 1++)
4.因为每轮最后一位数是确定的，不需要再参与下一次的排序，所以内循环的后长度不断缩小,修改2
for(int i = 0; i< a.size -1 ; 1++){
for(int j =0 ; j < a.size - i-1 ; j++ ){
//1中的代码
}
}
5. 冒泡排序还可以加一种优化思路，如果一轮冒泡，没有发生一次交换，即对于数组中任意相邻的两个数，前面的数都小于等于后面的数。
实际上已经排序完成。
02-快速排序
快速排序是冒泡的改进高级排序，数据结构里常见的高级排序时间复杂度都是O(N*logN)。
很多同学不理解这个时间复杂度，简单来说，就是每轮比较都把数组分为两部分，就是每轮时间都减半，那么n轮就是log级别的。
快速排序要点如下：（如果不理解，可以去官网看视频讲解）
1. 快速排序就是每轮把数组分为两部分（长度不一定相等），然后两边再不断分割，最后变成长度为1的全部有序单元
这个时候还完全不理解快速排序的思想，就可以实现下列代码
void quickSort(int[] s, int l, int r){
if (l < r) {
int i = patition(s, l, r);//patition是具体的排序过程
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
2. 每次排序就是找到一个基准点，一般采用数组的第一个数，然后按照一定规则冒泡，最后找到它的位置。
在它左边的数比它小，在它右边的数比它大。返回的是基准数最后的位置，用于1中的数组递归切分。
这个时候也是还不知道具体的分割方法，但是不影响写出以下代码。
int patition(int[] s, int l, int r) {
int i = l, j = r; int x = s[l]; //s[l]即s[i]就是第一个坑
while (i < j) {
//具体的单轮冒泡过程，现在还不知道
} //退出时，i等于j。将x填到这个坑中。
s[i] = x;
return i;
}
3. 每轮把当前数组分为左小右大的过程，是快排的难点和精髓。重点是找到每个数放置的位置。
因为基准数是第1个数，如果简单的从前往后移动，比基数小还好处理，直接不动，但是当前数比基准数大，这个数放在哪个位置，就很难解决，因为基准还要往右走。
所以简单从前往后不实用。
数据结构教材上使用的方法，俗称“挖坑法”。
设置基准数x=a[0]后，a[0]就空出来了，因为左小，也就是要找到一个比基准数小的数放到这个空出的坑里。
从后往前j找比基准数小的，放到左边的这个坑里
while(i < j && s[j] >= x)
j--;
if(i < j) {
s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
i++;
}
这时候j的位置，也是右边出现了一个空的坑，需要找一个比基准数大的数填它（右大）。
那就从前i往后找比基准数大的数，放到右侧j的位置
while(i < j && s[i] < x)
i++;
if(i < j) {
s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
j--;
}
反复填坑，直到i = j，这时候就说明基准数的前面都小于当前数，右边都大于。
4. 把3中的逻辑放到2中的具体逻辑部分，代码就完成了。
