排序算法

排序算法的介绍

  1. 排序算法是将一组数据，依指定的顺序进行排列的过程

排序的分类

  1. 内部排序

    指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。

  2. 外部排序法

    数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

算法的时间复杂度

  1. 时间频度：一个算法中的语句执行次数称为时间频度T(n)
  2. 常见的时间复杂度
    1. 常数阶O(1)
    2. 对数阶O(log2n)
    3. 线性阶O(n)
    4. 线性对数阶O(nlog2n)
    5. 平方阶O(n^2)
    6. 立方阶O(n^3)
    7. K次方阶O(n^k)
    8. 指数阶O(2^n)

冒泡排序

  1. 基本介绍

    通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，值较大的元素逐渐从前移向后部。

  2. 冒泡排序规则

    1. 一共进行数组大小-1次大的循环
    2. 每一趟循环的次数在逐渐减少
    3. 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序，这个就是优化。

  3. 代码实现

    public static void bubbleSort(int[] arr) {
                boolean flag = false;//标识变量，表示是否进行交换
                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]) {
                            flag = true;
                            int a = arr[j + 1];
                            arr[j + 1] = arr[j];
                            arr[j] = a;
                        }
                    }
                    if (flag != true) {//说明一次都没有交换
                        break;
                    } else {
                        flag = false; //重置flag ,进行下次判断
                    }
                }
                for (int i = 0; i < arr.length; i++) {
                    System.out.print(arr[i] + " ");
                }
            }

  4. 冒泡排序的时间复杂度是O(n^2)

选择排序

  1. 基本介绍

    就是遍历整个数组找到数组当中最小的值并与arr[0] 交换，接着，从arr[1]-arr[n]开始遍历数组，再次找到最小值并和arr[1]交换

  2. 思路说明

    1. 选择排序一共有数组大小-1轮排序

    2. 每一轮排序，又是一个循环

      1. 先假定当前这个数就是最小数
      2. 然后和后面的每个数进行比较，如果发现有比这个数更小的数，就重新确定这个最小数，并得到下标
      3. 当遍历到数组的最后时，就得到本轮最小数和小标
      4. 进行交换

    3. 代码实现

    //选择排序
      public  static  void selectort(int[] arr){
          for (int i = 0; i <arr.length-1; i++) {
              int min = arr[i];
              for (int j = i+1; j < arr.length; j++) {
                  if (arr[i] > arr[j]) {
                      min =arr[j]; //重置最小值
                      arr[j] =arr[i];
                      arr[i] =min;
                  }
              }
          }
          for (int i = 0; i <arr.length ; i++) {
              System.out.println(arr[i]+" ");
          }
              }
    1. 选择排序的时间复杂度n(n^2)

插入排序

  1. 基本介绍

    把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将他插入到有序表中的适当位置，使之成为新的有序表。

  2. 代码实现

    public  static void insertSort(int arr[]){
           for (int i = 1; i <arr.length ; i++) {
               //定义待插入的数
               int insertVal = arr[i];
               int insertIndex = i-1;
       
               while (insertIndex >=0 && insertVal < arr[insertIndex]){
                   arr[insertIndex +1] = arr[insertIndex];
                   insertIndex--;
               }
               arr[insertIndex +1] =insertVal;
           }
           System.out.println(Arrays.toString(arr));
       }