排序算法

• 定义：
  • 排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。
  • 通过排序算法得到有序数据，通常能够被更高效地查找、分析和处理。

排序算法评价维度：

维度	说明
运行效率	时间复杂度尽量低、操作尽量少
就地性	在原数组上直接操作实现排序，无须借助额外的辅助数组
稳定性	排序后`相等元素在数组中的相对顺序不发生改变
自适应性	自适应排序的时间复杂度会受输入数据的影响（最佳时间复杂度、最差时间复杂度、平均时间复杂度并不完全相等）
是否基于比较	基于比较的排序依赖比较运算符（$<=>$）来判断元素的相对顺序从而进行排序，理论最优时间复杂度为 $O(nlogn)$。 非比较排序不使用比较运算符，时间复杂度可达 $O(n)$ ，但其通用性相对较差。

计数、桶、基数

桶排序（Bucket Sort）：

• 思想：它通过设置一些具有有限数量、大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并

• 稳定排序、非原地排序，需要借助k个桶和n个元素的数组

• 非比较排序算法

• 算法流程：条件 一个长度为 $n$ 的数组，其元素是范围 $[0, 1)$ 内的浮点数

  1. 初始化 $k$ 个桶，将 $n$ 个元素分配到 $k$ 个桶中。
  2. 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。
  3. 按照桶从小到大的顺序合并结果。

• 桶排序的优化：

  • 将元素均匀分配到各个桶中，时间复杂度趋近于$O(n)$。可以借助值的概率分布。

• 图解：

• 代码：

  /* 桶排序 */
  func bucketSort(nums []float64) {
      // 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
      k := len(nums) / 2
      buckets := make([][]float64, k)
      for i := 0; i < k; i++ {
          buckets[i] = make([]float64, 0)
      }
      // 1. 将数组元素分配到各个桶中
      for _, num := range nums {
          // 输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
          i := int(num * float64(k))
          // 将 num 添加进桶 i
          buckets[i] = append(buckets[i], num)
      }
      // 2. 对各个桶执行排序
      for i := 0; i < k; i++ {
          // 使用内置切片排序函数，也可以替换成其他排序算法
          sort.Float64s(buckets[i])
      }
      // 3. 遍历桶合并结果
      i := 0
      for _, bucket := range buckets {
          for _, num := range bucket {
              nums[i] = num
              i++
          }
      }
  }

冒泡、选择、插入

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