排序算法(一)

发表于   |   更新于 | | 阅读数
字数统计 2.1k 字 | 阅读时长 8 分钟

常见排序算法

冒泡排序

  1. 概念:

    1. 冒泡排序每次操作都会对相邻的两个元素进行比较，看看是否满足大小关系要求；
    2. 不满足则进行位置交换
    3. 一次冒泡确保有一个元素会被移动到正确的位置

  2. 实现:

    1. 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16

      public static void bubbleSearch(int[] nums) {

          int n = nums.length;
          //控制排序次数
          for (int j = 0; j < nums.length; j++) {
              for (int i = 0; i < n; i++) {
                  if (nums[i] > nums[i + 1]) {
                      int temp = nums[i + 1];
                      nums[i + 1] = nums[i];
                      nums[i] = temp;
                  }
              }
          }

      }

    2. 两层循环，外层控制冒泡的次数，内层循环进行数据的比较和移动；

    3. 排序算法对于已经部分有序的数据来说，有一些比较动作是浪费的，因此内层循环可以再进行控制

    4. 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15

      public static void bubbleSearch(int[] nums) {

          int n = nums.length;
          for (int j = 0; j < nums.length; j++) {
              //i < n-i-j ; 每次冒泡之后，下次需要遍历的位置都可以前移，因为最后的数据已经排序完毕
              for (int i = 0; i < n-1-j; i++) {
                  if (nums[i] > nums[i + 1]) {
                      int temp = nums[i + 1];
                      nums[i + 1] = nums[i];
                      nums[i] = temp;
                  }
              }
          }
      }

    5. 这样每次冒泡进行元素比较的操作就可以减少一部分，但是考虑极端情况：完全有序 的n长数组进行排序需要几次?答案是 n 次，因为至少需要进行一次完整的遍历，才能判断是否需要进行元素的移动

    6. 当输入数组有序的情况下，是否能够提前退出循环？

    7. 实现:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      public static void bubbleSearch(int[] nums) {
      	
          int n = nums.length;
          for (int j = 0; j < nums.length; j++) {
             boolean flag = false;//退出标志位
              for (int i = 0; i < n-1-j; i++) {
                  if (nums[i] > nums[i + 1]) {
                      int temp = nums[i + 1];
                      nums[i + 1] = nums[i];
                      nums[i] = temp;
                      flag=true;//表示有数据进行了交换，不能提前退出循环
                  }
              }
              if(!flag){
                  //当一次遍历没有发生任何数据交换，说明输入数组是有序的，无需再进行排序
                  break;
              }
          }
      }
      1. 区别在于通过第i次排序是否发生了数据交换来判断当前输入的有序程度，完全顺序的输入不会产生任何的数据交换，因此可以直接跳出循环

插入排序:

  • 概念:

    1. 插入排序将未排序数组分为已排序区间和未排序区间，默认首位元素作为已排序数组的首位

    2. 每次取未排序数组的第一位，和已排序数组的末尾进行比较，倒序遍历已排序数组

    3. 如果存在未排序数据需要插入的情况，将插入位置后的元素进行整体后移

    4. 完成一次元素后移之后，将待排序元素插入

    5. 先按照顺序思维实现: 标准的线性思维，先实现出来，再尝试优化

    6. 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
      int[] a = {4,5,6,1,3,2};

      public static void insertSorted(int[] a){
          int n = a.length;
          int count=0;
          for(int i =0 ;i<n;i++){
              //假设起始位置0为已排序数组，后续均为需要比较移动的数据,
              for(int j=i+1;j<n-1;j++) {
                  //比较，将较小的数插入到较大数的前面
                  if(a[i]>a[j]) {
                      //较小数
                      int temp = a[j];
                      //将已排序元素后移，这里的已排序指的是 i ~ j-1 位置的元素
                      while(j>i){
                          count++;
                          int te = a[j-1];
                          a[j-1]=a[j];
                          a[j]=te;
                          j--;
                      }
                      //将较小数插入到i位置
                      a[i]=temp;
                      count++;
                  }
              }
          }
      }

    7. 写完之后觉得可以订正一下之前的思路:

      1. 当出现需要移动元素的情况，是将已排序区间的元素进行移动，哪里是已排序？比较的是 i和j 位置，那么已排序区间就是 [i，j-1]
      2. 区分上面这点很重要，因为大小比较并不是排序的重点，如何保持元素有序才是
      3. 在循环开始之前，定义了一个count来统计元素移动多少次之后，数组已经有序，对于数组 a 来说， count = 12 次
      4. 在王峥老师的《算法与数据结构之美》中提到一个有序度的概念：
        1. 有序度是具有有序关系的元素对的个数，例如 a 数组，有序对为 : 4,5;4,6;5,6;三对 ，顺序a数组的满有序度为: 1 +2 +3 +…+n-1 = n*(n-1)/2 ， 即 15；
        2. 由此再联想逆序度的概念：数组中逆序元素对的个数，逆序度 = 12
        3. 所以之前的统计中，当count等于12次的时候已经达到了满有序度，也就是总体数据移动了12次
        4. 得出结论：在给定的数组中，元素需要移动逆序度的次数才能完成排序。

    8. 上面的实现有哪些不足？：

      1. 总共有三层循环，第一层循环控制起始比较的位置；第二层循环控制未排序区间的起始位置；第三层循环进行数组数据的移动；那么是否可以进行优化？

      2. 优化:

      3. 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22

        public static void insertionSort(int[] a) {

            int n=a.length;
            for (int i = 1; i < n; ++i) {
                //未排序元素的第一个
                int temp = a[i];
                int j=i-1;
                for(;j>=0;j--){
                    //已排序区间的最后一个
                    int lower = a[j];
                    //比较
                    if (lower > temp) {
                        a[j+1]=a[j]; 
                    }else{
                        break;
                    }
                }
                a[j+1]=temp;
            }
            System.out.println(1);
        }

      4. 分析思路:

        1. 第一次实现的插入排序思路是十分顺序而简单的：
          1. 一次比较 i 和 1~n-1 位置的元素
          2. 发现需要进行交换的 j 位置元素时，将 i ~ j-1 位置的元素进行后移，空出 i 位置插入 j
          3. 因此使用了三重循环
        2. 优化后的思路是:
          1. 持有未排序元素的首位 ，位置 i ,a[ i ] =temp;
          2. 和已排序元素的末尾进行比较，即 i -1 位置，记为 j ；
          3. 如果 a[ j ] > a[ i ] ，后移 a[ j ]，a[ i ] 和 a[ j ]进行比较 ，直到 a[ i ] > a[ j ] ，说明 a[ i ] 的插入位置是 a[j+1]，a[ j+1 ] =a[ i ] = temp ;
          4. 比较妙的地方在于第 19 行 ： 保证了无论是否发生数据交换，a[ j+1 ] 位置的值都是正确的
          5. 因为我发现自己没有很好地表达出思路，说明理解不够深入，对以上思路进行订正：
            1. 插入排序应该视为将未排序区间的任一数据插入到已排序数组中的行为
            2. 将一个数据插入到数组中需要进行数据的移动，以维持数组空间的连续性
            3. 将未排序数组的数据逐个取出，倒序和已排序数组进行比较，当未排序<已排序，说明需要查找未排序插入的位置，并后移已比较过的数据，空出插入的空间；
            4. 对已排序数据进行后移，再次比较前一个数据和未排序的大小，确定是否需要遍历整个已排序数组

选择排序：

  • 思路：

    1. 在未排序数组区间中查找最小的元素移动到已排序区间的末尾

    2. 然后在剩余的数据范围内重复1的动作

    3. 实现:

    4. 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18

      public static void selectionSorted(int[] a) {
              
          int n = a.length;
          for (int i = 0; i < n - 1; i++) {
              //先假定a[i]是最小的数据
              int mix = a[i];
              for (int j = i + 1; j < n; j++) {
                  //确定最小的元素
                  if (mix > a[j]) {
                      int temp = a[j];
                      a[j] = a[i];
                      a[i] = temp;
                      mix = temp;
                  }
              }
          }
      }

    5. 在选择排序中重要的几点是：

      1. 确定一趟遍历中最小元素的位置
      2. 当最小元素发生变化，要进行数据位置交换

小结

  • 常见的三种排序算法：冒泡，插入，选择；插入排序的实现稍微复杂一点，比较考验思维能力；冒泡和选择都是比较直观

  • 冒泡排序存在可以提前终止的冒泡的条件，当一次冒泡过后，发现所有的相邻元素都已经按照顺序排列好了，就不需要再次冒泡

  • 插入排序的理解重点在于：将问题看作是在已排序数组中插入元素的行为，那将元素在已排序数组中遍历比较，找到位置插入即可