排序是笔试面试的常考知识点，检验应聘者对排序这类基本算法的接受程度和数据结构的理解。在2017春季暑期实习生招聘过程中该类提醒常被问及。特此加以整理。
常见的排序算法概述
相信在学习C语言和数据结构的时候冒泡排序和选择排序是肯定会讲的，其他几类算法也多少提及。稳定性指的是如果存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变则该算法稳定，反之，不稳定。通过上图发现，复杂性越高的算法时间复杂度低。冒泡排序、选择排序、直接插入排序算是简单的排序算法，其时间复杂度为O(n^2)。本篇为该专题的开篇，先从这三个简单排序算法入手，先易后难。
冒泡排序
冒泡排序就是一种最古老的，一趟一趟，每趟两两比较确定该趟排序最值并放到相应位置的算法。
上图实例，以第一趟为例。
第一次比较：49 > 38，交换两个数，数组状态：
38 49 65 97 76 13 27 49
第二次比较：49 < 65，无需交换，数组不变
第三次比较：65 < 97，无需交换，数组不变
第四次比较：97 > 76，交换两个数，数组状态：
38 49 65 76 97 13 27 49
第五次比较：97 > 13，交换两个数，数组状态：
38 49 65 76 13 97 27 49
第六次比较：97 > 27，交换两个数，数组状态：
38 49 65 76 13 27 97 49
第七次比较：97 > 49，交换两个数，数组状态：
38 49 65 76 13 27 49 97
经过一趟排序，数组最大值已就位，之后的排序以此类推，但只需要比较到上次排序的最大值之前即可。那么如果数组有n个元素，那么就需要n - 1趟排序呗。其实不一定。如果一趟排序，数组所有元素均未发生交换操作，即说明所有元素均已就位，无需之后的排序过程。
public void bubbleSort(int[] nums){
boolean flag ; //标记该趟排序是否发生交换
for(int i = 0; i < nums.length; i++){
flag = false; //每趟排序前初始化
for(int j = 0; j < nums.length - 1 -i; j++){
if(nums[j] > nums[j + 1]){ //若发生交换，交换的同时更新flag
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
flag = true;
}
}
if(!flag){ //未发生交换，跳出排序
break;
}
}
}
选择排序
冒泡排序的过程可以看做只要发现顺序有问题就做一次交换，选择排序和冒泡排序的不同就在于每趟排序只做一次交换，只是每次比较若发现顺序有问题就记录应交换操作的下标，当遍历完成后再做交换操作。
推理就不推了，直接看代码：
public void chooseSort(int[] nums){
int min; //升序排序，记录每趟最小值的下标
for(int i = 0; i < nums.length; i++){
min = i; //初始化为本次排序的第一个数
for(int j = i + 1; j < nums.length; j++){
if(nums[min] > nums[j]){ //顺序有问题，更新min即可
min = j;
}
}
if(min != i){ //发现更新，交换操作
int temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
}
}
}
选择排序能不能像冒泡排序一样做一个优化呢？并不能。每趟排序只做一次交换，即使本次不发生，也不能保证当前元素之后的数组元素顺序没有问题，所以只能乖乖比较n - 1次。所以时间复杂度也是O(n^2)。
直接插入排序
直接插入排序的思想应该是很好理解的，就想平常打扑克对扑克牌排序一样，从当前位置开始向前寻找，知道找到适合自己的位置为止。
public void insertSort(int[] nums){
for(int i = 1; i < nums.length; i++){
if(nums[i] < nums[i - 1]){
for(int j = i; j >= 1; j--){ //从当前位置开始向前寻找
if(nums[j] < nums[j - 1]){ //顺序出问题就交换
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
}else{ //因为之前的数组元素已排序，无需再进行比较
break;
}
}
}
}
}
本篇探讨的方法均是时间复杂度为O(n^2)的算法，之后的文章将详解更高级的排序算法。
