『算法拾遗』重学主流排序算法

衡量排序算法的好坏

时间复杂度

• 包含最好情况、最坏情况和平均情况
• 数据有序度不同的影响

空间复杂度

• 是否是原地排序

稳定性

• 排序后，相同元素之间的顺序是否会改变

O( n^2 )

冒泡排序（Bubble Sort）

依次比较相邻的元素，如果顺序错误，则交换它们。每轮排序将最大（或最小）的元素“冒泡”到正确的位置

简单易懂，但效率较低，不适用于大规模数据排序

• 过程

  1. 初始化待排序数组，设为 arr ，数组长度为 n
  2. 外层循环：重复 n-1 次（即 i 从 0 到 n-2 ） 思考：为什么外层是n-1次
     1. 内层循环：重复 n-i-1 次（即 j 从 0 到 n-i-2 ） 思考：为什么内层是n-i-1次
        1. 比较 arr[j] 和 arr[j+1] ，如果 arr[j] 大于 arr[j+1] ，执行下一步，否则继续内层循环
        2. 交换 arr[j] 和 arr[j+1] 的位置
     2. 判断是否在本轮内层循环中进行了交换操作：
        • 如果没有进行交换，说明数组已经有序，提前结束排序
  3. 冒泡排序结束，数组 arr 已经按升序排列

• 性质

  1. 在排序没有完成之前，小的数会逐步往前移，大的数会逐步往后移动
  2. 每轮排序至少会让一个最大元素放置在正确位置，重复 $n-1$ 次，就完成了 $n$ 个元素的排序
  3. 是稳定的排序算法
  4. 空间复杂度：冒泡排序的空间复杂度为 $O(1)$，它在原地进行排序，不需要额外的内存空间。
  5. 最优情况：冒泡排序的最优情况是输入数组已经有序。在这种情况下，只需要进行一次遍历，没有元素交换，时间复杂度为 $O(n)$
  6. 最坏情况：冒泡排序的最坏情况是输入数组完全逆序。在这种情况下，需要进行 $n-1$ 轮遍历，每轮遍历需要进行元素比较和交换，时间复杂度为 $O(n^2)$
  7. 平均情况：冒泡排序的平均时间复杂度为 $O(n^2)$ 。因为每一对元素在排序过程中都有可能发生交换，所以平均时间复杂度较高

• 代码

  func bubbleSort(arr []int) {
      n := len(arr)
      for i := 0; i < n-1; i++ { // 一共要排序 n-1 轮（因为每 1 轮至少能让 1 个元素放在正确的位置）
          // 标记是否进行了交换，如果在某轮遍历中没有发生交换，则说明数组已经有序，可以提前结束排序。
          swapped := false
          for j := 0; j < n-i-1; j++ { // 每轮比较 n-i-1 次（因为前面 i 轮已经让 i 个元素有序了）
              // 比较相邻的元素，如果顺序错误则交换它们
              if arr[j] > arr[j+1] {
                  arr[j], arr[j+1] = arr[j+1], arr[j]
                  swapped = true
              }
          }
          // 如果在某轮遍历中没有发生交换，则说明数组已经有序，可以提前结束排序。
          if !swapped {
              break
          }
      }
  }

• 冒泡排序的例子（GPT）

  好的，让我们来看一个冒泡排序的例子。假设我们要对一个整数数组进行升序排序，下面是冒泡排序的步骤：

  初始数组：[5, 2, 9, 1, 5, 6]

  第一轮冒泡：

  • 比较 5 和 2：需要交换位置，数组变为 [2, 5, 9, 1, 5, 6]
  • 比较 5 和 9：位置正确，不需要交换，数组保持不变 [2, 5, 9, 1, 5, 6]
  • 比较 9 和 1：需要交换位置，数组变为 [2, 5, 1, 9, 5, 6]
  • 比较 9 和 5：需要交换位置，数组变为 [2, 5, 1, 5, 9, 6]
  • 比较 9 和 6：需要交换位置，数组变为 [2, 5, 1, 5, 6, 9]

  第一轮冒泡结束后，最大的元素 9 已经被“冒泡”到正确的位置末尾。

  第二轮冒泡：

  • 比较 2 和 5：位置正确，不需要交换，数组保持不变 [2, 5, 1, 5, 6, 9]
  • 比较 5 和 1：需要交换位置，数组变为 [2, 1, 5, 5, 6, 9]
  • 比较 5 和 5：位置正确，不需要交换，数组保持不变 [2, 1, 5, 5, 6, 9]
  • 比较 5 和 6：位置正确，不需要交换，数组保持不变 [2, 1, 5, 5, 6, 9]

  第二轮冒泡结束后，第二大的元素 5 也已经被“冒泡”到正确的位置。

  第三轮冒泡：

  • 比较 2 和 1：需要交换位置，数组变为 [1, 2, 5, 5, 6, 9]
  • 比较 2 和 5：位置正确，不需要交换，数组保持不变 [1, 2, 5, 5, 6, 9]
  • 比较 5 和 5：位置正确，不需要交换，数组保持不变 [1, 2, 5, 5, 6, 9]

  第三轮冒泡结束后，第三大的元素 2 也已经被“冒泡”到正确的位置。

  第四轮冒泡：

  • 比较 1 和 2：位置正确，不需要交换，数组保持不变 [1, 2, 5, 5, 6, 9]
  • 比较 2 和 5：位置正确，不需要交换，数组保持不变 [1, 2, 5, 5, 6, 9]

  第四轮冒泡结束后，第四大的元素 1 也已经被“冒泡”到正确的位置。

  最后一轮冒泡：

  • 比较 1 和 2：位置正确，不需要交换，数组保持不变 [1, 2, 5, 5, 6, 9]

  最后一轮冒泡结束后，第五大的元素 1 也已经被“冒泡”到正确的位置。

  现在数组已经完全有序：[1, 2, 5, 5, 6, 9]。整个冒泡排序过程完成。

  冒泡排序的基本思想是通过相邻元素的比较和交换来逐步“冒泡”最大元素至正确位置。这个过程持续执行直至所有元素都排好序。请注意，冒泡排序可能需要多次遍历数组来确保所有元素都在正确的位置。虽然冒泡排序简单易懂，但它的效率较低，不适用于大规模数据的排序。

• 可能会问的问题（GPT）

  在面试中，关于冒泡排序，面试官可能会问您以下几类问题：

  1. 冒泡排序的原理和思想是什么？

     • 回答要点：冒泡排序是一种简单的排序算法，它通过相邻元素的比较和交换来逐步“冒泡”最大元素至正确的位置。它的核心思想是重复遍历数组，每次遍历将当前最大元素放到未排序部分的末尾。

  2. 冒泡排序的时间复杂度是多少？

     • 回答要点：冒泡排序的平均时间复杂度为O(n^2)，最好情况下（数组已经有序）为O(n)，最坏情况下（数组完全逆序）为O(n^2)。平均情况下，需要进行n-1轮外层循环，每轮循环需要比较n-i-1次，共进行(n-1) + (n-2) + … + 1 = n*(n-1)/2次比较。

  3. 冒泡排序是稳定排序算法吗？

     • 回答要点：是的，冒泡排序是一种稳定的排序算法。在冒泡排序的过程中，只有在相邻元素需要交换时才改变相等元素的顺序，所以相等元素的相对位置在排序前后保持不变。

  4. 如何优化冒泡排序的时间复杂度？

     • 回答要点：可以使用一个标志位来判断在某一轮外层循环中是否进行了交换操作，如果没有交换，说明数组已经有序，可以提前结束排序，从而优化最好情况下的时间复杂度为O(n)。

  5. 冒泡排序和其他排序算法的比较？

     • 回答要点：冒泡排序是一种简单易懂的排序算法，但其时间复杂度较高，不适合大规模数据的排序。相比之下，快速排序、归并排序和堆排序等排序算法在平均情况下有更高效的时间复杂度，并且更常用于实际应用。

  6. 你能实现冒泡排序的代码吗？

     • 回答要点：您需要在面试中展示您对冒泡排序的理解，然后根据编程语言要求编写冒泡排序的代码实现。

  在面试过程中，除了理解冒泡排序的原理和性质外，您还应该能够清晰地表达答案，展示您对算法的理解和编程能力。如果需要，可以使用示例或画图来帮助说明。同时，与面试官保持良好的沟通，如果有任何不清楚的地方，随时请教面试官。

插入排序（Insertion Sort）

分区左右分为已排序和未排序两个部分，每次选取一个元素插入到已排序的部分中

适用于小型数据集和基本有序的数据，效率较冒泡排序稍高。思考：时间复杂度相同，为什么说插入比冒泡效率高

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1

        // 将 arr[0..i-1] 中大于 key 的元素向后移动一格
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }
        arr[j+1] = key
    }
}

性质

• 移动的次数等于逆序度
• 是原地排序
• 是稳定的排序算法
• 最好时间复杂度（完全有序）： $O(n)$
• 最坏时间复杂度（完全倒序）： $O(n^2)$
• 平均时间复杂度：$O(n^2)$

选择排序（Selection Sort）

分区同样左右分为已排序和未排序两个部分，每次扫描未排序部分，找到最大（小）值，交换附加到已排序部分的末尾

一般不会使用

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        // 交换最小值和当前值
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

性质

• 是原地排序算法
• 最好、最坏、平均都是 $O(n^2)$
• 不稳定的排序算法

O( n*logn )

归并排序（Merge Sort）

先将左右两边分别排序，再合并到一起（自底向上）

递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    mid := len(nums) / 2
    return merge(mergeSort(nums[:mid]), mergeSort(nums[mid:]))
}

func merge(left, right []int) []int {
    res := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            res = append(res, left[i])
            i++
        } else {
            res = append(res, right[j])
            j++
        }
    }
    for ; i < len(left); i++ {
        res = append(res, left[i])
    }
    for ; j < len(right); j++ {
        res = append(res, right[j])
    }
    return res
}

性质

• 是稳定的排序算法

• 时间复杂度永远是 O(nlogn)

• 致命的弱点是需要 O(n) 的临时空间

• 可以统计逆序对

  在合并的时候如果 left[i] > right[j] ，那么 left 之中包括 left[i] 在内后面的元素都比 right[j] 大，都能构成逆序对，所以可以 ans += len(left) - i

快速排序（Quicksort）

选择一个基准分成左中右三部分（通常是中间或者末尾元素），然后使左部分都比基准小，右部分都比基准大（自顶向下）

递推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1… r)

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    pivot := arr[len(arr)-1]
    var left, right []int

    for _, num := range arr[:len(arr)-1] {
        if num <= pivot {
            left = append(left, num)
        } else {
            right = append(right, num)
        }
    }

    sortedLeft := quickSort(left)
    sortedRight := quickSort(right)

    return append(append(sortedLeft, pivot), sortedRight...)
}

你可以看见这不是原地排序的，优化后可以做到原地排序（类似选择排序，使用交换法在末尾放入元素）

// partition 函数负责将数组 nums 的子数组 [low, high] 分区。
// 函数选择一个枢轴元素，然后重新排列子数组，
// 使得所有小于枢轴的元素位于其左侧，
// 所有大于枢轴的元素位于其右侧。
func partition(nums []int, low, high int) int {
    pivot := nums[low] // 基准随便选，这里选首元素
    i, j := low, high

    for i < j {
        // 从右往左找到一个小于枢轴的元素
        for i < j && nums[j] >= pivot {
            j--
        }
        nums[i] = nums[j]
        // 从左往右找到一个大于枢轴的元素
        for i < j && nums[i] <= pivot {
            i++
        }
        nums[j] = nums[i]
    }

    // 将枢轴元素放回正确的位置（i 和 j 相遇的地方）
    nums[i] = pivot
    return i
}

// quickSort 函数负责对数组 nums 的子数组 [low, high] 进行快速排序。
func quickSort(nums []int, low, high int) {
    if low < high {
        // 对数组进行分区，并获得枢轴元素的索引
        pivotIndex := partition(nums, low, high)
        // 对左右两部分进行递归排序
        quickSort(nums, low, pivotIndex-1)
        quickSort(nums, pivotIndex+1, high)
    }
}

还有一种短小精悍的写法，我愿称之为最强模板

func quickSort(nums []int) {
    n := len(nums)
    if n <= 1 {
        return
    }

    // 取消注释这两行可增强性能（随机选择一个索引作为基准值）
    // pivotIndex := rand.Intn(n)
    // nums[0], nums[pivotIndex] = nums[pivotIndex], nums[0]

    pivot := nums[0]
    i, j := -1, n

    for i < j {
        for i++; nums[i] < pivot; i++ {}
        for j--; nums[j] > pivot; j-- {}
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    quickSort(nums[:j+1])
    quickSort(nums[j+1:])
}

衍生的 Kth 问题 模板，使用快排改造的 quickSelect 解法能达到 $O(n)$ 的复杂度

func findKthLargest(nums []int, k int) int {
	n := len(nums)
	return quickSelect(nums, n-k) // 第k个最大 -> 第n-k大
}
func quickSelect(nums []int, k int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}

	p := nums[0]
	i, j := -1, n

	for i < j {
		for i++; nums[i] < p; i++ {}
		for j--; nums[j] > p; j-- {}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if k <= j {
		return quickSelect(nums[:j+1], k)
	} else {
		return quickSelect(nums[j+1:], k-j-1)
	}
}

但是这个模板的快排并不是真正的快排，它不能满足一个关键性质：使左部分都比基准小，右部分都比基准大

但是它又能跑，我只能说非常的神奇 😋

性质

堆排序

O( n )

计数排序

基数排序

桶排序