面试中可能被问到的常用排序算法

排序算法

排序算法是一种比较简单的算法，从我们一开始接触计算机编程开始接触的可能就是排序或者搜索一类的算法，但是因为排序在其他的一些算法中应用较多，所以为了提高性能已经研究了多种排序算法。目前区别排序算法主要还是以时间复杂度，空间复杂度，稳定性等来排序，接下来我们分别分析。

稳定性算法

区别一个排序算法是否是稳定算法只需看相同的关键字在排序完成后是否保持原来两者的前后关系即可，比如对于[1,2,3,4,1],a[0]=a[4]，a[0]在a[4]之前，稳定的排序在排序完成后a[0]依旧在a[4]的前面，反之则是不稳定排序算法。

冒泡排序

基本原理

冒泡排序(Bubble Sort)是一种比较简单的排序算法。基本原理为选定一个数作为比较标准，遍历整个数组比较两个数的大小，如果顺序不对则进行交换，知道没有再需要交换的数为止。冒泡排序是稳定的排序算法
 冒泡排序算法的运作如下：
1.比较相邻的两个元素。并根据需要进行交换，如果需要正序，那么就将较大的放在后面，倒叙则将较小的放在后面。
2.对每一组相邻元素同样的操作。这步做完后，最后的元素会是最大的数。
3.外循环对除已经选择出的元素重复上面的步骤，直到没有任何一对数字需要比较，表示排序已经完成。

代码
    public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j+1);
                }
            }
        }
    }

复杂度

如果序列的初始状态是正序的，一趟扫描即可完成排序，不需要交换操作。经过n次的循环后排序完成，所以时间复杂度为O(n)，整个过程没有使用辅助空间，空间复杂度为O(1)。

选择排序

选择排序（Selection sort）是一种很简单排序算法。它要求是每一次从待排序的元素中选出最小(最大)的一个元素，存放在起始位置，然后再从剩余未排序元素中继续寻找最小(大)元素，然后放到上一位已经排好序的后面。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

选择排序算法的运作如下：
1.第一次遍历整个数据序列，查找出最大(小)的数。并将该数放在第一位置。
2.将已经排序好的位置除外，剩下的数据序列重复进行上面的操作。

代码
    public static void insertSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            //一趟之后最小的数到了下标为i的位置
            for(int j=i+1;j<arr.length;j++){
                if(arr[i] > arr[j]){
                    swap(arr, i, j);
                }
            }
        }
    }

复杂度

如果数据本身就是有序的，0次交换；最坏的情况下需要进行n-1次交换；比较操作次数固定为N^2/2，时间复杂度为O(n^2)，空间复杂度为O(1)。

直接插入排序

插入排序是比较简单的排序方法，插入排序将待排序数组分为两部分，一部分是已排序部分，另一部分则是待排序部分。最开始仅第一个数字为已排序部分。然后每次从待排序部分取出一个数，同已排序部分的数据进行比较，选出刚好前一个数比该数小，后一个数比该数大(第一位除外)，将该数放在这个位置。进过遍历后整个数组有序。

选择排序算法的运作如下：
1.将第一个数选择为已排序部分，取第二个数同第一个数比较，如果大于第一个数则不变，小于则交换位置。上述过程完成后将前两个数字作为已排序部分。
2.再次从待排序部分取出一个数字，重复上诉步骤找出该数的位置。从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
3.重复上面的步骤直到将数据全部遍历完成则表示数组有序。

代码
    public static void insertSort(int[] nums){
        int i,j;
        for(i=1;i<nums.length;i++){
            int temp = nums[i];
            //将元素后移
            for(j=i-1;j>=0&&temp<nums[j];j--){
                nums[j+1] = nums[j];
            }
            nums[j+1] = temp;
        }

    }

复杂度

在将n个元素的序列进行升序或者降序排列，采用插入排序最好情况就是序列已经是有序的了，在这种情况下，需要进行的比较操作需n-1次即可。最坏情况就是序列是反序的，那么此时需要进行的比较共有n(n-1)/2次。平均来说插入排序算法复杂度为 O(n^2)。所以插入排序不适合对于数据量比较大的排序应用。但是在需要排序的数据量很小或者若已知输入元素大致上按照顺序排列，插入排序的效率还是不错。

带哨兵的插入排序

在插入排序的时候，我们看到每一次进行比较都有两次比较操作j>=0&&temp<nums[j]，即既要保证不越界又要判断数据是否符合条件，假设在反序的情况下就几乎多出一倍的比较次数。这里我们使用一个哨兵来消除掉多的比较操作。

代码
    public static void insertWithSentinelSort(int[] nums){
        int i,j;
        for(i=1;i<nums.length;i++){
            //将第一个元素指定为哨兵
            //要求传入的数组比原数组长度大1
            nums[0] = nums[i];
            //将元素后移
            //这里只需比较数据是否符合条件
            for(j=i-1;nums[j]>nums[0];j--){
                nums[j+1] = nums[j];
            }
            nums[j+1] = nums[0];
        }
    }

添加哨兵的好处就是将原本的比较次数减少，提高了算法效率。

希尔排序

希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定的步长进行分组，对每组数据使用直接插入排序算法排序；随着步长逐渐减少，每组包含的关键词越来越多，当步长为1时，刚好就是一个插入排序。而在此时整个数据序列已经基本有序，插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性排序的效率。所以希尔排序的整体效率较高。

希尔排序的步骤：
1.选择步长大小，根据步长将数据分组
2.循环对每一组进行排序
3.修改步长的大小(一般为一半，也可以通过步长数组指定)，重复1-2操作
4.直到步长为1进行排序后停止

代码
    public static void shellSort(int[] nums){
        int size = nums.length/2;
        int i,j;
        while(size>=1){
            for(i=0;i<nums.length;i++){
                for(j=i;j+size<nums.length;j+=size){
                    if(nums[j]>nums[j+size]){
                        swap(nums, j, j+size);
                    }
                }
            }
            size/=2;
        }
    }

复杂度

希尔排序的时间复杂度分析比较复杂，因为它和所选取的步长有着直接的关系。步长的选取没有一个统一的定论，只需要使得步长最后为1即可。希尔排序的时间复杂度根据所选取的步长不同时间复杂度范围在o(n^1.3)~o(n^2)。

快速排序

快速排序是对冒泡排序的改进。

快排的基本步骤：
1.从待排序列中选取一个数(一般为第一个)，进行一次排序，将大于该数的放在该数前面，小于该数的放在其后面。
2.上述操作将待排序列分为两个独立的部分，递归的进行上面的操作，直到序列无法再被分割。
3.最后一次排序后序列中是有序的。

代码
    public static void quickSort(int[] nums, int low, int high){
        if(low<high){
            int partation = partition(nums, low, high);
            //这里返回的low值的位置已经确定了 所以不用参与排序
            quickSort(nums, 0, low-1);
            quickSort(nums, low+1, high);
        }
    }
   
    //进行一次排序 将待排序列分为两个部分
    public static int partition(int[] nums, int low, int high){
        //选取第一个值为枢纽值
        int pivo = nums[low];
        while(low<high){
            while(low<high&&nums[high]>=pivo){
                high--;
            }
            nums[low] = nums[high];
            while(low<high&&nums[low]<=pivo){
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low] = pivo;

        return low;
    }

复杂度

时间复杂度

在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归的深度就为log2n+1，即仅需递归log2n 次。时间复杂度为O(nlogn)。

最糟糕的情况就是待排序列为需要排序方向的逆序。每次划分只得到一个比上一次划分少一个记录的子序列。这时快排退化为冒泡排序。时间复杂度为O(n^2)。

快排的平均复杂度为O(nlogn)，证明过程较长，直接贴个链接吧。

空间复杂度

被快速排序所使用的空间，根据上面我们实现的代码来看，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生 o(logn)嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(logn)次的嵌套递归调用，所以它需要O(logn)的空间。最坏情况下需要 O(n)次嵌套递归调用，因此需要O(n)的空间。

归并排序

归并是指将两个及以上的有序序列合并成一个有序序列。

归并排序步骤：
1.申请一个和待排序列长度相同的空间空间该空间用来存放合并后的序列
2.设定两个数为对数组中位置的指向，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择小的元素放入到合并空间，并移动被选择的数的指针到下一位置
4.重复步骤3直到某一指针到达指定的序列尾部
5.将另一序列剩下的所有元素直接复制到合并序列尾

代码
    public static void mergeSort(int[] nums, int[] temp, int left, int right){
        if(left<right){
            int mid = (left+right)/2;
            mergeSort(nums, temp,left,mid);
            mergeSort(nums, temp,mid+1,right);
            merge(nums,temp, mid, left, right);
        }
    }

    public static void merge(int[] nums, int[] temp, int mid, int left, int right){
        int i=left,j=mid+1,k=0;
        while(i<=mid&&j<=right){
            if(nums[i]<nums[j]){
                temp[k++] = nums[i++];
            }else {
                temp[k++] = nums[j++];
            }
        }

        while(i<=mid){
            temp[k++] = nums[i++];
        }

        while(j<=right){
            temp[k++] = nums[j++];
        }
        //将temp中的元素全部拷贝到原数组中
        //这里必须将原来排好序的数组值复制回去
        //否则后续的对比前面排序长的数组排序时会出错
        //比如4 1 2 3  讲过排序后分为1 4 和2 3两组
        //如果没有将值复制回去那么合并后将是2 3 4 1
        k=0;
        while(left<=right){
            nums[left++] = temp[k++];
        }
    }

复杂度

归并排序是一种效率高且稳定的算法。但是却需要额外的空间。

归并排序的比较是分层次来归并的。第一次将序列分为两部分，第二次将第一次得到的两部分各自分为两部分。最后分割合并就类似一课二叉树。其平均时间复杂度为O(nlogn)。空间复杂度因为其需要额外长度为n的辅助空间，其空间复杂度为O(n)。

大数据量排序

上面演示的代码也被成为2-路归并排序，其核心思想是将以为数组中前后响铃的两个有序序列合并为一个有序序列。但是实际上平时我们不会使用这种排序方式。

但是归并排序使用场景还是很多的，特别是在对数量较大的序列进行排序是，比如目前我们有大量的数据存储在文本中，现在需要对其进行排序。由于内存的限制没有办法一次性加载所有的数据，这时候我们就可以使用归并排序，将大的文件分割为若干份小文件，分别对这些小文件的数据进行排序后使用归并排序再将其进行排序。并且排序过程中可以使用多线程等手段提高算法效率。

TIMSort

在JDK中，Arrays工具类为我们提高了各种类型的排序方法，Arrays.sort在JDK1.6及之前使用的是归并排序，在1.7开始使用的是TimSort排序。

TimSort算法是一种起源于归并排序和插入排序的混合排序算法，设计初衷是为了在真实世界中的各种数据中可以有较好的性能。基本工作过程是：
1.扫描数组，确定其中的单调上升段和严格单调下降段，将严格下降段反转；
2.定义最小基本片段长度，短于此的单调片段通过插入排序集中为长于此的段；
3.反复归并一些相邻片段，过程中避免归并长度相差很大的片段，直至整个排序完成，所用分段选择策略可以保证O(n log n)时间复杂性。