排序在很多场合都能用到，并且排序的方法有很多，下面介绍的是七种比较常见的基于比较的排序。

稳定性：能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

注：一个稳定的排序是由代码决定的，稳定的排序可以变为不稳定的排序，而不稳定的排序一定不能变为稳定的排序。

一、基数排序

“基于比较”可以有些读者和认为排序不都是基于比较的吗？但是，有个排序方法不用根据大小就能够排序——基数排序。

基数排序它是根据每位数的大小来比较的。首先，创建9个大小相等的队列。再根据每个数的个位数去比较大小。

例如：初始化：

根据个位数去比较大小：

从左到右依次出队。

再根据十位数的大小去入队：

最后依次出列则已经排好序。

基数排序的空间复杂度太大。因此基数排序我们只作了解即可，只不过它比较特殊不需要排序就能够排出大小。

二、直接插入排序

1.直接插入排序思路与代码

思路：直接插入排序它是从下标为1的数开始，将i下标的元素放入tmp中，若有元素比tmp中的数大，则放在j+1的位置，j再往后回退。目的是将最小的数放在最后排序时的最终位置。

例如：
初始化：令i从下标1开始，j从i-1开始。

将i下标的元素放入tmp中，比较j下标的元素。若j下标的元素比tmp大，则有arr[j+1]=arr[j]。

此时j小于0,则遍历i。i到2下标，重复相同的操作。但是若有tmp>arr[j]，直接跳出现在i下标处的循环，i到下一个位置。

最后如果退出这一趟的循环，则记得要将arr[j+1]=tmp，将tmp的值放入数组当中。

代码：

public static void insertSort(int[] array) {
        for(int i = 1;i < array.length;i++) {//n-1
            int tmp = array[i];
            int j = i-1;
            for(; j >= 0;j--) {//n-1
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

2.直接插入排序特点、时间复杂度、空间复杂度、稳定性分析

特点：当一组数据数据量不大且趋近有序，此时用直接插入排序是比较快的，并且是数组越有序越快。

时间复杂度：

• 若数组基本上是有序的，则最好时间复杂度为O(N) 。
• 若数组基本上是无序的，则最坏时间复杂度为O(N^2) 。
• 平均时间复杂度：O(N^2) 。

空间复杂度：O(1) 。

稳定性：稳定。

若要将直接插入排序的稳定性变为不稳定，则只需将array[j] > tmp改为array[j] >= tmp即可。例如一个数组由16*(星号当中标记),16,18组成，则i为16的位置，j为16 * 的位置，因为 16 * 大于等于16，则16* 移到16的位置，最后j- -，j小于0，则16移到了16*的位置。结果为：16,16 * ,18 。

3.折半插入排序（了解）

在有序区间选择数据应该插入的位置时，因为区间的有序性，可以利用折半查找的思想。

public static void bsInsertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int v = array[i];
        int left = 0;
        int right = i;
        // [left, right)
        // 需要考虑稳定性
        while (left < right) {
            int m = (left + right) / 2;
            if (v >= array[m]) {
                left = m + 1;
           } else {
                right = m;
           }
       }
        // 搬移
        for (int j = i; j > left; j--) {
            array[j] = array[j - 1];
       }
          array[left] = v;
   }
}

三、希尔排序

1.希尔排序思路与代码

希尔排序是基于直接插入排序的优化。

思想：假设10000个数据，若用直接插入排序则最坏情况下的时间复杂度为1000010000=1亿，若采用分组的思想，10000个数据分为100组，每组100个，则每组的时间复杂度为100100=10000，因为有100则，则100组的时间复杂度为10000*100=100w。远小于直接插入排序的时间复杂度。而希尔排序就是用的分组的思想。

例子：
我们先将一个数组分为5组。则跨度为5，有：

我们原理上可以是先将每组的数字排序。例如12，8，7排序后为7，8，12 。每一组都是相同的排序。

最后有：

但是我们求出来的只是每个组有序。此时我们可以将跨度改为3，即3组。有：

相同地，将每组的数据排序后，有：（虽然跨度越来越小，但是数组本身越来越有序）

最后将跨度变为1，则每一个数据为一组，等同于直接插入排序。

理论上是以上的思想。但是代码上有所不同。
如果代码上直接实现每组排序是比较困难的。我们不妨先将i到每组的中间位置，j为每组的起始位置。

初始化：

因为8比12小，有：

**此时令i++，比较的是第二组中的中间位置与起始位置的数值。**发现5比33小，5回退5个单位，小于0，则再i++。

我们发现当i++一直加到最后一组的中间元素之后，比较的是第一组的最后一个元素与中间元素。

如：（j每次要比i小gap个单位）。

需要注意的是，最后一次的跨度一定要为1，否则无法保证有序。

public static void shellSort(int[] array) {
        //处理gap
        int gap = array.length;
        while (gap > 1) {
            gap  = gap / 3 + 1;//+1是为了保证最后一个序列是1，其实除几都行
            // gap /= 2;
            shell(array,gap);
        }
    }
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

2.希尔排序特点、时间复杂度、空间复杂度、稳定性分析

特点：到目前为止，还没有人求得一种最好的增量序列（gap），数组中不同个数的数值对应最好的增量序列也不同。

时间复杂度：

• 数组趋近于有序：O(N) 。
• 数组趋近于无序：O(N^2) ，比较难构造。
• 平均时间复杂度：O(N^1.3) 。

空间复杂度：O(1) 。

稳定性：不稳定。

四、选择排序

1.选择排序思路与代码

思路：选择排序是为了将数组的最小的元素调整到数组的最前方，并且是从0下标开始调整。

public static void selectSort(int[] arr) {
        for (int i = 0; i <arr.length ; i++) {
            for (int j = i+1; j <arr.length ; j++) {
                if(arr[i]>arr[j]) {
                    int tmp = arr[i];
                    arr[i]=arr[j];
                    arr[j]=tmp;
                }
            }
        }
    }

2.选择排序特点、时间复杂度、空间复杂度、稳定性分析

选择排序特点：每一次从无序区间选出最大（或最小）的一个元素，存放在无序区
间的最后（或最前），直到全部待排序的数据元素排完 。

时间复杂度：O(N^2) 。

空间复杂度：O(1) 。

稳定性：不稳定。

五、冒泡排序

1.冒泡排序思路与代码

下面是优化的代码，设置了flg能够直接判断数组是否是有序的，若在一个排序的情况下已知整个数组是有序的，则直接退出循环，不用再继续排序了。

思路：外层遍历的是数组需要排序的趟数，而j遍历的是数组当中的每个数据是否需要排序。

需要注意的是，i和j的范围都是array.length-1，是因为调整到数组的最后时，数组的最后一个数的前面的数已经是调整过的了，并且最后一个数无需再调整。

public static void bubbleSort(int[] array) {
        // boolean flg = false;
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;//为什么每一趟都要置为false
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if(flg == false) {
                break;
            }
        }
    }

2.冒泡排序特点、时间复杂度、空间复杂度、稳定性分析

特点：冒泡排序比较直观，若前面一个数比后面一个数大，则直接交换。

时间复杂度：最好最坏都是O(n^2) ，但是：如果优化了，并且数组有序的时候就是O(n)，只要看情况。

空间复杂度：O(1) 。

稳定性：稳定。

六、堆排序

1.堆排序的思路与代码

原理：基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。

注意： 排升序要建大堆；排降序要建小堆。

下面这篇博客是作者早前详细写过有关堆排序以及它的应用的文章，有兴趣的可以点入链接，此处不再说明。
堆排序及堆的应用

2.堆排序特点、时间复杂度、空间复杂度、稳定性分析

特点：堆排序能够很快地找出堆当中前K大或前K小的数据。

时间复杂度：O(N*log2^N) 。

空间复杂度：O(1) 。

稳定性：不稳定。

七、快速排序

1.快速排序的思路与代码

原理：待排序的数据当中要找到一个基准(pivot)。

Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；找基准也是一个排序的过程。

采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度==1，代表已经有序，或者小区间的长度 = = 0，代表没有数据。

挖坑法代码思路(partition)：
以数组0下标的元素作为基准，存入tmp中。设置low指向0下标，high指向数组的最后的下标。
如果有arr[high]>=tmp，则high向左直到遇到有比tmp大的。如果high向左遍历中有比tmp小的，则arr[low]=arr[high]。
此时向右遍历low，判断是否有数据比tmp大。若有，则arr[high]=arr[low]。
当然，如果low和high相遇了就不再遍历low和high。此时将tmp的值放入arr[low]中即可，此时返回low下标就是数组的基准，它是将数组划分为左右两边，左边的数都是比它小的，右边的数都是比它大的。挖坑法首先将数组0下标的数放入tmp中，此时一定要从右边开始与tmp比较大小。

(1) 递归实现快速排序

图解：

初始化：

挖坑法后的第一趟：

此时6已经是排好序的，只要以相同的挖坑法去执行pivot左右两边的数据即可达到排序。

三数取中找基准是有arr[mid]<=arr[low]<=arr[high]是为了将基准最后按照挖坑法放到数组的中间位置，更快地递归执行pivot两边的数据。

快速排序的递归：

public static void insertSort(int[] arr,int start,int end) {
        for (int i = start+1; i <arr.length ; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (j = i-1; j >=start ; j--) {
                if(arr[j]>tmp) {
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }
    public static int partition(int[] arr,int low,int high) {
        int tmp = arr[low];
        while(low<high) {
            while(low<high&&tmp<=arr[high]) {
                high--;
            }
            arr[low]=arr[high];
            while(low<high&&tmp>=arr[low]) {
                low++;
            }
            arr[high]=arr[low];
        }
        arr[low]=tmp;
        return low;
    }
    public static void quickSort(int[] arr,int low,int high) {
        if(low>=high) {
            return;
        }
        if(high-low+1<=100) {
            insertSort(arr,low,high);
        }
        selectPivotMedianOfThree(arr,low,high);
        int pivot = partition(arr,low,high);
        quickSort(arr,0,pivot-1);
        quickSort(arr,pivot+1,high);
    }
    //快排中的三数取中找基准
    public static void selectPivotMedianOfThree(int[] arr,int low,int high) {
        //arr[mid]<=arr[low]<=arr[high]
        int mid = (low+high)/2;
        if(arr[mid]>arr[low]) {
            int tmp = arr[mid];
            arr[mid]=arr[low];
            arr[low]=tmp;
        }
        if(arr[low]>arr[high]) {
            int tmp = arr[low];
            arr[low]=arr[high];
            arr[high]=tmp;
        }
    }
    public static void quick(int[] arr) {
        quickSort(arr,0,arr.length-1);
    }
        public static void main(String[] args) {
        int[] array = {12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        quick(array);
        System.out.println(Arrays.toString(array));
    }

(2) 非递归实现快速排序

快速排序非递归要用到栈。

思路：首先找到数组的基准。并且要判断基准的两边是否足够数据来找基准。若数据个数为1或0，则无需找基准；反之可以找基准。

再将左边数据的左右边界压入栈中，再将右边数据的左右边界压入栈中。此时栈如果不为空，则出栈中的两个元素，即右边数据的左右边界，此时再去找它们的基准。若右边的找基准的左右边界不再入栈即右边完成了排序。同样地，左边找基准也是如此。

代码：

public static int partition(int[] arr,int low,int high) {
        int tmp = arr[low];
        while(low<high) {
            while(low<high&&tmp<=arr[high]) {
                high--;
            }
            arr[low]=arr[high];
            while(low<high&&tmp>=arr[low]) {
                low++;
            }
            arr[high]=arr[low];
        }
        arr[low]=tmp;
        return low;
    }
    public static void quickSort2(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int start = 0 ;
        int end= array.length-1;
        int pivot = partition(array,start, end);
        if(pivot>start+1) {
            stack.push(0);
            stack.push(pivot-1);
        }
        if(pivot<end-1) {
            stack.push(pivot+1);
            stack.push(end);
        }
        while(!stack.empty()) {
            end =stack.pop();
            start =stack.pop();
            pivot = partition(array,start,end);
            if(pivot>start+1) {
                stack.push(0);
                stack.push(pivot-1);
            }
            if(pivot<end-1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

注意：出栈的先后顺序分别是end和start 。

思路：
1.先调用partition，找到pivot。
2.把当前的pivot的左边区间和右边区间的下标放入栈中。
3.判断栈是否为空，不为空弹出两个元素，要注意先后顺序给的是谁。
4.再进行partition，若左右都排完序则栈为空。

2.快速排序特点、时间复杂度、空间复杂度、稳定性分析

特点：排序速度最快。

时间复杂度：
最好时间复杂度：O(n * log2^N) 。 基准将数组均匀地分割。如同一颗二叉树。
最坏时间复杂度：O(N^2) 。 数组完全逆序。 如同单分支的二叉树。

空间复杂度：
最好空间复杂度：O(log2^N) 。
最坏空间复杂度：O(N) 。

稳定性：不稳定。

表示最好时间复杂度。

表示最坏时间复杂度：
如：9，8，7，6

八、归并排序

1.归并排序思路与代码

原理与思路：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

从上往下的归并排序采用了递归的方式实现。它的原理非常简单，如图：

以上图为例，很像一个二叉树，将一个数组的每一个元素分为一组，这是“递”。再将一个一个合并为每两个一组、两个两个合并为四个一组等等，这是"归"。**因此此处涉及到了合并两个有序数组的问题。**观察下图，可见当low和high相等时，则子数据不需要再进一步归并排序了，此时只需要将它们合并并且排序。要注意的是需要设置一个数组tmp将数据都保存起来。

(1) 递归实现归并排序

因为看图解，归并排序的分解很像一颗二叉树的先序遍历。当low和high相等就是一个单位的数据，此时就要归并。

public static void mergeSort1(int[] array) {
        mergeSortInternal(array, 0,array.length-1);
    }
    
    public static void mergeSortInternal(int[] array,int low,int high) {
        if(low >= high) {
            return;
        }
        int mid = (low+high) / 2;
        mergeSortInternal(array,low,mid);
        mergeSortInternal(array,mid+1,high);
        //合并的过程
        merge(array,low,mid,high);
    }
    
        public static void merge(int[] array,int low,int mid,int high) {
        int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;

        int[] tmp = new int[high-low+1];
        int k = 0;//代表tmp数组的下标

        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }

        //有2种情况
        while (s1 <= e1){
            //说明第2个归并段没有了数据 把第1个归并段剩下的数据 全部拷贝过来
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            //说明第1个归并段没有了数据 把第2个归并段剩下的数据 全部拷贝过来
            tmp[k++] = array[s2++];
        }
        //tmp数组当中 存储的就是当前归并好的数据

        //这样的代码是错误的
        /*for (int i = 0; i < array.length; i++) {
            array[i] = tmp[i];
        }*/
        for (int i = 0; i < tmp.length; i++) {
            array[i+low] = tmp[i];
        }
    }

注意：
1.tmp数组的作用就是将分散的数据合并起来，因此有array[i+low] = tmp[i];**是因为数组的后半段不能覆盖掉数组前面的数据，**若array[i] = tmp[i];就会覆盖掉前面的数据。
如：后面的40 80与20 60归并在一起时，不能覆盖掉原数组前面10 30 50 70 90的值。并且此时它们的low为5，array[i] = tmp[i];能够避免。
2.递归实现的归并排序首先每一个每一个合并为一组，此时一组为两个，再每两组每两组合并，此时一组为四个，以此类推。

(2) 非递归实现归并排序

非递归来实现归并排序跟递归实现归并排序的方法类型，也要**考虑到合并两个有序的数组问题。**但不同的是，非递归是直接将一整个数组运用递归的归并排序思想的基础上在原数组当中调整。因此tmp数组的长度直接设置为原数组的长度。

注意：
要考虑到右边是否有归并段，因此有while循环的判断条件s2 < array.length。如果右边没有归并段，则直接将左边归并段的数据拷入到tmp当中，tmp数组的大小跟原数组的大小相同。如果右边有归并段，则归并完成后要调整s1,e1,s2,e2的值。

mergeSort方法内部是控制每几个每几个数据的合并。merge2方法内部是将两个数组合并并排序。

e2的位置要注意不能数组越界，如果超过数组的长度，则让它指向数组最后的元素；若不超过，则按照常规逻辑有e2=s2+gap-1。

public static void mergeSort(int[] array) {
        for (int i = 1; i < array.length; i*=2) {
            merge2(array,i);
        }
    }
    
        public static void merge2(int[] array,int gap) {
        int[] tmp = new int[array.length];
        int k = 0;

        int s1 = 0;
        int e1 = s1+gap-1;
        int s2 = e1+1;
        int e2 = s2+gap-1 < array.length ?  s2+gap-1 : array.length-1;

        //保证有两个归并段
        while (s2 < array.length) {
            while (s1 <= e1 && s2 <= e2) {
                if(array[s1] <= array[s2]) {
                    tmp[k++] = array[s1++];
                }else {
                    tmp[k++] = array[s2++];
                }
            }
            while (s1 <= e1) {
                tmp[k++] = array[s1++];
            }
            while (s2 <= e2) {
                tmp[k++] = array[s2++];
            }
            //一组完了 确定新的区间的开始和结束
            s1 = e2+1;
            e1 = s1+gap-1;
            s2 = e1+1;
            e2 = s2+gap-1 < array.length ?  s2+gap-1 : array.length-1;
        }
        //e2 > array.length
        while (s1 <= array.length-1) {
            tmp[k++] = array[s1++];
        }

        for (int i = 0; i < tmp.length; i++) {
            array[i] = tmp[i];
        }
    }

2.归并排序特点、时间复杂度、空间复杂度、稳定性分析

特点：归并排序的排序速度相对来说比较快，但仍没有快速排序快。并且它的空间复杂度较大。

时间复杂度： 最好最坏情况下：O(N * log2^N) 。

空间复杂度：O(N) 。

稳定性：稳定。

九、排序中时间复杂度、空间复杂度、稳定性的总结