【数据结构与算法】简单排序

阳光穿透心脏的1/2处 2024-04-26 02:20 64阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年10月22日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  一、简单排序
 *  二、Comparable接口
 *  三、冒泡排序
 *  四、选择排序
 *  五、插入排序

## 一、简单排序 ##

在我们的程序中，排序是非常常见的一种需求，提供一些数据元素，把这些数据元素按照一定的规则进行排序。比  
如查询一些订单，按照订单的日期进行排序；再比如查询一些商品，按照商品的价格进行排序等等

在 **Java** 的开发工具包 **jdk** 中，已经给我们提供了很多数据结构与算法的实现，比如 **List**、**Set**、**Map**、**Math** 等等，它们都是以 **API** 的方式提供，这种方式的好处在于一次编写，多处使用。我们借鉴 **jdk** 的方式，也把算法封装到某个类中，所以，在我们写 **Java** 代码之前，就需要先进行 **API** 的设计，设计好之后，再对这些 **API** 进行实现

比如我们先设计一套 **API** 如下：

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>ArrayList</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>ArrayList()</code>：创建 ArrayList 对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>boolean add(E e)</code>：向集合中添加元素</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>E remove(int index)</code>：从集合中删除指定的元素</td> 
  </tr> 
 </tbody> 
</table>

## 二、Comparable接口 ##

**Java** 提供了一个接口 **Comparable** 用来定义排序的规则，有 **Java** 基础的小伙伴对这个常见的接口应该不陌生，这里我们以案例的形式对 **Comparable** 接口做一个简单的介绍

**需求：**

1.  定义一个学生类 **Student**，具有年龄 **age** 和姓名 **userName** 两个属性，并通过 **Comparable** 接口提供比较规则
2.  定义测试类 **Test**，在测试类 **Test** 中定义测试方法 `Comparable getMax(Comparable c1,Comparable c2)` 完成测试

*  Student类
    
        public class Student implements Comparable<Student> {
              
            private String userName;
            private int age;
        
            public String getUserName() {
              
                return userName;
            }
        
            public void setUserName(String userName) {
              
                this.userName = userName;
            }
        
            public int getAge() {
              
                return age;
            }
        
            public void setAge(int age) {
              
                this.age = age;
            }
        
            @Override
            public String toString() {
              
                return "Student{" +
                        "userName='" + userName + '\'' +
                        ", age=" + age +
                        '}';
            }
        
            //定义比较规则
            @Override
            public int compareTo(Student o) {
              
                return this.getAge() - o.getAge();
            }
        }
 *  test类
    
        public class test {
              
            public static void main(String[] args) {
              
                Student s1 = new Student();
                s1.setUserName("张三");
                s1.setAge(20);
        
                Student s2 = new Student();
                s2.setUserName("李四");
                s2.setAge(21);
        
                Comparable max = getMax(s1, s2);
                System.out.println("max=" + max);
            }
        
            //测试方法，获取两个元素中的较大值
            public static Comparable getMax(Comparable c1, Comparable c2) {
              
                int cmp = c1.compareTo(c2);
        
                if (cmp >= 0) {
              
                    return c1;
                } else {
              
                    return c2;
                }
            }
        }
 *  运行结果  
    ![在这里插入图片描述][3ca2aff19cc84c6d85c2bb27a5a3c7cf.png]

## 三、冒泡排序 ##

冒泡排序（Bubble Sort），是计算机科学领域一种比较简单的排序算法

我们的需求是：

*  排序前：**\{ 4, 3, 5, 6, 2, 1 \}**
 *  排序后：**\{ 1, 2, 3, 4, 5, 6 \}**

排序原理：

*  比较相邻的元素，如果前一个元素比后一个元素大，就交换这两个元素的位置
 *  对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素，最终最后位置的元素就是最大值

![在这里插入图片描述][db3054d2f985467bab0ab7a5fd356c37.gif_pic_center]

**< 冒泡排序 API 设计 >**

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>Bubble</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>Bubble()</code> ：创建 <strong>Bubble</strong> 对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>public static void sort(Comparable[] c)</code> ：对数组内的元素进行排序</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private static boolean greater(Comparable c1, Comparable c2)</code> ： 判断 <strong>c1</strong> 是否大于 <strong>c2</strong></td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private static void exch(Comparable[] c, int i, int j)</code> ：交换 <strong>c</strong> 数组中，索引 <strong>i</strong> 和索引 <strong>j</strong> 处的值</td> 
  </tr> 
 </tbody> 
</table>

**< 冒泡排序代码实现 >**

*  Bubble类
    
        public class Bubble {
              
            //对数组 C 中的元素进行排序
            public static void sort(Comparable[] c) {
              
                for (int i = c.length - 1; i > 0; --i) {
              
                    for (int j = 0; j < i; ++j) {
              
                        if (greater(c[j], c[j + 1])) {
              
                            exch(c, j, j + 1);
                        }
                    }
                }
            }
        
            //比较 c1 元素是否大于 c2 元素
            private static boolean greater(Comparable c1, Comparable c2) {
              
                return c1.compareTo(c2) > 0;
            }
        
            //数组中索引为 i 和索引为 j 的元素互换位置
            private static void exch(Comparable[] c, int i, int j) {
              
                Comparable temp = c[i];
                c[i] = c[j];
                c[j] = temp;
            }
        }
 *  test类
    
        import java.util.Arrays;
        
        public class test {
              
            public static void main(String[] args) {
              
                Integer[] a = {
              4, 5, 6, 3, 2, 1};
                Bubble.sort(a);
                System.out.println(Arrays.toString(a));
            }
        }
 *  运行结果
    
    ![在这里插入图片描述][a9a6e98701094d44a7d115333b1c50fa.png]

**< 冒泡排序时间复杂度分析 >**

冒泡排序中使用了双层 **for** 循环，其中内层循环的循环体是真正完成排序的代码，所以，我们在分析其时间复杂度时，主要分析一下内层循环体的执行次数即可

在最坏的情况下，也就是假如要排序的元素顺序为 **\{ 6, 5, 4, 3, 2, 1 \}** 时，此时

元素比较的次数为（**n** 为元素的个数）：  
 ( n − 1 ) + ( n − 2 ) + ( n − 3 ) + ⋯ + 2 + 1 = ( n − 1 + 1 ) × ( n − 1 ) 2 = n 2 − n 2 (n - 1) + (n - 2) + (n - 3) + \\dots + 2 + 1 = \\frac\{(n - 1 + 1) \\times (n - 1)\}\{2\} = \\frac\{n^2 - n\}\{2\} (n−1)\+(n−2)\+(n−3)\+⋯\+2\+1=2(n−1\+1)×(n−1)=2n2−n

元素交换的次数为：  
 ( n − 1 ) + ( n − 2 ) + ( n − 3 ) + ⋯ + 2 + 1 = ( n − 1 + 1 ) × ( n − 1 ) 2 = n 2 − n 2 (n - 1) + (n - 2) + (n - 3) + \\dots + 2 + 1 = \\frac\{(n - 1 + 1) \\times (n - 1)\}\{2\} = \\frac\{n^2 - n\}\{2\} (n−1)\+(n−2)\+(n−3)\+⋯\+2\+1=2(n−1\+1)×(n−1)=2n2−n

所以总的执行次数为：  
 n 2 − n 2 + n 2 − n 2 = n 2 − n \\frac\{n^2 - n\}\{2\} + \\frac\{n^2 - n\}\{2\} = n^2 - n 2n2−n\+2n2−n=n2−n

按照大 **O** 推导法则，保留函数中的最高阶项，那么最终冒泡排序的时间复杂度为  O ( n 2 ) O(n^2) O(n2)

## 四、选择排序 ##

选择排序是一种更加简单直观的排序方法

我们的需求是：

*  排序前：**\{ 4, 3, 5, 6, 2, 1 \}**
 *  排序后：**\{ 1, 2, 3, 4, 5, 6 \}**

排序原理：

*  每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他索引处的值，则假定其他某个所以处的值为最小值，最后可以找到最小值所在的索引
 *  交换第一个索引处和最小值所在的索引处的值

![在这里插入图片描述][201333d3a0e04b6ea9118a1bae5742f7.gif_pic_center]

**< 选择排序 API 设计 >**

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>Selection</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>Selection()</code> ：创建 <strong>Selection</strong> 对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>public static void sort(Comparable[] c)</code> ：对数组内的元素进行排序</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private static boolean greater(Comparable c1, Comparable c2)</code> ： 判断 <strong>c1</strong> 是否大于 <strong>c2</strong></td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private static void exch(Comparable[] c, int i, int j)</code> ：交换 <strong>c</strong> 数组中，索引 <strong>i</strong> 和索引 <strong>j</strong> 处的值</td> 
  </tr> 
 </tbody> 
</table>

**< 选择排序代码实现 >**

*  Selection类
    
        public class Selection {
              
            //对数组 C 中的元素进行排序
            public static void sort(Comparable[] c) {
              
                for (int i = 0; i < c.length - 1; ++i) {
              
                    //假定本次遍历，最小值所在的索引是 i
                    int minIndex = i;
                    for (int j = i + 1; j < c.length; ++j) {
              
                        if (greater(c[minIndex], c[j])) {
              
                            //交换最小值所在的索引
                            minIndex = j;
                        }
                    }
        
                    //交换 i 索引处和 minIndex 索引处的值
                    exch(c, i, minIndex);
                }
            }
        
            //比较 c1 元素是否大于 c2 元素
            private static boolean greater(Comparable c1, Comparable c2) {
              
                return c1.compareTo(c2) > 0;
            }
        
            //数组中索引为 i 和索引为 j 的元素互换位置
            private static void exch(Comparable[] c, int i, int j) {
              
                Comparable temp = c[i];
                c[i] = c[j];
                c[j] = temp;
            }
        }
 *  test类
    
        import java.util.Arrays;
        
        public class test {
              
            public static void main(String[] args) {
              
                Integer[] a = {
              4, 5, 6, 3, 2, 1};
                Selection.sort(a);
                System.out.println(Arrays.toString(a));
            }
        }
 *  运算结果  
    ![在这里插入图片描述][26534bc209834552b3fa83c67656ecb5.png]

**< 选择排序时间复杂度分析 >**

选择排序使用了双层 **for** 循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换和数据比较次数

在最坏的情况下，也就是假如要排序的元素顺序为 **\{ 6, 5, 4, 3, 2, 1 \}** 时，此时

元素比较的次数为：  
 ( n − 1 ) + ( n − 2 ) + ( n − 3 ) + ⋯ + 2 + 1 = ( n − 1 + 1 ) × ( n − 1 ) 2 = n 2 − n 2 (n - 1) + (n - 2) + (n - 3) + \\dots + 2 + 1 = \\frac\{(n - 1 + 1) \\times (n - 1)\}\{2\} = \\frac\{n^2 - n\}\{2\} (n−1)\+(n−2)\+(n−3)\+⋯\+2\+1=2(n−1\+1)×(n−1)=2n2−n

元素交换的次数为：  
 n − 1 n - 1 n−1

所以总的执行次数为：  
 n 2 − n 2 + n − 1 = n 2 + n − 2 2 \\frac\{n^2 - n\}\{2\} + n - 1 = \\frac\{n^2 + n - 2\}\{2\} 2n2−n\+n−1=2n2\+n−2

按照大 **O** 推导法则，保留函数中的最高阶项，那么最终选择排序的时间复杂度为  O ( n 2 ) O(n^2) O(n2)

## 五、插入排序 ##

插入排序（Insertion sort）是一种简单直观且稳定的排序算法

插入排序的工作方式非常像人们排序手上的扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置，为了找到一张牌的正确位置，我们从左到右将它与已在手中的每张牌进行比较

![在这里插入图片描述][970192a9aa454c14b87a381e629a80c6.gif_pic_center]

我们的需求是：

*  排序前：**\{ 4, 3, 5, 6, 2, 1 \}**
 *  排序后：**\{ 1, 2, 3, 4, 5, 6 \}**

排序原理：

*  把所有的元素分为两组，已经排序的未排序的
 *  找到未排序的组中的第一个元素，向已经排序的组中进行插入
 *  倒序遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位

**< 插入排序 API 设计 >**

<table> 
 <thead> 
  <tr> 
   <th>类名</th> 
   <th>Insertion</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td><code>Insertion()</code> ：创建 <strong>Insertion</strong> 对象</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>public static void sort(Comparable[] c)</code> ：对数组内的元素进行排序</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private static boolean greater(Comparable c1, Comparable c2)</code> ： 判断 <strong>c1</strong> 是否大于 <strong>c2</strong></td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td><code>private static void exch(Comparable[] c, int i, int j)</code> ：交换 <strong>c</strong> 数组中，索引 <strong>i</strong> 和索引 <strong>j</strong> 处的值</td> 
  </tr> 
 </tbody> 
</table>

**< 插入排序代码实现 >**

*  Insertion类
    
        public class Insertion {
              
            //对数组 C 中的元素进行排序
            public static void sort(Comparable[] c) {
              
                for (int i = 1; i < c.length; ++i) {
              
                    //当前元素为 c[i]，依次和 i 前面的元素比较，找到一个小于等于 c[i]的元素
                    for (int j = i; j > 0; --j) {
              
                        if (greater(c[j - 1], c[j])) {
              
                            //交换元素
                            exch(c, j - 1, j);
                        } else {
              
                            //找到了该元素，结束循环
                            break;
                        }
                    }
                }
            }
        
            //比较 c1 元素是否大于 c2 元素
            private static boolean greater(Comparable c1, Comparable c2) {
              
                return c1.compareTo(c2) > 0;
            }
        
            //数组中索引为 i 和索引为 j 的元素互换位置
            private static void exch(Comparable[] c, int i, int j) {
              
                Comparable temp = c[i];
                c[i] = c[j];
                c[j] = temp;
            }
        }
 *  test类
    
        import java.util.Arrays;
        
        public class test {
              
            public static void main(String[] args) {
              
                Integer[] a = {
              4, 5, 6, 3, 2, 1};
                Insertion.sort(a);
                System.out.println(Arrays.toString(a));
            }
        }
 *  运行结果
    
    ![在这里插入图片描述][152a1dc8a6474f69bb79c263e5ff9773.png]

**< 插入排序时间复杂度分析 >**

插入排序使用了双层 **for** 循环，其中内层循环的循环体是真正完成排序的代码，所以，我们主要分析一下内层循环体的执行次数即可

在最坏的情况下，也就是假如要排序的元素顺序为 **\{ 6, 5, 4, 3, 2, 1 \}** 时，此时

所以总的执行次数为：  
 n 2 − n 2 + n 2 − n 2 = n 2 − n \\frac\{n^2 - n\}\{2\} + \\frac\{n^2 - n\}\{2\} = n^2 - n 2n2−n\+2n2−n=n2−n

按照大 **O** 推导法则，保留函数中的最高阶项，那么最终选择排序的时间复杂度为  O ( n 2 ) O(n^2) O(n2)

> 简单排序的介绍到这里就结束了，继续加油吧

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_12010243.html?spm=1001.2014.3001.5482
[3ca2aff19cc84c6d85c2bb27a5a3c7cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/4e6cc05b6aa94b6095981b09b50ef382.png
[db3054d2f985467bab0ab7a5fd356c37.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/45a443df35c54aa5972f99d87e7894c8.gif
[a9a6e98701094d44a7d115333b1c50fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/95d30cf56aa646e0b0df60fb4570f392.png
[201333d3a0e04b6ea9118a1bae5742f7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/11504610044c43d19cdaefb9a29bae0f.gif
[26534bc209834552b3fa83c67656ecb5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/267572d4b1bb4aa5b975b69cd543c704.png
[970192a9aa454c14b87a381e629a80c6.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b2ebd11c5a6b48da99d120d9270509dd.gif
[152a1dc8a6474f69bb79c263e5ff9773.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/7a08c87705ab43b299a0c6e4f2122652.png