【面试】最容易被问到的N种排序算法！
今晚可以不加班！
面试官：小明，是吧？你都知道哪些排序算法，哪几种是稳定排序？ 小明：这个我有总结！
关于排序稳定性的定义
通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。
现实生活中稳定排序如何表现呢？
举个例子： 某次学校发奖学金，只有排在前三个的有奖，结果一排序把原来在第三位的并列第三名给弄到第四位了，他估计不会乐意?
接下来给大家用java代码演绎一下常见的几种排序，前提：有一个数组arr，要求从小到大排序。
选择排序
简单选择排序的思想是：从第一个位置开始，逐渐向后，选择后面的无序序列中的最小值放到该位置。很简单，直接上代码吧：
1//选择排序
2for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
3 int k = i;
4 for(int j = k + 1; j < arr.length; j++){// 选最小的记录
5 if(arr[j] < arr[k]){
6 k = j; //记下目前找到的最小值所在的位置
7 }
8 }
9 //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
10 if(i != k){ //交换a[i]和a[k]
11 int temp = arr[i];
12 arr[i] = arr[k];
13 arr[k] = temp;
14 }
15}那选择排序是稳定排序吗？
举个例子，假如有序列[5,8,5,2,9]按从小到大排序，第一遍排序,第一个元素“5”会和第四个元素“2”交换，那么原序列中两个“5”的相对前后顺序此时就遭到破坏了，由此可见，选择排序不是一个稳定的排序算法。
冒泡排序
冒泡排序就是相邻的两个元素之间按照要求进行比较交换，代码如下：
1// 冒泡排序
2for (int i = 0; i < arr.length - 1; i++) { //外层循环n-1
3 for (int j = 0; j < arr.length - i - 1; j++) { //内层循环n-i-1
4 if (arr[j] > arr[j + 1]) { //从第一个开始，往后两两比较大小，如果前面的比后面的大，交换位置
5 int tmp = arr[j];
6 arr[j] = arr[j + 1];
7 arr[j + 1] = tmp;
8 }
9 }
10}那冒泡排序是稳定排序吗？
因为发生在相邻的元素之间，所以，如果两个元素相等，我们是不会多此一举把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
插入排序
插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较，代码如下：
1// 插入排序
2for (int index = 1; index < length; index++) { //外层向右的index，即作为比较对象的数据的index
3 int temp = arr[index]; //用作比较的数据
4 int leftindex = index - 1;
5 while (leftindex >= 0 && arr[leftindex] > temp) { //当比到最左边或者遇到比temp小的数据时，结束循环
6 arr[leftindex + 1] = arr[leftindex];
7 leftindex--;
8 }
9 arr[leftindex + 1] = temp;//把temp放到空位上
10}一开始，左边会产生一个只有一个元素的有序序列，比较是从该有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
那插入排序是稳定排序吗？
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，代码如下：
1// 快速排序
2public static void sort(int[] a, int low, int height) {
3 int i = low;
4 int j = height;
5 if (i > j) { //放在k之前，防止下标越界
6 return;
7 }
8 int k = a[i];
9 while (i < j) {
10 while (i < j && a[j] > k) { //找出小的数
11 j--;
12 }
13 while (i < j && a[i] <= k) { //找出大的数
14 i++;
15 }
16 if (i < j) { //交换
17 int swap = a[i];
18 a[i] = a[j];
19 a[j] = swap;
20 }
21
22 }
23 //交换K
24 k = a[i];
25 a[i] = a[low];
26 a[low] = k;
27 //对左边进行排序,递归算法
28 sort(a, low, i - 1);
29 //对右边进行排序
30 sort(a, i + 1, height);
31}那快速排序是稳定排序吗？
比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第五个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序，代码如下：
1// 归并排序
2public class Main {
3
4 public static void main(String[] args) {
5 int[] arr = {11,44,23,67,88,65,34,48,9,12};
6 int[] tmp = new int[arr.length]; //新建一个临时数组存放
7 mergeSort(arr,0,arr.length-1,tmp);
8 for(int i=0;i<arr.length;i++){
9 System.out.print(arr[i]+" ");
10 }
11 }
12
13 public static void merge(int[] arr,int low,int mid,int high,int[] tmp){
14 int i = 0;
15 int j = low,k = mid+1; //左边序列和右边序列起始索引
16 while(j <= mid && k <= high){
17 if(arr[j] < arr[k]){
18 tmp[i++] = arr[j++];
19 }else{
20 tmp[i++] = arr[k++];
21 }
22 }
23 //若左边序列还有剩余，则将其全部拷贝进tmp[]中
24 while(j <= mid){
25 tmp[i++] = arr[j++];
26 }
27
28 while(k <= high){
29 tmp[i++] = arr[k++];
30 }
31
32 for(int t=0;t<i;t++){
33 arr[low+t] = tmp[t];
34 }
35 }
36
37 public static void mergeSort(int[] arr,int low,int high,int[] tmp){
38 if(low<high){
39 int mid = (low+high)/2;
40 mergeSort(arr,low,mid,tmp); //对左边序列进行归并排序
41 mergeSort(arr,mid+1,high,tmp); //对右边序列进行归并排序
42 merge(arr,low,mid,high,tmp); //合并两个有序序列
43 }
44 }
45
46}那归并排序是稳定排序吗？
可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
基数排序（又称桶子法）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
桶子法动画
代码如下：
1// 基数排序（又称桶子法）
2public static void myRadixSort(int[] arr) {
3 int max = 0;
4// 找到最大的数
5 for (int i = 0; i < arr.length; i++) {
6 if (arr[i] > max) {
7 max = arr[i];
8 }
9 }
10// 获取最大数的位数
11 int times = 0;
12 while (max > 0) {
13 max = max / 10;
14 times++;
15 }
16// 创建一个二维的list
17 List<ArrayList> list = new ArrayList<>();
18// 创建10个list（每一位有从0到9，一共10个数，每个list数组用来存放每次迭代中，0-9 每个数组中需要装入的数）
19 for (int i = 0; i < 10; i++) {
20 ArrayList list1 = new ArrayList();
21 //在二维数组中把这10个数组加进去，相当于二维数组的行，从0-9的行
22 list.add(list1);
23 }
24// 进行times次分配和收集
25 for (int i = 0; i < times; i++) {
26// 分配
27 for (int j = 0; j < arr.length; j++) {
28 int x = arr[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
29 // list.get(x) 是在返回第0的这个行的list上面的数，然后再 add(arr[j]) 是把当前的这个数添加到末尾去
30 list.get(x).add(arr[j]);
31 }
32// 收集 ------------> 把这0-9共10个list里面的数值存到一个数组里面
33 int count = 0;
34 for (int j = 0; j < 10; j++) {
35 while (list.get(j).size() > 0) {
36 // 把list这个二维list中的第j行返回并赋值给list2
37 ArrayList<Integer> list2 = list.get(j);
38 // 把list2这个数组中的第0个位置的元素，赋值给arr[count]
39 arr[count] = list2.get(0);
40 // 把list2这个数组中的第0个位置的元素删除掉，则后面的元素会自动移上来
41 list2.remove(0);
42 count++;
43 }
44 }
45 }
46}那基数排序是稳定排序吗？
由上可得，基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
希尔排序
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高，所以，希尔排序的时间复杂度会比O(n^2)好一些。代码如下：
1// 希尔排序
2int incrementNum = arr.length / 2;
3while (incrementNum >= 1) {
4 for (int i = 0; i < arr.length; i++) {
5 //进行插入排序
6 for (int j = i; j < arr.length - incrementNum; j = j + incrementNum) {
7 if (arr[j] > arr[j + incrementNum]) {
8 int temple = arr[j];
9 arr[j] = arr[j + incrementNum];
10 arr[j + incrementNum] = temple;
11 }
12 }
13 }
14 //设置新的增量
15 incrementNum = incrementNum / 2;
16}那希尔排序是稳定排序吗？
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
堆排序
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了,代码举例如下：
1// 堆排序
2public static void sort(int[] arr) {
3 //1.构建大顶堆
4 for (int i = arr.length / 2 - 1; i >= 0; i--) {
5 //从第一个非叶子结点从下至上，从右至左调整结构
6 adjustHeap(arr, i, arr.length);
7 }
8 //2.调整堆结构+交换堆顶元素与末尾元素
9 for (int j = arr.length - 1; j > 0; j--) {
10 swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
11 adjustHeap(arr, 0, j);//重新对堆进行调整
12 }
13
14}
15
16/**
17* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
18*
19* @param arr
20* @param i
21* @param length
22*/
23public static void adjustHeap(int[] arr, int i, int length) {
24 int temp = arr[i];//先取出当前元素i
25 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
26 if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
27 k++;
28 }
29 if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
30 arr[i] = arr[k];
31 i = k;
32 } else {
33 break;
34 }
35 }
36 arr[i] = temp;//将temp值放到最终的位置
37}
38
39/**
40* 交换元素
41*
42* @param arr
43* @param a
44* @param b
45*/
46public static void swap(int[] arr, int a, int b) {
47 int temp = arr[a];
48 arr[a] = arr[b];
49 arr[b] = temp;
50}那堆排序是稳定排序吗？
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
总结
- 不稳定的排序: 选择排序、快速排序、希尔排序、堆排序
- 稳定排序：冒泡排序、插入排序、归并排序、基数排序