一、冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。（类似于气泡上浮过程）

动图演示

代码实现

 int a[]={2,5,3,7,4,8};
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }

二、选择排序

从未排序序列中找到最小（最大），放在已排序序列尾部

动图演示

代码实现

 int a[]={2,5,3,7,4,8};
        for (int i = 0; i < a.length; i++) {
            int k=i;
            for (int j = i+1; j < a.length - i - 1; j++) {
                if (a[j] > a[k]) {
                    k=j;
                }
                int temp = a[j];
                a[j] = a[k];
                a[k] = temp;
            }
        }

三、快速排序

以一个元素为基数，将小于基数的元素移到基数前面，大于基数的元素移到基数后面，对左右区间递归以上步骤，直到区间只有一个数

动图演示

代码实现

 public static void quickSort(int[] a, int left, int right) {
            if (left >= right) {
                return;
            }

            int i = left;
            int j = right;
            int base = a[i];
            while (i < j) {
                //先进行从后往前比较,比基准值小的交换,否则一直往前找比基准值小的
                while (a[j] >= base && i < j) {
                    j--;
                }
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                //再从前往后比较，找比基准值大的交换，否则一直往后找
                while (a[i] <= base && i < j) {
                    i++;
                }
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;

            }
            //当i=j时,就以i或者j下标的元素看成分界线,这时左边比这个分界线的数小,右边比这个分界线的值大。然后再对这两个区进行递归，直到每个组只剩一个数
            quickSort(a, left, i - 1);   //分界线左边进行排序
            quickSort(a, i + 1, right);  //分界线后边进行排序
        }

注：引用quickSort时，left为0，right为a.length-1

四、插入排序

将数组中的数据从第二位开始向前找到合适的位置插入，有点类似向前的冒泡排序

动图演示

代码实现

 for (int i = 1; i < a.length; i++) {  
                for (int j = i; j > 0; j--) {
                    if (a[j]<a[j-1]){
                        int temp = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = temp;
                    } else {
                        break;
                    }
                }
            }

五、计数排序

首先设置一个包含所有范围数据的数组count，count[i]代表i这个数据出现了多少次，最后从起始位置遍历时count[i]等于几，就在数组中追加几个i。计数排序是一种特殊的桶排序，适用于量大但是范围小的数据排序，比如高考成绩排名。

动图演示

代码实现

        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        //找出最小的数min
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        //创建计数数组
        int[] count = new int[max + 1];
        //遍历a
        for (int i = 0; i < a.length; i++) {
            count[a[i]]++;
        }
        //遍历输出计数数组
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                a[k++] = i;  //a[k]=1;   k++;
                count[i]--;
            }
        }

代码优化

我们考虑一个问题，如果数组是[101,103,110,116,,119,120],如果开辟了一个121大小的数组,前100个位置都是空的,显然是不合适的,因此我们可以把数组的大小设置成max-min+1。这时，我们向数组中计数时，下标要减去一个偏移量min，输出数组的时候，要加上这个偏移量。

int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        //找出最小的数min
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < min) {
                min = a[i];
            }
        }
        //创建计数数组
        int[] count = new int[max - min + 1];
        //遍历a
        for (int i = 0; i < a.length; i++) {
            count[a[i] - min]++;
        }
        //遍历输出计数数组
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                a[k++] =i + min;  //a[k]=1;   k++;
                count[i]--;
            }
        }

六、希尔排序

希尔排序可以理解成插入排序的优化版本。

希尔排序是先将任意间隔为N的元素有序，刚开始可以是N=n/2，接着让N=N/2，让N一直缩小，当N=1,时，此时序列间隔为1有序。

动图演示

代码实现

 //希尔排序
        for (int gap = a.length / 2; gap > 0; gap /= 2) {
            //插入排序将1换成gap
            for (int i = gap; i < a.length; i++) {
                for (int j = i; j - gap>=0; j -= gap) {
                    if (a[j] < a[j - gap]) {
                        int temp = a[j];
                        a[j] = a[j - gap];
                        a[j - gap] = temp;
                    } else {
                        break;
                    }
                }
            }
        }

七、归并排序

归并排序的采用分治思想，如果要排序一个数组，我们先把数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。核心是merge()合并函数。

动图演示

代码实现1（递归）：

public class MergeSort {
    // 归并排序(递归）
    public static int[] mergeSort(int[] arr, int left, int right) {
        // 如果 left == right，表示数组只有一个元素，则不用递归排序
        if (left < right) {
            // 把大的数组分隔成两个数组
            int mid = (left + right) / 2;
            // 对左半部分进行排序
            arr = mergeSort(arr, left, mid);
            // 对右半部分进行排序
            arr = mergeSort(arr, mid + 1, right);
            //进行合并
            merge(arr, left, mid, right);
        }
        return arr;
    }

    // 合并函数merge，把两个有序的数组合并起来
    // arr[left..mif]表示一个数组，arr[mid+1 .. right]表示一个数组
    private static void merge(int[] arr, int left, int mid, int right) {
        //先用一个临时数组把他们合并汇总起来
        int[] a = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                a[k++] = arr[i++];
                //(即a[k]=a[i]; k=k+1; i=i+1;
            } else {
                a[k++] = arr[j++];
            }
        }
        while(i <= mid) a[k++] = arr[i++];
        while(j <= right) a[k++] = arr[j++];
        // 把临时数组复制到原数组
        for (i = 0; i < k; i++) {
            arr[left++] = a[i];
        }
    }
}

代码实现2（非递归）：

public class MergeSort {
    // 归并排序（非递归）
    public static int[] mergeSort(int[] arr) {
        int n = arr.length;
        // 子数组的大小分别为1，2，4，8...
        // 刚开始合并的数组大小是1，接着是2，接着4....
        for (int i = 1; i < n; i += i) {
            //进行数组进行划分
            int left = 0;
            int mid = left + i - 1;
            int right = mid + i;
            //进行合并，对数组大小为 i 的数组进行两两合并
            while (right < n) {
                // 合并函数和递归式的合并函数一样
                merge(arr, left, mid, right);
                left = right + 1;
                mid = left + i - 1;
                right = mid + i;
            }
            // 还有一些被遗漏的数组没合并，千万别忘了
            // 因为不可能每个字数组的大小都刚好为 i
            if (left < n && mid < n) {
                merge(arr, left, mid, n - 1);
            }
        }
        return arr;
    }
}

八、桶排序

桶排序是将数组分别放到有限数量的桶里。每个桶再进行排序。

桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。

那么，桶排序当中所谓的“桶”，又是什么概念呢？

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。桶排序的第一步，就是创建这些桶，确定每一个桶的区间范围：

具体建立多少个桶，如何确定桶的区间范围，有很多不同的方式。

我们这里创建的桶数量等于原始数列的元素数量，除了最后一个桶只包含数列最大值，前面各个桶的区间范围按照比例确定。

区间跨度（大小） = （最大值-最小值）/ （桶的数量 - 1）

注：除了最后一个桶之外，其余的桶均分最大值和最小值的差值，区间跨度（大小）也就是桶的范围的大小。

代码中，所有的桶保存在ArrayList集合当中，每一个桶被定义成一个链表（LinkedList<Double>），这样便于在尾部插入元素。

定位元素属于第几个桶，是按照比例来定位：

(array[i] - min) * (bucketNum-1) / d

注：要定位元素 array[i] 在第几个桶，先减去最小值min,看它在桶数组（ArrayList）中的偏移为多少，然后除以桶的区间大小d/(buketNum-1),相当于乘以(buketNum-1)/d，除以桶区间大小就可以定位是在哪个桶里了。

同时，代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort，小伙伴们可以简单地把它们当做是一种时间复杂度 O（nlogn）的排序。

动图演示

代码实现

public static int[] BucketSort(int[] arr) {
            if(arr == null || arr.length < 2) return arr;

            int n = arr.length;
            int max = arr[0];
            int min = arr[0];
            // 寻找数组的最大值与最小值
            for (int i = 1; i < n; i++) {
                if(min > arr[i])
                    min = arr[i];
                if(max < arr[i])
                    max = arr[i];
            }
            //和优化版本的计数排序一样，弄一个大小为 min 的偏移值
            int d = max - min;

            //初始化桶
            int bucketNum = arr.length;
            ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
            for (int i = 0; i < bucketNum; i++) {
                bucketList.add(new LinkedList<Integer>());
            }
            //遍历原数组，将每个元素放入桶中
            for (int i = 0; i < n; i++) {
                int num = (int)((arr[i] - min)  * (bucketNum - 1) / d);
                bucketList.get(num).add(arr[i]);
            }
            //对桶内的元素进行排序，我这里采用系统自带的排序工具
            for (int i = 0; i < bucketNum; i++) {
                Collections.sort(bucketList.get(i));
            }
            //把每个桶排序好的数据进行合并汇总放回原数组
            int k = 0;
            for (int i = 0; i < bucketNum; i++) {
                for (Integer t : bucketList.get(i)) {
                    arr[k++] = t + min;
                }
            }
            return arr;
        }

ArrayList：https://www.runoob.com/java/java-arraylist.html

LinkedList：https://www.runoob.com/java/java-linkedlist.html

九、堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。

堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换…如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

堆（Heap）

父节点及子节点下标的关系

动图演示：

思路：

1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端

2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1

3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

注意:升序用大根堆，降序就用小根堆(默认为升序)

代码实现

public class Dui {
    public static void main(String[] args) {
        int a[]={3，1，2，5，4};
        sort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }

    }
    //堆排序的方法
    private static void sort(int[] arr){
        //建堆
        for(int i = arr.length/2 - 1; i >= 0; i--){
            adjustHeap(arr,i,arr.length);
        }
        //排序
        for(int j = arr.length - 1; j > 0; j--){
            //堆顶和最后一个元素交换
            swap(arr,0,j);
            //交换后重新建队
            adjustHeap(arr,0,j);
        }
    }
    //建堆的方法
    //实际上就是对于每一个节点，比较其与其子节点中最大的那个数，并将最大的那个数交换到节点位置
    private static void adjustHeap(int[] arr,int i,int length){
        int temp = arr[i];
        for(int k = i*2+1; k < length; k = k*2+1){
            if( k+1 < length && arr[k] < arr[k+1] ){//有右孩子且右孩子大于左孩子
                k++;
            }
            if( arr[k] > temp ){//如果子大于父，则父与子节点交换
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;
    }
    //交换两个数的方法
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

详细内容也可参照此博客：https://blog.csdn.net/weixin_51609435/article/details/122982075（作者Oorik）

也可参照bilibiliup主（请叫我AXin）的视频https://www.bilibili.com/video/BV1fp4y1D7cj/?spm_id_from=333.337.search-card.all.click

十、基数排序

基数排序是一种特殊的桶排序

思路：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小…

排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。

由于某位数（个位/十位…，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了

动图演示

代码实现

public class RadioSort {

    public static int[] radioSort(int[] arr) {
        if(arr == null || arr.length < 2) return arr;

        int n = arr.length;
        int max = arr[0];
        // 找出最大值
        for (int i = 1; i < n; i++) {
            if(max < arr[i]) max = arr[i];
        }
        // 计算最大值是几位数
        int num = 1;
        while (max / 10 > 0) {
            num++;
            max = max / 10;
        }
        // 创建10个桶
        ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
        //初始化桶
        for (int i = 0; i < 10; i++) {
            bucketList.add(new LinkedList<Integer>());
        }
        // 进行每一趟的排序，从个位数开始排
        for (int i = 1; i <= num; i++) {
            for (int j = 0; j < n; j++) {
                // 获取每个数最后第 i 位是数组
                int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
                //放进对应的桶里
                bucketList.get(radio).add(arr[j]);
            }
            //合并放回原数组
            int k = 0;
            for (int j = 0; j < 10; j++) {
                for (Integer t : bucketList.get(j)) {
                    arr[k++] = t;
                }
                //取出来合并了之后把桶清光数据
                bucketList.get(j).clear();
            }
        }
        return arr;
    }
}