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

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

一、简单排序

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

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

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

二、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();
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34

• 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;
          }
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25

• 运行结果
  

三、冒泡排序

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

我们的需求是：

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

排序原理：

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

< 冒泡排序 API 设计 >

< 冒泡排序代码实现 >

• 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;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24

• 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));
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 运行结果

  

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

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

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

元素比较的次数为（n 为元素的个数）：
$$(n-1)+(n-2)+(n-3)+\cdots +2+1=\frac{(n-1+1)\times (n-1)}{2}=\frac{n^2-n}{2}$$

元素交换的次数为：
$$(n-1)+(n-2)+(n-3)+\cdots +2+1=\frac{(n-1+1)\times (n-1)}{2}=\frac{n^2-n}{2}$$

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

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

四、选择排序

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

我们的需求是：

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

排序原理：

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

< 选择排序 API 设计 >

< 选择排序代码实现 >

• 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;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30

• 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));
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 运算结果
  

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

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

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

元素比较的次数为：
$$(n-1)+(n-2)+(n-3)+\cdots +2+1=\frac{(n-1+1)\times (n-1)}{2}=\frac{n^2-n}{2}$$

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

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

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

五、插入排序

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

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

我们的需求是：

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

排序原理：

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

< 插入排序 API 设计 >

< 插入排序代码实现 >

• 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;
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29

• 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));
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 运行结果

  

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

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

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

元素比较的次数为：
$$(n-1)+(n-2)+(n-3)+\cdots +2+1=\frac{(n-1+1)\times (n-1)}{2}=\frac{n^2-n}{2}$$

元素交换的次数为：
$$(n-1)+(n-2)+(n-3)+\cdots +2+1=\frac{(n-1+1)\times (n-1)}{2}=\frac{n^2-n}{2}$$

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

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

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