02

标签: 数据结构与算法

目录

Comparable接口

简单排序

冒泡排序

选择排序

插入排序

高级排序

希尔排序

概念

增常量h的确定

代码

时间复杂度

归并排序


  1. Comparable接口

    1. 作用
      1. 通常用于给对象排序
  2. 简单排序

    1. 冒泡排序

      1. 概念
        1. 从数组的头部开始, 不断的根据相邻的两个数的大小来交换两个数的位置
      2. 时间复杂度: O(n^2)
      3. 不推荐使用
    2. 选择排序

      1. 概念
        1. 从数组中选择出合适大小的数字, 放大合适的位置
      2. 时间复杂度: O(n^2)
      3. 不推荐使用
    3. 插入排序

      1. 概念
        1. 简单直观切稳定
        2. 已有数组: 1, 3, 5, 7, 2, 6, 9, 1; 前4个已经排好序了, 现在要给第5个数字2排序, 那么排序的方法是: 2和7进行比较, 2<7, 交换2和7对位置, 然后继续比较2和5, 2<5, 交换2和5的位置, 依次进行即可
      2. 时间复杂度: O(n^2)
      3. 不推荐使用
  3. 高级排序

    1. 希尔排序

      1. 概念

        1. 是插入排序的改良版
        2. 先对数据进行分组, 然后再对每一组数据进行插入排序
        3. 需要进行多次排序, 每一次排序都会使数组更加有序(部分有序)
        4. 最后一次增常量h=1, 这个时候就是普通的插入排序了, 但是此时的数组是部分有序的, 因此比较的次数会大大降到底
      2. 增常量h的确定

        1. 先确定初始值
          1. int h = 1;
            while (h < a.length / 2) {
                h = 2 * h + 1;
            }

             

        2. 再依次减小
          1. 减小规则 h=h/2
      3. 代码

        1. package lq.sort;
          
          import org.junit.Test;
          
          import java.util.Arrays;
          
          /**
           * @author LQ
           * @create 2020-05-24 15:45
           */
          public class Shell {
              @Test
              public void test() {
                  Integer[] arr1 = {8, 1, 0, 4, 1, 9, 45, 3, 7, 9, 10};
                  sort(arr1);
                  System.out.println(Arrays.toString(arr1));
              }
          
              public static void  sort(Comparable[] a) {
                  //先求出增常量h的初始值
                  int h = 1;
                  while (h < a.length / 2) {
                      h = 2 * h + 1;
                  }
                  //希尔排序
                  while (h >= 1) {
                      //
                      /*
                      1 根据h的值分组, h是多少, 分组的个数就是多少
                      2 先假定h的值是3, 即当前分了3组, 从索引值是3的位置开始都是待插入的数, 然后我们依次遍历这些数, 遍历第一个数, 这个数就是属于
                          第一组的, 然后遍历到第二个数, 第二个数是属于第二组的, 然后遍历到第三个数, 第三个数是属于第三组的, 然后遍历到第四个数, 此时,
                          第四个数是属于第一组的, 即遍历到的第四个数是属于第一组的第二个数, 继续遍历, 知道遍历到数组的最后一个数, 排序完成!
                       */
                      //找出待插入的数
                      for (int i = h; i < a.length; i++) {
                          for (int j = i; j >= h; j -= h) {
                              if (greater(a[j - h], a[j])) {
                                  exchange(a, j - h, j);
                              } else {
                                  break;
                              }
                          }
                      }
                      //减小h的值
                      h /= 2;
                  }
              }
          
              /**
               * @param x
               * @param y
               * @return true: x>y
               */
              public static boolean greater(Comparable x, Comparable y) {
                  return x.compareTo(y) > 0;
              }
          
              /**
               * 交换数组中x和y的位置
               * @param a
               * @param x
               * @param y
               */
              public static void exchange(Comparable[] a, int x, int y) {
                  Comparable t;
                  t = a[x];
                  a[x] = a[y];
                  a[y] = t;
              }
          }
          

           

      4. 时间复杂度

        1. 直接计算时间复杂度是比较麻烦的, 所以我们直接拿测试数据进行测试
        2. package lq.test;
          
          import lq.sort.Insertion;
          import lq.sort.Shell;
          import org.junit.Test;
          
          import java.io.BufferedReader;
          import java.io.IOException;
          import java.io.InputStreamReader;
          import java.util.ArrayList;
          
          /**
           * @author LQ
           * @create 2020-05-24 18:10
           */
          public class TestShell {
              @Test
              public void test() throws IOException {
                  //创建数组
                  ArrayList<Integer> arr = new ArrayList<Integer>();
                  //将文件读取出来
                  BufferedReader reader = new BufferedReader(new InputStreamReader(TestShell.class.getClassLoader().getResourceAsStream("reverse_arr.txt")));
                  String line = null;
                  while ((line = reader.readLine()) != null) {
                      arr.add(Integer.parseInt(line));
                  }
                  //调用方法
                  Integer[] arr2 = new Integer[arr.size()];
                  arr.toArray(arr2);
                  testShell(arr2);
          //        testInsertion(arr2);
              }
          
              public void testShell(Integer[] a) {
                  //获取开始时的时间
                  long start = System.currentTimeMillis();
                  //排序
                  Shell.sort(a);
                  //获取结束时的时间
                  long end = System.currentTimeMillis();
                  System.out.println("Shell: " + (end-start) + " ms");
              }
          
          }
          

           

    2. 归并排序

      1. 递归

        1. 方法调用需要先把方法进入栈内存, 如果一个递归算法是一个无穷的递归时, 就会报栈内存溢出异常
      2. 概念

        1. 合并的概念图
      3. 归并排序的代码
        1. package lq.sort;
          
          import org.junit.Test;
          
          import java.util.Arrays;
          
          /**
           * @author LQ
           * @create 2020-05-24 15:45
           */
          public class Merge {
              private static Comparable[] assist;
          
              @Test
              public void test() {
                  Integer[] arr1 = {8, 1, 0, 4, 1, 9, 45, 3, 7, 9, 10};
                  sort(arr1);
                  System.out.println(Arrays.toString(arr1));
              }
          
              public static void sort(Comparable[] a) {
                  //初始化辅助数组
                  assist = new Integer[a.length];
                  //找出开始和结束的索引值
                  int lo = 0;
                  int hi = a.length - 1;
                  //调用方法
                  sort(a, lo, hi);
              }
          
              public static void sort(Comparable[] a, int lo, int hi) {
                  //做安全检验
                  if (lo >= hi) {
                      return;
                  }
                  //求出中间位置的索引值
                  int mid = (lo + hi) / 2;
                  //递归调用
                  sort(a, lo, mid);
                  sort(a, mid + 1, hi);
                  //合并
                  merge(a, lo, mid, hi);
              }
          
              /**
               * 归并算法的核心
               *
               * @param a
               * @param lo
               * @param mid
               * @param hi
               */
              public static void merge(Comparable[] a, int lo, int mid, int hi) {
                  //定义三个指针
                  int i = lo;
                  int p1 = lo;
                  int p2 = mid + 1;
                  //遍历, 移动指针p1 p2 i
                  while (p1 <= mid && p2 <= hi) {
                      if (less(a[p1], a[p2])) {
                          assist[i++] = a[p1++];
                      }else {
                          assist[i++] = a[p2++];
                      }
                  }
                  //如果p1指针还没有走完, 那直接吧剩余元素放大辅助数组中去
                  while (p1<=mid){
                      assist[i++] = a[p1++];
                  }
                  //如果p2指针还没有走完, 那直接吧剩余元素放大辅助数组中去
                  while (p2<=hi){
                      assist[i++] = a[p2++];
                  }
                  //将辅助数组的数据拷贝到原数组
                  for (int j = lo; j <=hi; j++) {
                      a[j]=assist[j];
                  }
              }
          
              /**
               * @param x
               * @param y
               * @return true: x>y
               */
              public static boolean less(Comparable x, Comparable y) {
                  return x.compareTo(y) < 0;
              }
          
              /**
               * 交换数组中x和y的位置
               *
               * @param a
               * @param x
               * @param y
               */
              public static void exchange(Comparable[] a, int x, int y) {
                  Comparable t;
                  t = a[x];
                  a[x] = a[y];
                  a[y] = t;
              }
          }
          

           

      4. 时间复杂度:O(nlogn)
      5. 归并排序的缺点
        1. 需要申请额外的数组空间, 导致空间复杂度上升, 是典型的的以空间换时间的操作
          1. 辅助数组的大小和原数组的大小是一样的
      6. 归并排序和希尔排序的速度是差不多的
版权声明:本文为qq_44756419原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44756419/article/details/106311880