Java实现常用的排序算法（冒泡排序、选择排序、插入排序、希尔排序）

骑猪看日落 2024-04-07 13:55 65阅读 0赞

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

*  常见的排序算法
 *  排序算法的时间复杂度
 *  冒泡排序
 *   *  1.简介
     *  2.思路分析
     *  3.图解
     *   *  1.第一次循环（黄色代表交换位置，红色代表确定最终位置）
         *  2.第二次循环
         *  3.第三次循环
         *  4.第四次循环
     *  4.代码实现
 *  选择排序
 *   *  1.简介
     *  2.思路分析
     *   *  2.1 第一次交换数据
         *  2.2 第二次 从 i+1开始
         *  2.3总结
     *  3.图解
     *  4.代码实现
 *  插入排序
 *   *  1.简介
     *  2.思路分析
     *  3.图解
     *   *  3.1第一轮
         *  3.2第二轮
         *  3.3第三轮
         *  3.4第四轮
     *  4.代码实现
 *  希尔排序
 *   *  1.简介
     *  2.思路分析
     *  3.图解
     *   *  3.1 第一轮
         *  3.2 第二轮
     *  4.代码实现

## 常见的排序算法 ##

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

## 排序算法的时间复杂度 ##

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>平均时间</th> 
   <th>最差时间</th> 
   <th>稳定性</th> 
   <th>空间复杂度</th> 
   <th>备注</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>n较小时好</td> 
  </tr> 
  <tr> 
   <td>交换排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(1) n</td> 
   <td>较小时好</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(1) n</td> 
   <td>较小时好</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>大部分已有序时好</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>稳定</td> 
   <td>O(n)</td> 
   <td>二维数组（桶）、一维数组（桶中首元素的位置）</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(nlogn)</td> 
   <td>O(ns)(1&lt;s&lt;2)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>s是所选分组</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(logn)</td> 
   <td>n较大时好</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>n较大时好</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>n较大时好</td> 
  </tr> 
 </tbody> 
</table>

## 冒泡排序 ##

### 1.简介 ###

> 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。  
> 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。  
> 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

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

*  比较相邻的两个元素，如果第一个比第二个大那么就交换位置
 *  对后续的每一次元素都进行这个操作，直到最后一个结束第一轮循环，这样最后一个元素一定是最大的元素，所以后续进行循环比较时，可以不需要对最后一个元素进行比较
 *  重复以上步骤，依次排除上一次循环的最后一个元素，这样内层循环的次数会越来越少
 *  直到没有任何一对数字需要比较
 *  外层循环次数为**数组元素个数-1**，而且==每次内层循环比较次数越来越少–
 *  优化：如果在某次外层循环中元素没有发生交换，证明已经是有序数组，那么可以结束循环

### 3.图解 ###

#### 1.第一次循环（黄色代表交换位置，红色代表确定最终位置） ####

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

#### 2.第二次循环 ####

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

#### 3.第三次循环 ####

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

#### 4.第四次循环 ####

![在这里插入图片描述][3c89ecf98b5e40b6be2e8e81bad76607.png]  
结束循环

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

/**
     * 冒泡排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/7
     */
    public class Bubbling {
        
        public static void main(String[] args) {
        
            int[] arr = {
        3,9,-1,7,21};
            // 外层循环次数为数组的长度-1
            for (int i = 0; i < arr.length - 1; i++) {
        
                // 内层循环次数，每次都会减少
                for (int j = 0; j < arr.length - 1 - i; j++) {
        
                    // 交换位置
                    if (arr[j] > arr[j+1]){
        
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
    
            // 打印
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
        }
    
    }

优化：如果在某次外层循环结束后发现数组元素位置没有发生改变，那么循环结束，已经是有序的数组了

代码：

/**
     * 冒泡排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/7
     */
    public class Bubbling {
        
        public static void main(String[] args) {
        
            int[] arr = {
        3,9,-1,7,21};
            // 外层循环次数为数组的长度-1
            for (int i = 0; i < arr.length - 1; i++) {
        
                // 如果内层循环没有交换位置，那么已经是有序数组，结束循环
                boolean flag = true;
                // 内层循环次数，每次都会减少
                for (int j = 0; j < arr.length - 1 - i; j++) {
        
                    // 交换位置
                    if (arr[j] > arr[j+1]){
        
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        flag = false;
                    }
                }
                if (flag){
        
                    break;
                }
            }
    
            // 打印
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
        }
    
    }

## 选择排序 ##

### 1.简介 ###

> 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

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

#### 2.1 第一次交换数据 ####

/**
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/7
     */
    public class Deduction {
        
        public static void main(String[] args) {
        
            int[] arr = {
        8,3,2,1,7,4,6,5};
            // 记录最小数的下标
            int min;
            // 假设min=0开始
            min = 0;
            // 既然我们都假设下标为0的是最小，那么就从他后面开始比较
            for (int i = 1; i < arr.length; i++) {
        
                // 如果后面的元素中有小于的元素，记住的他下标
                if (arr[min] > arr[i]){
        
                    min = i;
                }
            }
            // 交换
            int temp = arr[0];
            arr[0] = arr[min];
            arr[min] = temp;
    
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
    
            // 打印获取到 1 3 2 8 7 4 6 5 
    
        }
    }

#### 2.2 第二次 从 i+1开始 ####

/**
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/7
     */
    public class Deduction {
        
        public static void main(String[] args) {
        
    //        int[] arr = {8,3,2,1,7,4,6,5};
            int[] arr = {
        1,3,2,8,7,4,6,5};
            // 记录最小数的下标
            int min;
            // 假设min=1开始
            min = 1;
            // 既然我们都假设下标为1的是最小，那么就从他后面开始比较
            for (int i = 2; i < arr.length; i++) {
        
                // 如果后面的元素中有小于的元素，记住的他下标
                if (arr[min] > arr[i]){
        
                    min = i;
                }
            }
            // 交换
            int temp = arr[1];
            arr[1] = arr[min];
            arr[min] = temp;
    
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
    
            // 打印获取到 1 2 3 8 7 4 6 5 
    
        }
    }

以此类推

#### 2.3总结 ####

*  i 从 0 开始，假设min代表最小值的索引，一开始假设min = i， 然后找到**后面**数组中最小元素的下标，让min = minIndex，交换位置，注意在寻找最小值索引下标时，其他元素的位置是不能动的
 *  然后数组往后移，因为第一个数已经是最小数了，不需要再进行比较了，从 i+1开始
 *  重复以上步骤，直到 排序结束
 *  一共需要遍历 数组长度 - 1次。

### 3.图解 ###

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

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

/**
     * 选择排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/7
     */
    public class Choice {
        
        public static void main(String[] args) {
        
            int[] arr = {
        8,3,2,1,7,4,6,5};
            // 记录最小数的下标
            int min;
            // 外层循环次数为数组长度 - 1
            for (int i = 0; i < arr.length - 1; i++) {
        
                min = i;
                // 内层循环每次都是从i+1开始
                for (int j = i+1; j < arr.length; j++) {
        
                    // 找出最小数的下标
                    if (arr[min] > arr[j]){
        
                        min = j;
                    }
                }
                // 如果不是同一个数，那么就交换位置
                if (min != i){
        
                    int temp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = temp;
                }
            }
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
        }
    }

## 插入排序 ##

### 1.简介 ###

> 插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

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

*  因为原数组中的第一个元素作为有序列表的第一个元素，所以直接从索引为1的元素开始，当1作为插入元素与有序列表中的最后一个元素进行比较
 *  如果插入元素小于，那么有序列表中最后一个元素就要后移一位，直到找到**有序列表**中元素**不大于**插入元素的位置，或者索引小于0时，结束比较
 *  然后再将插入元素赋值

### 3.图解 ###

注意这里红色的数组代表已经是有序列表元素

#### 3.1第一轮 ####

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

#### 3.2第二轮 ####

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

#### 3.3第三轮 ####

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

#### 3.4第四轮 ####

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

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

/**
     * 插入排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/9
     */
    public class InsertSorted {
        
        public static void main(String[] args) {
        
            int[] arr = {
        3, 1, 6, 10, 2};
    
            for (int i = 1; i < arr.length; i++) {
        
                // 保留即将插入元素的值
                int insertValue = arr[i];
                // 当前索引
                int index = i;
                // 1.如果索引大于0，说明还没遍历完
                // 2.如果插入的值小于有序列表中的值，那么久有序列表中大于插入元素的元素，就要后移
                while (index > 0 && insertValue < arr[index-1]){
        
                    arr[index] = arr[index-1];
                    index --;
                }
                // 直到找到插入元素不大于有序列表中元素的位置
                arr[index] = insertValue;
    
            }
    		// 打印
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
    
        }
    }

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

## 希尔排序 ##

### 1.简介 ###

> 希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。  
> 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个数据恰被分成一组，算法便终止。

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

*  选择一个增量序列t1（一般是数组长度/2），t2（一般是一个分组长度/2），……，tk，其中 ti > tj, tk = 1；
 *  按增量序列个数 k，对序列进行 k 趟排序；
 *  每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

### 3.图解 ###

#### 3.1 第一轮 ####

增量为3，直接从arr\[3\]开始进行比对，发现arr\[3\] > arr\[0\],不需要换位置，arr\[4\] < arr\[1\]需要换位置  
![在这里插入图片描述][5a9ee1e7c5d545b0b1a3047281601008.png]  
交换位置后，继续进行比较

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

直到arr\[6\]<arr\[3\],交换位置  
![在这里插入图片描述][4cff7e011d0d4ee78fba1214bc6c2e09.png]  
然后我们发现 arr\[3\] 还能再和 arr\[0\] 进行比较 因为 index-gap >= 0 就能继续比较

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

#### 3.2 第二轮 ####

从arr\[1\]开始进行比较，依次往后比较，直到 arr\[6\] < arr\[5\]

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

交换位置后，arr\[5\] 与 arr\[4\] 进行比较，交换位置  
![在这里插入图片描述][e1a69ff450bf484096ec4636e3c1dd0c.png]

结束  
![在这里插入图片描述][7c298fa396fd4e9cbd2ffa8009de7ff8.png]

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

/**
     * 希尔排序
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/9/9
     */
    public class ShellInsert {
        
        public static void main(String[] args) {
        
            int[] arr = {
        23,34,21,31,18,98,10};
            // 增量
            int gap = arr.length/2;
            // 只要增量大于等于1就继续分组
            while (gap >= 1){
        
    
                // 从索引=增量开始，依次往后
                for (int i = gap; i < arr.length; i++) {
        
                    // 定义一个变量，防止下面代码影响原 i 的值
                    int j = i;
                    // 只有 arr[j] < arr[j-gap] 交换位置 ，而且可能一次不一定能比较完，需要多次比较 j-gap >= 0
                    while (j-gap >= 0 && arr[j] < arr[j-gap]){
        
                        // 交换
                        int temp = arr[j];
                        arr[j] = arr[j-gap];
                        arr[j-gap] = temp;
                        // 假设 j = 6 时，可以多次执行
                        j -= gap;
                    }
                }
    
                // 控制增量
                gap /= 2;
    
            }
    
            // 打印
            for (int i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i]+" ");
            }
    
        }
    }

[50a81312f3ab4b78a2501f193b908c0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7b8bb2226b824540ba639c1ce20dc5e8.png
[e23fac71b95d4b2cbdc3e135ec436008.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9c7406155c3c4bd0adbeb5f5bd5c8b2f.png
[b0378e25771848328f05cfb7102f098b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1cd3e95b4cf445329c2dec9673618324.png
[fd7a044f6374477bbdc9235dec4cf18b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/451aa0ed3da24bbcafba5c49c9979341.png
[3c89ecf98b5e40b6be2e8e81bad76607.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b20593418ab54cd7856570ff9c0cdcf6.png
[9e58d3d5a0c949c6a6630ace778a9143.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/946b963ad6984df68aa4214b286853eb.png
[e99581d1b93241479bef82cfa01ccb45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4538283d032545038b40216db19197ea.png
[0a85807c63804ffa8f98d627b50aa76d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/5f943fe3122f4cd784f1a40076d7a8ec.png
[456f7cbd2b8e458390f8a67265a8d6a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/aea0d8524ac349d9bddfbfa7fd4c025c.png
[416a2cc31ad84f38b758490b27cca7e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/06ecca206ad24f108e8defa360eee3d5.png
[5a9ee1e7c5d545b0b1a3047281601008.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3e24735dcde64d269089de62799597ec.png
[fbdfdef70da145a1ae3765872bc27f94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ae0fd7e77fce4dfd86aca46064799b84.png
[4cff7e011d0d4ee78fba1214bc6c2e09.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f6c037414b6b45698b2ed69c1f5c8ece.png
[ea36a67c23b2497795f78181b80cf455.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b89c7ed742634de8895ae23d321e367d.png
[a7562ffc38f84ab28d49d1c53daff9e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9e0b25dd6fe24653bfd374a0ba86bb67.png
[e1a69ff450bf484096ec4636e3c1dd0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7346619c283346179905106ebc05f5e0.png
[7c298fa396fd4e9cbd2ffa8009de7ff8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/e4fc307333504b24a67ba379c0462567.png