冒泡、插入、选择

冒泡、选择、插入

冒泡排序（Bubble Sort）：

• 思想：比较相邻的元素，如果前一个元素比后一个元素大，就交换它们的位置，重复进行直到整个数组排序完成。
• 稳定排序，在“冒泡”中遇到相等元素不交换
• 算法流程：
  1. 首先，对 $n$ 个元素执行“冒泡”，将数组的最大元素交换至正确位置。
  2. 接下来，对剩余 $n - 1$ 个元素执行“冒泡”，将第二大元素交换至正确位置。
  3. 以此类推，经过 $n - 1$ 轮“冒泡”后，前 $n - 1$ 大的元素都被交换至正确位置。
  4. 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。
• 代码：

  /* 冒泡排序 */ 
  func bubbleSort(nums []int) {
      // 外循环：未排序区间为 [0, i]
      for i := len(nums) - 1; i > 0; i-- {
          // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
          for j := 0; j < i; j++ {
              if nums[j] > nums[j+1] {
                  // 交换 nums[j] 与 nums[j + 1]
                  nums[j], nums[j+1] = nums[j+1], nums[j]
              }
          }
      }
  }
  
  /* 冒泡排序（标志优化）当数组有序时，将不会发生交换，可以直接中断 */
  func bubbleSortWithFlag(nums []int) {
      // 外循环：未排序区间为 [0, i]
      for i := len(nums) - 1; i > 0; i-- {
          flag := false // 初始化标志位
          // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
          for j := 0; j < i; j++ {
              if nums[j] > nums[j+1] {
                  // 交换 nums[j] 与 nums[j + 1]
                  nums[j], nums[j+1] = nums[j+1], nums[j]
                  flag = true // 记录交换元素
              }
          }
          if flag == false { // 此轮“冒泡”未交换任何元素，直接跳出
              break
          }
      }
  }

选择排序（Selection Sort）：

• 思想：每次从未排序的部分中选择最小的元素，放到已排序部分的末尾，重复进行直到整个数组排序完成。
• 不稳定排序
• 算法流程：
  1. 初始状态下，所有元素未排序，即未排序（索引）区间为 $[0, n-1]$ 。
  2. 选取区间 $[0, n-1]$ 中的最小元素，将其与索引 $0$ 处的元素交换。完成后，数组前 1 个元素已排序。
  3. 选取区间 $[1, n-1]$ 中的最小元素，将其与索引 $1$ 处的元素交换。完成后，数组前 2 个元素已排序。
  4. 以此类推。经过 $n - 1$ 轮选择与交换后，数组前 $n - 1$ 个元素已排序。
  5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。
• 代码：

  /* 选择排序 */
  func selectionSort(nums []int) {
      n := len(nums)
      // 外循环：未排序区间为 [i, n-1]
      for i := 0; i < n-1; i++ {
          // 内循环：找到未排序区间内的最小元素
          min := i
          for j := i + 1; j < n; j++ {
              if nums[j] < nums[min] {
                  // 记录最小元素的索引
                  min = j
              }
          }
          // 将该最小元素与未排序区间的首个元素交换
          nums[i], nums[min] = nums[min], nums[i]
  
      }
  }

插入排序（Insertion Sort）：

• 思想：将数组分为已排序和未排序两个部分，每次从未排序部分中选择一个元素插入到已排序部分的正确位置，重复进行直到整个数组排序完成。（参考扑克牌的排序）
• 稳定排序
• 算法流程：
  1. 初始状态下，数组的第 1 个元素已完成排序。
  2. 选取数组的第 2 个元素作为 base ，将其插入到正确位置后，数组的前 2 个元素已排序。
  3. 选取第 3 个元素作为 base ，将其插入到正确位置后，数组的前 3 个元素已排序。
  4. 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序。
• 代码：

  /* 插入排序 */
  func insertionSort(nums []int) {
      // 外循环：已排序区间为 [0, i-1]
      for i := 1; i < len(nums); i++ {
  
          // 内循环：将索引i，值为base 插入到已排序区间 [0, i-1] 中的正确位置
          for j := i - 1; j >= 0 ; j-- {
              if nums[j+1] < nums[j] {                        // 冒泡的逆过程
                  nums[j+1], nums[j] = nums[j], nums[j+1]     // 两两比较交换
              } else {                                        // 一旦发现小值或者等值，则说明位置已经找到，结束内循环。因为等值时不改变位置，所以是稳定排序。
                  break
              }
          }
      }
  }