Java实现常用的排序算法（快速排序、归并排序、基数排序）

超、凢脫俗 2024-04-07 15:21 44阅读 0赞

#### 排序算法 ####

*  常见的排序算法
 *  快速排序
 *   *  1.简介
     *  2.思路分析
     *  3.图解
     *   *  3.1 开始
         *  3.2 从右向左遇到小于基准的数
         *  3.3 右边停止，从左向右寻找大于基准的数
         *  3.4 交换L和R相对应的数
         *  3.5持续上述方法
         *  3.6 处理左边的数
         *  3.7处理右边的数
     *  4.代码实现
 *  归并排序
 *   *  1.简介
     *  2.思路分析
     *  3.图解
     *   *  3.1 拆分，将所有的序列分解
         *  3.2开始排序合并
     *  4.代码实现
 *  基数排序
 *   *  1.简介
     *  2.思路分析
     *  3.图解
     *   *  3.1第一轮按个位放入桶中
         *  3.2 第二轮按十位放入桶中
         *  3.3第三轮按百位上放入桶中
         *  3.34第四轮按千位放入桶中
     *  4.代码实现

## 常见的排序算法 ##

![在这里插入图片描述][ac8d8fa777be4624905baeccc5801bc5.png]

## 快速排序 ##

### 1.简介 ###

> 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

### 2.思路分析 ###

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：  
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。  
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。  
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。  
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

### 3.图解 ###

#### 3.1 开始 ####

分别从arr数组的两端开始探测。先从右往左找一个小于8的数，再从左往右找一个大于8的数，然后交换他们。这里可以用两个变量L（左边）和R（右边），分别指向序列最左边和最右边。刚开始的时候让L指向数组的最左边，指向数字8。让R指向数组的最右边，指向数字11。  
![在这里插入图片描述][e4d071080627466f83dafb1d52f3af78.png]

#### 3.2 从右向左遇到小于基准的数 ####

![在这里插入图片描述][8bb6d8aca8284593bddb01ede7163527.png]

#### 3.3 右边停止，从左向右寻找大于基准的数 ####

![在这里插入图片描述][cf22bd10fb354144a2c87ffec5fe73aa.png]

#### 3.4 交换L和R相对应的数 ####

![在这里插入图片描述][76b37158227b4480b905899feb5bb909.png]

交换后  
![在这里插入图片描述][ab52837ea6cb4a6ebbd3c4451a9154a4.png]

#### 3.5持续上述方法 ####

首先R开始出动。因为此处设置的基准数是最左边的数，所以需要让R先出动，这一点非常重要（请自己想一想为什么）。哨兵R一步一步地向左挪动（即R–-），直到找到一个小于8的数停下来。接下来哨兵L再一步一步向右挪动（即L++），直到找到一个数大于8的数停下来。

交换  
![在这里插入图片描述][4f2ae3b317e84c0ab7a4249f68a018ea.png]

交换后

![在这里插入图片描述][dffaa5dac05f49c4818fb8fcbd05e2b0.png]

这个时候R继续向左移动  
![在这里插入图片描述][b22c1700cce74857ba16a5cf5e1bebeb.png]

然后L移动  
![在这里插入图片描述][5b662c29cfc14de0a7a6fcfc4d552d75.png]

L == R 时候，说明这个位置就是8的位置，交换  
![在这里插入图片描述][253ba667ca464bd78651ddb12260d495.png]

得到：

![在这里插入图片描述][bb40a886195e4664969784dad3694440.png]  
到此第一轮探测结束。此时以基准数8为分界点，8左边的数都小于等于8，8右边的数都大于等于8。回顾一下刚才的过程，其实R的使命就是要找小于基准数的数，而L的使命就是要找大于基准数的数，直到L和R碰头为止。

#### 3.6 处理左边的数 ####

![在这里插入图片描述][3be144a1755043399cf5ea5e4110e5d0.png]

#### 3.7处理右边的数 ####

![在这里插入图片描述][64f215cfef06459f924834666457c5e6.png]

得到：  
![在这里插入图片描述][1ef404f31787417397f2a9f6922a9bf7.png]

### 4.代码实现 ###

/**
     * 快速排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/10
     */
    public class QuickSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        8, 12, 19, -1, 45, 0, 14, 4, 11};
            quickSort(arr,0,arr.length-1);
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
        }
        public static void quickSort(int[] arr,int start, int end){
        
            // 什么时候结束排序？
            if (start>end){
        
                return;
            }
            // 左指针
            int L = start;
            // 右指针
            int R = end;
            // 基准
            int pivot = arr[start];
            // 只要L！=R就继续循环
            while (L < R){
        
                // 右边大于基准，从右向左移动
                while (L<R && arr[R] >= pivot){
        
                    R --;
                }
                // 左边小于基准，从左向右移动
                while (L<R&& arr[L] <= pivot){
        
                    L ++;
                }
                // 说明右边有小于基准的数，左边有大于基准的数，交换
                if (L<R){
        
                    int temp = arr[L];
                    arr[L] = arr[R];
                    arr[R] = temp;
                }
            }
            // L 与 R碰面 找到了 基准的位置
            arr[start] = arr[L];
            arr[L] = pivot;
    
            // 左边排序
            quickSort(arr,start,R-1);
            // 右边排序
            quickSort(arr,L+1,end);
    
        }
    
    }

> 快速排序这篇文章写的好，可以参考[别人的快速排序写法和理解][Link 1]

--------------------

## 归并排序 ##

### 1.简介 ###

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

### 2.思路分析 ###

归并排序用到了分而治之的思想，其难点是治

*  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 *  首先是分解序列，将序列分解到每个组中序列的数量为1，然后在进行合并排序
 *  设定两个指针，最初位置分别为两个已经排序序列的起始位置
 *  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 *  重复上一步 直到某一指针达到序列尾
 *  将另一序列剩下的所有元素直接复制到合并序列尾

### 3.图解 ###

#### 3.1 拆分，将所有的序列分解 ####

![在这里插入图片描述][5fe4954a395b4cf4aabe669a39f9b8f0.png]

#### 3.2开始排序合并 ####

![在这里插入图片描述][f1b93741173e4ee1afad6533bf911392.png]

每次填充完后，指针移动一位  
![在这里插入图片描述][3435100309af48669263a885bc849c0a.png]

![在这里插入图片描述][fb65dca0d5d64345b2b35e38aa091a88.png]

当左边数组没有元素后，右边直接填充进去  
![在这里插入图片描述][d3cc5cd393b54d369817c082e072cd4d.png]

得到  
![在这里插入图片描述][c2c22f5584594c0794e623accc81da26.png]

### 4.代码实现 ###

/**
     * 归并排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/12
     */
    public class MergeSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        1, 5, 6, 3, 2, 8, 7, 4};
            int[] temp = new int[arr.length];
            mergeSort(arr,0,arr.length-1,temp);
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
        }
    
        /** 分解,并合并排序 */
        public static void mergeSort(int[] arr,int left ,int right,int[] temp){
        
            if (left<right){
        
                //中间索引
                int mid = (left+right)/2;
                //向左递归分解
                mergeSort(arr,left,mid,temp);
                //向右递归分解
                mergeSort(arr,mid+1,right,temp);
                //合并
                merge(arr,left,mid,right,temp);
            }
        }
    
        /**
         * 合并排序
         * @param arr   未排序的数组
         * @param left  左边有序子数组的初始索引
         * @param mid   中间索引
         * @param right 右边最大索引
         * @param temp  临时数组
         */
        public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        
            // 左边指针索引
            int leftPoint = left;
            // 右边指针索引
            int rightPoint = mid+1;
            // 临时数据的指针
            int tempLeft = 0;
    
            // 两个序列都不为空时
            while (leftPoint <= mid && rightPoint <= right){
        
                //如果第一个序列的元素小于第二序列的元素，就将其放入temp中
                if (arr[leftPoint] <= arr[rightPoint]){
        
                    temp[tempLeft] = arr[leftPoint];
                    leftPoint++;
                    tempLeft ++;
                }else{
        
                    temp[tempLeft] = arr[rightPoint];
                    rightPoint++;
                    tempLeft ++;
                }
            }
    
            // 右序列为空，直接将做序列的所有元素填充进去
            while (leftPoint <= mid){
        
                temp[tempLeft] = arr[leftPoint];
                leftPoint++;
                tempLeft++;
            }
    
            // 左序列为空，直接将右序列的所有元素填充进去
            while (rightPoint <= right){
        
                temp[tempLeft] = arr[rightPoint];
                rightPoint++;
                tempLeft++;
            }
    
            //将临时数组中的元素放回数组arr中
            tempLeft = 0;
            leftPoint = left;
            while (leftPoint <= right){
        
                arr[leftPoint] = temp[tempLeft];
                leftPoint++;
                tempLeft++;
            }
    
    
        }
    }

--------------------

## 基数排序 ##

### 1.简介 ###

> 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

### 2.思路分析 ###

*  将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
 *  从最低位开始，依次进行一次排序
 *  从最低位排序一直到最高位（个位->十位->百位->…->最高位）排序完成以后, 数列就变成一个有序序列
 *  需要我们获得最大数的位数
    
     *  可以通过将最大数变为String类型，再求得它的长度即可

### 3.图解 ###

首先要有10个桶代表\[0-9\]

#### 3.1第一轮按个位放入桶中 ####

![在这里插入图片描述][12d30ab2b0d7493e89f8990588efe8a3.png]  
然后再依次将他们取出，如果一个桶里面有多个元素，先进去的那么先取出来  
![在这里插入图片描述][318bdf0560d84b04b990f45a076369f1.png]

#### 3.2 第二轮按十位放入桶中 ####

![在这里插入图片描述][b0c125abb2944e68adcfee9782e70c22.png]  
如果没有十位数，那么就在个位的前面补0

![在这里插入图片描述][0d379fde83164666bd6f66abdc95ec74.png]

#### 3.3第三轮按百位上放入桶中 ####

![在这里插入图片描述][46ccbb63560e44818dd4491205ab1111.png]

依次取出后  
![在这里插入图片描述][2f0163db5ee74b40978a4445eb60832a.png]

#### 3.34第四轮按千位放入桶中 ####

![在这里插入图片描述][f7667ca5a0674e448032a2fff0f1d403.png]

取出得到：

![在这里插入图片描述][4d30c4a5276449798f2a759d71949956.png]

### 4.代码实现 ###

/**
     * 基数排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/13
     */
    public class BaseSorted {
        
        public static void main(String[] args) {
        
            int[] arr = {
        43, 52, 1, 89, 190};
            sort(arr);
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
        }
    
        public static void sort(int[] arr){
        
            int maxLength = getMaxLength(arr);
            // 定义个二维数组桶，存储元素
            int[][] bucket = new int[10][arr.length];
            // 存储每个桶中有多少个元素
            int[] elementCounts = new int[10];
            for (int times = 1,step = 1; times < maxLength + 1; times++,step *= 10) {
        
                // 遍历数组，将元素存入桶中
                for (int i = 0; i < arr.length; i++) {
        
                    // 获取位数上的数
                    int digits = arr[i] / step % 10;
                    bucket[digits][elementCounts[digits]] = arr[i];
                    elementCounts[digits] ++;
                }
    
                //将桶中的元素重新放回到数组中
                //用于记录应该放入原数组的哪个位置
                int index = 0;
                for (int i = 0; i < 10; i++) {
        
                    // 从桶中按放入顺序依次取出元素，放入原数组
                    int position = 0;
                    while ( elementCounts[i] > 0){
        
                        arr[index] = bucket[i][position];
                        position++;
                        elementCounts[i]--;
                        index++;
                    }
                }
    
    
    
            }
    
        }
    
        /** 获取数组中元素长度最长的长度 */
        public static int getMaxLength(int[] arr){
        
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) {
        
                if (arr[i] > max ){
        
                    max = arr[i];
                }
            }
            return (max + "").length();
        }
    }

[ac8d8fa777be4624905baeccc5801bc5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f3da3f3f31ee4215a8e84a141691c020.png
[e4d071080627466f83dafb1d52f3af78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/5ab211956d2f4287b6f31394ef42b586.png
[8bb6d8aca8284593bddb01ede7163527.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/bc109df761cd452fa21d86cdc206dc64.png
[cf22bd10fb354144a2c87ffec5fe73aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/26163fe762874b2cad8144e21b5ecd89.png
[76b37158227b4480b905899feb5bb909.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2148c99022a04fda88ef62e49288b905.png
[ab52837ea6cb4a6ebbd3c4451a9154a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6e5a51449f6544989894481292a41e66.png
[4f2ae3b317e84c0ab7a4249f68a018ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2d07b3c8de6f485389350676546d8dd2.png
[dffaa5dac05f49c4818fb8fcbd05e2b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/43c88984fee84f8f8ba93b460209c294.png
[b22c1700cce74857ba16a5cf5e1bebeb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/dd88b4c27d474175a24af3bc96d8cf5f.png
[5b662c29cfc14de0a7a6fcfc4d552d75.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/155fa17e30ec4f47bcb759a3f7841cb3.png
[253ba667ca464bd78651ddb12260d495.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/646b2db3b44f4f84859f8e06bfbad58e.png
[bb40a886195e4664969784dad3694440.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8c0983c8242f4647b61aeba2cde2fd78.png
[3be144a1755043399cf5ea5e4110e5d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ea48d91595904a7386f072764d1e6442.png
[64f215cfef06459f924834666457c5e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8e39df7dc05b4217ac2f3c5dfb05edc5.png
[1ef404f31787417397f2a9f6922a9bf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ea3c330e98454661bd16e67cbb666bbb.png
[Link 1]: https://blog.csdn.net/weixin_43586713/article/details/119820797
[5fe4954a395b4cf4aabe669a39f9b8f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/74183e8ba95940a8a1772d794d67f327.png
[f1b93741173e4ee1afad6533bf911392.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/0f684fdf326e4fdd88e9466fa666385a.png
[3435100309af48669263a885bc849c0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7b1887f1721c4f5393a4d50c7e8f9aa2.png
[fb65dca0d5d64345b2b35e38aa091a88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/407c330473434744926dca3a97c05eca.png
[d3cc5cd393b54d369817c082e072cd4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3281ae0ec533407ea259f282f14c24f0.png
[c2c22f5584594c0794e623accc81da26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/195ef91ec3e74b448e5301be68d68599.png
[12d30ab2b0d7493e89f8990588efe8a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/24029259b4e94cfea097b2fd518c4746.png
[318bdf0560d84b04b990f45a076369f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6dce744a046e4645a6c4e1ac3172e57a.png
[b0c125abb2944e68adcfee9782e70c22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/546a8fc02f7e4714a490e0ee4145683d.png
[0d379fde83164666bd6f66abdc95ec74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/051ba0df4e84413cb34669e3dff2d041.png
[46ccbb63560e44818dd4491205ab1111.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2cdcb2e0c5834159bdd927b16d1907d8.png
[2f0163db5ee74b40978a4445eb60832a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7b24f8ada55e4612922f50d16779821d.png
[f7667ca5a0674e448032a2fff0f1d403.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/63e967aa56a146baafc4afcac7dc6f02.png
[4d30c4a5276449798f2a759d71949956.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6c05e879db1549ff91731c78d546cde8.png