交换排序

交换排序是一种通过交换元素位置来实现排序的算法。它主要包括两种常见的算法：冒泡排序和快速排序。

### 冒泡排序

冒泡排序的基本思想是比较相邻的元素，如果第一个比第二个大，就交换它们两个。这个过程会重复进行，直到整个序列变得有序。

```pythondef bubble_sort（arr）: n = len（arr） for i in range（n）: for j in range（0, n-i-1）: if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr[1:] # 返回排序后的数组，去掉最后一个元素```

冒泡排序的时间复杂度为O（n^2），空间复杂度为O（1）。

### 快速排序

快速排序是一种分治算法，通过选择一个基准元素，将数组分为两部分，使得左边的元素都小于基准，右边的元素都大于基准，然后递归地对这两部分进行排序。

```pythondef quick_sort（arr）: if len（arr） <= 1: return arr pivot = arr[len（arr） // 2] left = [x for x in arr if x pivot] return quick_sort（left） + middle + quick_sort（right）```

快速排序的平均时间复杂度为O（n log n），空间复杂度为O（log n）。

交换排序通常用于小规模数据的排序，而快速排序在实际应用中通常有更好的性能表现。

其他小伙伴的相似问题：

交换排序的优化方法有哪些？

冒泡排序在什么情况下适用？

快速排序的基准元素如何选择？