一、冒泡排序

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
过程：
　①、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
　②、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。
　③、针对所有的元素重复以上的步骤，除了最后一个。
　④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序

平均时间复杂度：O(n²)
代码实现：

public class BubbleSort {
    public static int[] sort(int[] array){
        int temp;//临时变量
        boolean flag;//是否交换的标识

        //这里for循环表示总共需要比较多少轮
        for(int i=1;i<array.length;i++){
            flag = false;
            //j的范围很关键，这个范围是在逐步缩小的,因为每轮比较都会将最大的放在右边
            for(int j=0;j<array.length-i;j++){
                if(array[j]>array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = true;
                }
            }
            //如果flag为false，表示此次循环没有数据交换，退出循环
            if(!flag){
                break;
            }
        }
        return array;
    }
}

二、选择排序

基本思想：选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
过程：
　①、从待排序序列中，找到关键字最小的元素
　②、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
　③、从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束

选择排序

平均时间复杂度：O(n²)
代码实现：

public class ChoiceSort {
    public static int[] sort(int[] array){
        //总共要经过N-1轮比较
        for(int i=0;i<array.length-1;i++){
            int minIndex = i;
            //每轮要比较的次数
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;//记录目前能找到的最小值元素的下标
                }
            }

            //将找到的最小值和i位置所在的值进行位置交换
            if(minIndex != i){
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }
        return array;
    }
}

三、插入排序

基本思想：直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
过程：

插入排序

平均时间复杂度：O(n²)
代码实现：

public class InsertSort {
    public static int[] sort(int[] array){
        int j;
        //从下标为1的元素开始开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for(int i=1;i<array.length;i++){
            int temp =array[i];//记录要插入的数据
            j = i;
            while (j>0 && temp<array[j-1]){
                array[j] = array[j-1];//向后挪动
                j--;
            }
            array[j] = temp;//插入此数
        }
        return array;
    }
}

四、希尔排序

基本思想：在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
过程：

希尔排序

//希尔排序 间隔为2h
public class ShellSort {
    public static int[] sort(int[] array){
        int step;
        int length  = array.length;
        for(step = length/2;step>0;step=step/2){
            //分别对每个增量间隔进行排序
            for (int i=step;i<array.length;i++){
                int j=i;
                int temp = array[j];
                while (j-step>=0 && temp<array[j-step]){
                    array[j] = array[j-step];
                    j -= step;
                }
                array[j] = temp;
            }
        }
        return array;
    }
}

五、快速排序

基本思想：（分治）
　①、先从数列中取出一个数作为key值；
　②、将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
　③、对左右两个小数列重复第二步，直至各区间只有1个数。
过程：

上面表示的是一个无序数组，选取第一个元素 6 作为基准元素。左游标是 i 哨兵，右游标是 j 哨兵。然后左游标向左移动，右游标向右移动，它们遵循的规则如下：
一、左游标向右扫描， 跨过所有小于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素， 在那个位置停下。
二、右游标向左扫描， 跨过所有大于基准元素的数组元素, 直到遇到一个小于或等于基准元素的数组元素，在那个位置停下。

第一步：哨兵 j 先开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 j 先开始出动，哨兵 j 一步一步的向左挪动，直到找到一个小于 6 的元素停下来。接下来，哨兵 i 再一步一步的向右挪动，直到找到一个大于 6 的元素停下来。最后哨兵 i 停在了数字 7 面前，哨兵 j 停在了数字 5 面前。

左边序列为【3,1,2,5,4】,右边序列为【9,7,10,8】。接着对于左边序列而言，以数字 3 为基准元素，重复上面的探测操作，探测完毕之后的序列为【2,1,3,5,4】；对于右边序列而言，以数字 9 位基准元素，也重复上面的探测操作。然后一步一步的划分，最后排序完全结束。

平均时间复杂度：O(N*logN)
代码实现：

public class QuickSort {
    public static void sort(int[] array,int left,int right){
        //区间只有1个数，就退出
        if(left>=right){
            return;
        }

        int i = left,j = right,key = array[left];//key是基准数
        while (i<j){
            //顺序很重要，要先从右边开始找
            while (i<j && array[j]>=key){
                j--;
            }
            while (i<j && array[i]<=key){
                i++;
            }

            if(i<j){//交换两个数在数组中的位置
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //最终将基准数归位
        array[left] = array[i];
        array[i] = key;

        sort(array,left,i-1);//递归调用
        sort(array,i+1,right);
    }

    public static void main(String[] args) {
        int[] array = {2,3,1,3,1,2,3,4,5,1,2,-4,99};
        sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

六、归并排序

基本思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B，就生成了第三个有序数组C。数组C包含数组A和B的所有数据项。
过程：比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
平均时间复杂度：O(N*logN)
代码实现：

public class MergeSort {
    public static int[] sort(int[] array,int start,int last){
        if(last > start){
            int mid = (start+last)/2;
            sort(array,start,mid);//左边数组排序
            sort(array,mid+1,last);//右边数组排序
            merge(array,start,mid,last);//合并左右数组
        }
        return array;
    }

    public static void merge(int[] array,int start,int mid,int last){
        int[] temp = new int[last-start+1];//定义临时数组
        int i = start;//定义左边数组的下标
        int j = mid + 1;//定义右边数组的下标
        int k = 0;
        while(i <= mid && j <= last){
            if(array[i] < array[j]){
                temp[k++] = array[i++];
            }else{
                temp[k++] = array[j++];
            }
        }
        //把左边剩余数组元素移入新数组中
        while(i <= mid){
            temp[k++] = array[i++];
        }
        //把右边剩余数组元素移入到新数组中
        while(j <= last){
            temp[k++] = array[j++];
        }

        //把新数组中的数覆盖到array数组中
        for(int m = 0 ; m < temp.length ; m++){
            array[m+start] = temp[m];
        }
    }

    public static void main(String[] args) {
        int[] array = {2,3,1,3,1,2,3,4,5,1,2,-4,99};
        sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

七、堆排序

基本思想： 堆排序是指利用堆这种数据结构所设计的一种排序算法。
过程：
　①将待排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素。
　②将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆。
　③重复步骤②，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

假设给定的无序序列arr是：
4 5 8 2 3 9 7 1
1、将无序序列构建成一个大顶堆。
首先我们将现在的无序序列看成一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。

根据大顶堆的性质，每个节点的值都大于或者等于它的左右子节点的值。所以我们需要找到所有包含子节点的节点，也就是非叶子节点，然后调整他们的父子关系，非叶子节点遍历的顺序应该是从下往上，这比从上往下的顺序遍历次数少很多，因为，大顶堆的性质要求父节点的值要大于或者等于子节点的值，如果从上往下遍历，当某个节点即是父节点又是子节点并且它的子节点仍然有子节点的时候，因为子节点还没有遍历到，所以子节点不符合大顶堆性质，当子节点调整后，必然会影响其父节点需要二次调整。但是从下往上的方式不需要考虑父节点，因为当前节点调整完之后，当前节点必然比它的所有子节点都大，所以，只会影响到子节点二次调整。相比之下，从下往上的遍历方式比从上往下的方式少了父节点的二次调整。

那么，该如何知道最后一个非叶子节点的位置，也就是索引值？

对于一个完全二叉树，在填满的情况下（非叶子节点都有两个子节点），每一层的元素个数是上一层的二倍，根节点数量是1，所以最后一层的节点数量，一定是之前所有层节点总数+1，所以，我们能找到最后一层的第一个节点的索引，即节点总数/2（根节点索引为0），这也就是第一个叶子节点，所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢？这个计算方式仍然适用，当我们从上往下，从左往右填充二叉树的过程中，第一个叶子节点，一定是序列长度/2，所以第一个非叶子节点的索引就是arr.length / 2 -1。

现在找到了最后一个非叶子节点，即元素值为2的节点，比较它的左右节点的值，是否比他大，如果大就换位置。这里因为1<2，所以，不需要任何操作，继续比较下一个，即元素值为8的节点，它的左节点值为9比它本身大，所以需要交换

交换后的序列为：
4 5 9 2 3 8 7 1
因为元素8没有子节点，所以继续比较下一个非叶子节点，元素值为5的节点，它的两个子节点值都比本身小，不需要调整；然后是元素值为4的节点，也就是根节点，因为9>4，所以需要调整位置

交换后的序列为：
9 5 4 2 3 8 7 1
此时，原来元素值为9的节点值变成4了，而且它本身有两个子节点，所以，这时需要再次调整该节点

交换后的序列为：
9 5 8 2 3 4 7 1
到此，大顶堆就构建完毕了。满足大顶堆的性质。

2、排序序列，将堆顶的元素值和尾部的元素交换

交换后的序列为：
1 5 8 2 3 4 7 9
然后将剩余的元素重新构建大顶堆，其实就是调整根节点以及其调整后影响的子节点，因为其他节点之前已经满足大顶堆性质。

交换后的序列为：
8 5 7 2 3 4 1 9
然后，继续交换，堆顶节点元素值为8与当前尾部节点元素值为1的进行交换
一直重复此步骤

参考链接：https://blog.csdn.net/qq_28063811/article/details/93034625
平均时间复杂度：O(N*logN)
代码实现：

public class HeapSort {

    private void heapSort(int[] arr){
        //1、构建大根堆 从第一个非叶子节点开始
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }

        //2、交换第一个节点和最后一个节点值，继续下沉调整
        for(int i=arr.length-1;i>0;i--){
            swap(arr,0,i);
            adjustHeap(arr,0,i);
        }

    }

    private void adjustHeap(int[] arr,int index,int length){
        int maxIndex = index;//记录最大值下标
        int leftIndex = 2*index+1;//左子节点下标
        int rightIndex = 2*index+2;//右子节点下标
        //1、如果存在左子节点并且比父节点值大
        if(leftIndex<length && arr[maxIndex]<arr[leftIndex]){
            maxIndex = leftIndex;
        }
        //2、如果存在右子节点并且比父节点值大
        if(rightIndex<length && arr[maxIndex]<arr[rightIndex]){
            maxIndex = rightIndex;
        }
        //3、如果交换了值，那么继续向下比较
        if(maxIndex != index){
            swap(arr,index,maxIndex);
            adjustHeap(arr,maxIndex,length);
        }
    }

    private void swap(int[] arr,int i,int j){
        int value = arr[i];
        arr[i] = arr[j];
        arr[j] = value;
    }
}

八、桶排序

桶排序需要两个辅助空间：

• 第一个辅助空间，是桶空间B
• 第二个辅助空间，是桶内的元素链表空间

总的来说，空间复杂度是O(n)。

桶排序有两个关键步骤：

• 扫描待排序数据arr[N]，对于元素arr[i]，放入对应的桶X
• arr[i]放入桶X，如果桶X已经有了若干元素，使用插入排序，将arr[i]放到桶内合适的位置

画外音：
（1）桶X内的所有元素，是一直有序的；
（2）插入排序是稳定的，因此桶内元素顺序也是稳定的；

当arr[N]中的所有元素，都按照上述步骤放入对应的桶后，就完成了全量的排序。

桶排序的伪代码是：
bucketSort(arr[N]){
　for i =1 to n{
　　将arr[i]放入对应的桶B[X];
　　使用插入排序，将arr[i]插入到B[X]中正确的位置;
　}
　将B[X]中的所有元素，按顺序合并，排序完毕;
}

举个例子：
假设待排序的数组均匀分布在[0, 99]之间：
{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}
可以设定10个桶，申请额外的空间bucket[10]来作为辅助空间。其中，每个桶bucket[i]来存放[10i, 10i+9]的元素链表。

上图所示：

• 待排序的数组为arr[16]
• 桶空间是buket[10]
• 扫描所有元素之后，元素被放到了自己对应的桶里
• 每个桶内，使用插入排序，保证一直是有序的

例如，标红的元素66, 67, 62最终会在一个桶里，并且使用插入排序桶内保持有序。

最终，每个桶按照次序输出，排序完毕。

桶排序(Bucket Sort)，总结：

• 桶排序，是一种复杂度为O(n)的排序
• 桶排序，是一种稳定的排序
• 桶排序，适用于数据均匀分布在一个区间内的场景

参考链接：来自微信公众号58沈剑 架构师之路

九、基数排序

举个例子：
假设待排序的数组arr={72, 11, 82, 32, 44, 13, 17, 95, 54, 28, 79, 56}

基数排序的两个关键要点：
（1）基：被排序的元素的“个位”“十位”“百位”，暂且叫“基”，栗子中“基”的个数是2（个位和十位）；
（2）桶：“基”的每一位，都有一个取值范围，栗子中“基”的取值范围是0-9共10种，所以需要10个桶（bucket），来存放被排序的元素；

基数排序的算法步骤为：
for (每一个基) {
　//循环内，以某一个“基”为依据
　第一步：遍历数据集arr，将元素放入对应的桶bucket
　第二步：遍历桶bucket，将元素放回数据集arr
}

更具体的，对应到上面的例子，“基”有个位和十位，所以，for循环会执行两次。

【第一次：以“个位”为依据】

画外音：上图中标红的部分，个位为“基”。

第一步：遍历数据集arr，将元素放入对应的桶bucket；

操作完成之后，各个桶会变成上面这个样子，即：个位数相同的元素，会在同一个桶里。

第二步：遍历桶bucket，将元素放回数据集arr；
画外音：需要注意，先入桶的元素要先出桶。

操作完成之后，数据集会变成上面这个样子，即：整体按照个位数排序了。
画外音：个位数小的在前面，个位数大的在后面。

【第二次：以“十位”为依据】

画外音：上图中标红的部分，十位为“基”。

第一步：依然遍历数据集arr，将元素放入对应的桶bucket；

操作完成之后，各个桶会变成上面这个样子，即：十位数相同的元素，会在同一个桶里。

第二步：依然遍历桶bucket，将元素放回数据集arr；

操作完成之后，数据集会变成上面这个样子，即：整体按照十位数也排序了。
画外音：十位数小的在前面，十位数大的在后面。

首次按照个位从小到大，第二次按照十位从小到大，即：排序结束。

几个小点：
（1）基的选取，可以先从个位开始，也可以先从十位开始，结果是一样的；
（2）基数排序，是一种稳定的排序；
（3）时间复杂度，可以认为是线性的O(n)；

十、计数排序

计数排序的适用范围？
待排序的元素在某一个范围[MIN, MAX]之间。
画外音：很多业务场景是符合这一场景，例如uint32的数字排序位于[0, 2^32]之间。

计数排序的空间复杂度？
计数排序需要一个辅助空间，空间大小为O(MAX-MIN)，用来存储所有元素出现次数（“计数”）。
画外音：计数排序的核心是，空间换时间。

计数排序的关键步骤？
步骤一：扫描待排序数据arr[N]，使用计数数组counting[MAX-MIN]，对每一个arr[N]中出现的元素进行计数；
步骤二：扫描计数数组counting[]，还原arr[N]，排序结束；

举个例子：
假设待排序的数组，
arr={5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6}
很容易发现，待排序的元素在[0, 10]之间，可以用counting[0,10]来存储计数。

第一步：统计计数

扫描未排序的数组arr[N]，对每一个出现的元素进行计数。

扫描完毕后，计数数组counting[0, 10]会变成上图中的样子，如粉色示意，6这个元素在arr[N]中出现了4次，在counting[0, 10]中，下标为6的位置计数是4。

第二步：还原数组

扫描计数数组counting[0, 10]，通过每个元素的计数，还原arr[N]。

如上图粉色示意，count[0, 10]下标为6的位置计数是4，排完序是4个连续的6。
从counting下标MIN到MAX，逐个还原，填满arr[N]时，排序结束。

计数排序(Counting Sort)，总结：

• 计数排序，时间复杂度为O(n)；
• 当待排序元素个数很多，但值域范围很窄时，计数排序是很节省空间的；

稳定：冒泡排序、插入排序、归并排序、桶排序、基数排序、计数排序
不稳定：选择排序、快速排序、希尔排序、堆排序