简单排序

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

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

例:

类名ArrayList
构造方法ArrayList():创建ArrayList对象
成员方法1.boolean add(E e):向集合中添加元素 2.E remove(int index):从集合中删除指定的元素

Comparable接口介绍

因为要学习排序,所有肯定会在元素之间进行比较,而java提供了一个接口Comparable就是用来定义排序规则的,举个例子

需求:

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

Student类:

public class TestComparable {

  public static void main(String[] args) {
    //创建2个Student对象,调用getMax方法,完成测试
    Student student = new Student();
    Student student1 = student;
    student1.setUsername("YQHP");
    student1.setAge(20);
    Student student2 = new Student();
    student2.setUsername("XP");
    student2.setAge(19);

    Comparable max = getMax(student1, student2);
    System.out.println(max);
  }

  public static Comparable getMax(Comparable c1, Comparable c2) {
    int result = c1.compareTo(c2);
    //如果result<0,则c1<2
    //如果result>0;则c1>c2
    //如果result=0,则c1=c2
    if (result >= 0) {
      return c1;
    } else {
      return c2;
    }
  }
}

TestComparable类:

public class TestComparable {

  public static void main(String[] args) {
    //创建2个Student对象,调用getMax方法,完成测试
    Student student = new Student();
    Student student1 = student;
    student1.setUsername("YQHP");
    student1.setAge(20);
    Student student2 = new Student();
    student2.setUsername("XP");
    student2.setAge(19);

    Comparable max = getMax(student1, student2);
    System.out.println(max);
  }

  public static Comparable getMax(Comparable c1, Comparable c2) {
    int result = c1.compareTo(c2);
    //如果result<0,则c1<2
    //如果result>0;则c1>c2
    //如果result=0,则c1=c2
    if (result >= 0) {
      return c1;
    } else {
      return c2;
    }
  }
}

冒泡排序

冒泡排序(Bubble Sort)是一种计算机科学领域的一种较简单的排序算法

例:

  • 排序前:$4,5,6,3,2,1$
  • 排序后:$1,2,3,4,5,6$

排序原理:

  1. 比较相邻的元素,如果前一个元素比后一个元素大,就交换这两个元素的位置
  2. 对每一对相邻的元素做同样的工作,从开始第一对元素到结尾的最后一对元素,最终最后位置的元素就是最大值
冒泡排序API设计
类名Bubble
构造方法Bubble():创建Bubble对象
成员方法1.public static void(Comparable[] a):对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j处的值
冒泡排序的代码实现

Bubble对象

public class Bubble {

  /**
   * 对数组A中的元素进行排序
   */
  public static void sort(Comparable[] a) {
    /**其实如果数组有n个数字,一共只需要执行n-2次排序即可完成
     * 因为第n-2次是第一个比第二个比较,而n-1次与n次就已经没有意义了
     */
    for (int i = a.length - 1; i > 0; i--) {
      //从第0个开始比较,到排好的最后一个
      for (int j = 0; j < i; j++) {
        //如果v>w,就交换
        if (greater(a[j], a[j + 1])) {
          exch(a, j, j + 1);
        }
      }
    }
  }

  /**
   * 比较v是否大于w/
   */
  private static boolean greater(Comparable v, Comparable w) {
    //如果v>w,则返回true,相反则false
    return v.compareTo(w) > 0;
  }

  /**
   * 数组i与j交换位置
   */
  private static void exch(Comparable[] a, int i, int j) {
    Comparable temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
}

测试方法

public static void main(String[] args) {
    //如果写int[] arr={4,5,6,3,2,1};会报错的,因为不是comparable类型
    Integer[] arr = {4, 5, 6, 3, 2, 1};
    Bubble.sort(arr);
    System.out.println(Arrays.toString(arr));
  }
冒泡排序的时间复杂度分析

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

在最坏的情况下,也就是假如要排序的数组的元素全为逆序,例如$6,5,4,3,2,1$

  • 元素比较的次数

    • $(N-1)+(N-2)+(N-3)+...+(2)+(1)=\cfrac{N^2}{2}-\cfrac{N}{2}$
  • 元素交换的次数

    • $(N-1)+(N-2)+(N-3)+...+(2)+(1)=\cfrac{N^2}{2}-\cfrac{N}{2}$
  • 总的执行次数

    • $(\cfrac{N^2}{2}-\cfrac{N}{2})+(\cfrac{N^2}{2}-\cfrac{N}{2})=N^2-N$

根据大O推导法则,保留函数中的最高阶项,那么冒泡函数的时间复杂度为$O(N^2)$

选择排序

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

需求

排序前:$4,6,8,7,9,2,10,1$

排序后:$1,2,4,5,7,8,9,10$

排序原理
  1. 每一次遍历的过程中,都假定第一个索引处的值是最小值,和其他索引处的值一次进行比较,如果当前索引处的值大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后可以找到最小值所在的索引
  2. 交换第一个索引处和最小值所在的索引处的值

选择排序API设计
类名Selection
构造方法Selection():创建Selection对象
成员方法1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j的位置
选择排序的代码实现

Selection对象

public class Selection {

  /**
   * 对数组a中的元素进行选择排序
   */
  public static void sort(Comparable[] a) {
    for (int i = 0; i <= a.length - 2; i++) {
      //temp做记录最小值的位置,到最后与第一个要排序的进行交换
      int temp = i, j = i + 1;
      while (j < a.length) {
        if (greater(a[temp], a[j])) {
          //交换数组元素的坐标
          temp = j;
        }
        //不管找没找到是否有更小的,j都会++,继续向后找,直到找到最后
        j++;
      }
      //交换元素值
      exch(a, i, temp);
    }
  }

  /**
   * 如果元素v大于元素w
   */

  private static boolean greater(Comparable v, Comparable w) {
    return v.compareTo(w) > 0;
  }

  /**
   * 数组元素i与j交换位置
   */
  private static void exch(Comparable[] a, int i, int j) {
    Comparable temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
}

测试方法

public static void main(String[] args) {
    //测试数据
    Integer arr[] = {4, 6, 8, 7, 9, 2, 10, 1};
    Selection.sort(arr);
    System.out.println(Arrays.toString(arr));
  }
选择排序的时间复杂分析

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

  • 数据比较次数

    • $(N-1)+(N-2)+(N-3)+...+(2)+(1)=\cfrac{N^2}{2}-\cfrac{N}{2}$
  • 数据交换次数

    • $N-1$
  • 时间复杂度

    • $\cfrac{N^2}{2}+\cfrac{N}{2}-1$

根据大$O$推导法则,保留最高阶项,去除常熟因子,时间复杂度为$O(N^2)$

插入排序

插入排序(Insertion sort)是一种简单直观且稳定的排序方法

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

需求

排序前:$4,3,2,10,12,1,5,6$

排序后:$1,2,3,4,5,6,10,12$

排序原理
  1. 把所有的元素分为两组,已经排序的和未排序的
  2. 找到未排序的组中第一个元素,向已经排序的组中进行排序
  3. 倒叙遍历已经排序的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他的元素向后移动一位
插入排序API设计
类名Insertion
构造方法Insertion():创建Insertion对象
成员方法1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j):交换a数组中,索引i和索引j的位置

Insertion对象

public class Insertion {

  public static void sort(Comparable[] a) {
    //从第一个开始,挨个开始插入排序到最后
    for (int i = 1; i <= a.length - 1; i++) {
      //以倒序的方式进行向前查找
      for (int j = i; j > 0; j--) {
        //如果前面比后面大,就交换元素i与j,如果前面比后面小,则直接跳出此层循环,继续向后进行排序
        if (greater(a[j - 1], a[j])) {
          exch(a, j - 1, j);
        } else {
          break;
        }
      }
    }
  }


  /**
   * 创建比较元素的方法
   */
  private static boolean greater(Comparable v, Comparable w) {
    return v.compareTo(w) > 0;
  }


  /**
   * 创建交换元素i与j的值方法
   */
  private static void exch(Comparable[] a, int i, int j) {
    Comparable temp = a[j];
    a[j] = a[i];
    a[i] = temp;
  }
}

测试方法

public static void main(String[] args) {
    Integer[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
    Insertion.sort(arr);
    System.out.println(Arrays.toString(arr));
  }
插入排序的时间复杂度分析

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

最坏情况,也是就是待排序的数据元素要从当前位置找到数组头部

  • 比较的次数

    • $(N-1)+(N-2)+(N-3)+...+(2)+(1)=\cfrac{N^2}{2}-\cfrac{N}{2}$
  • 交换的次数

    • $(N-1)+(N-2)+(N-3)+...+(2)+(1)=\cfrac{N^2}{2}-\cfrac{N}{2}$
  • 总执行的次数

    • $(\cfrac{N^2}{2}-\cfrac{N}{2})+(\cfrac{N^2}{2}-\cfrac{N}{2})=N^2-N$

根据大$O$推导法则,保留函数中的最高阶项,那么最终插入排序的时间复杂度为$O(N^2)$

Last modification:March 22nd, 2021 at 05:59 pm