冒泡、选择、插入

冒泡排序（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
          }
      }
  }