常用排序算法（一）

排序是笔试面试的常考知识点，检验应聘者对排序这类基本算法的接受程度和数据结构的理解。在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)的算法，之后的文章将详解更高级的排序算法。