八大排序算法（2）交换排序-冒泡排序 和 快速排序

快速排序（Quick Sort） 和 冒泡排序（Bubble Sort） 都是常见的交换排序算法，它们的核心思想都是通过交换元素来实现排序。但是，它们的工作原理和性能差异非常大。下面我们来详细对比这两种排序算法：

1. 冒泡排序（Bubble Sort）

工作原理：

冒泡排序的基本思想是通过重复遍历数组，在每一轮中将未排序部分的最大元素“冒泡”到数组的末尾。

在每一轮中，比较相邻的元素，如果它们的顺序错误，就交换它们。这样，经过每一轮遍历，当前未排序部分的最大元素会被放到正确的位置。

这个过程持续进行，直到没有元素需要交换为止，数组被排序好。

时间复杂度：

最优时间复杂度：O(n)，当数组已经是有序的时，冒泡排序只需要进行一次遍历就可以完成排序。

最坏时间复杂度：O(n^2)，当数组是逆序的时，每一轮都需要进行大量的交换，导致时间复杂度达到平方级别。

平均时间复杂度：O(n^2)，由于每次都需要比较和交换，尤其是对大规模数据集时，性能较差。

空间复杂度：

空间复杂度：O(1)，冒泡排序是原地排序算法，不需要额外的存储空间。

稳定性：

稳定性：冒泡排序是稳定排序算法，相等的元素不会改变相对顺序。

优缺点：

优点：简单易懂，容易实现。

缺点：效率低，特别是对于大规模数据集时，不适用于大数据排序。

2. 快速排序（Quick Sort）

工作原理：

快速排序是一种分治法的排序算法。其基本思想是：选择一个基准元素（pivot），然后将数组中的元素分成两部分：

左边部分所有元素都小于基准元素

右边部分所有元素都大于基准元素

递归地对左右两部分进行排序，直到数组完全有序。

快速排序的核心是通过分区操作将数组分成两部分，每次递归地进行排序。

时间复杂度：

最优时间复杂度：O(n log n)，每次分区都能均匀地将数组分成两半，递归深度为 log n，每次分区操作的时间为 O(n)。

最坏时间复杂度：O(n^2)，当基准元素选得不好（如每次选到最大或最小元素）时，划分不均匀，导致递归的深度接近 n，此时性能与冒泡排序类似。

平均时间复杂度：O(n log n)，通常情况下，快速排序的时间复杂度非常好，适用于大规模数据。

空间复杂度：

空间复杂度：O(log n)，由于递归调用，最多需要 log n 的栈空间。

稳定性：

稳定性：快速排序通常不是稳定排序。因为相等的元素可能会被交换位置，导致它们的相对顺序发生变化。

优缺点：

优点：平均时间复杂度 O(n log n)，非常高效，特别适用于大规模数据排序。

缺点：最坏情况下时间复杂度为 O(n^2)，而且不是稳定的排序。

快速排序与冒泡排序的对比

特性	冒泡排序	快速排序
时间复杂度	最优：O(n)，最坏：O(n^2)，平均：O(n^2)	最优：O(n log n)，最坏：O(n^2)，平均：O(n log n)
空间复杂度	O(1)	O(log n)
稳定性	稳定	不稳定
实现难度	简单，易于理解	相对复杂，需要递归和分区操作
适用场景	小规模数据，或者数据几乎已经有序时	大规模数据，性能优于冒泡排序
优缺点	优：实现简单，缺：效率低	优：高效，缺：可能会退化为 O(n^2)，不稳定