博客

title: 2022-06-28-冒泡排序&选择排序

date: 2022-06-28 23:19:00

tag: 算法

我的最新博客地址

2022-06-28-冒泡排序&选择排序

1. 冒泡排序

1.1 思想

• 冒泡排序的排序思想：

从小到大：假定第一个数是最小值，将当前这个数依次和剩下的值进行比较，若遇到比当前这个值小的，就交换位置。

• 冒泡排序代码

  package com.leeue.learn.demo;
  
  /**
   * 冒泡排序
   *
   * @Date 2022/6/28 22:18
   * @Author mac
   */
  public class BubbleSort {
  
      public static void main(String[] args) {
  
          int[] sortList = {1, 3, 4, 2, 9, 1, 34, 5, 3, 7, 0, 3, 5, 9, 90, 32, 4, 5};
  
          sort(sortList);
      }
    
      public static void sort(int[] nums) {
  
          //1. 第一层 for 循环控制需要比较的次数，最后一次不用比较
          for (int i = 0; i < nums.length - 1; i++) {
              
              for (int j = i + 1; j < nums.length; j++) {
                  if (nums[i] > nums[j]) {
                      int temp = nums[i];
                      nums[i] = nums[j];
                      nums[j] = temp;
                  }
              }
          }
  
          for (int i = 0; i < nums.length; i++) {
              System.out.printf("" + nums[i] + " ");
          }
      }
  }
  
  

• 算法复杂度

  算法复杂度为 O(n2)

• 注意事项

  1. 第一层 for 循环是控制比较的次数，最后一次不用比较，前面都排序好了。最后一次也就不用再比较排序了。
  2. 假定第一个数是最小，第二层 for 循环从 最小的前面一个值开始进行比较

2.选择排序

2.1 思想

默认第一个数的下标是最小的。若第一个数的下标跟其他数比较，遇到了比其还小的数字，就记录最小下标，拿这个下标的值跟其他数比较

2.2 代码

public class SelectSort {

    public static void main(String[] args) {

        int[] sortList = {1, 3, 21, 91, 11, 34, 5, 7, 0, 51, 9, 90, 32, 43, 51};

        selectSort(sortList);
    }
  
    public static void selectSort(int[] nums) {
        for (int i = 0; i < nums.length-1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[minIndex] > nums[j]) {
                    minIndex = j;
                }
            }

            if (i != minIndex) {
                int temp = nums[minIndex];
                nums[minIndex] = nums[i];
                nums[i] = temp;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            System.out.printf("" + nums[i] + " ");
        }
    }
}

注意点

1. 选择排序是一个不稳定的排序算法，有时候遇到比较规律的数，交换就会少很多。
2. 特点是
   
记录下标最小值

3. 第一层 for 循环也是次数，第二层 for 循环是跟
   
i + 1

   个数进行比较