本文共 1112 字，大约阅读时间需要 3 分钟。

在之前两篇文章中，我们学习了插入排序和选择排序，，，这篇文章，我们来了解一下交换排序。

常用的交换排序有冒泡排序和快速排序，主要思想就是交换。

1.冒泡排序

基本思想：每相邻两个数比较，若大小与要排序顺序不同，则交换。

将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素（ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；） 对序列当中剩下的n-1个元素再次执行以上步骤。

时间复杂度：O(N^2)

空间复杂度：O(1)

void BubbleSort(int a[],int n){    for (int i = 0; i < n; i++)    {        for (int j = 0; j < n - i - 1; j++)        {            if (a[j]>a[j + 1])                swap(a[j], a[j + 1]);        }    }}

2.快速排序

基本思想：挖坑填数+分治法

从序列当中选择一个基准数 在这里我们选择序列当中第一个数最为基准数 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧 重复步骤1.2，直到所有子集当中只有一个元素为止。

时间复杂度：O(Nlog2N)

空间复杂度：O(N) N为递归压栈次数

void QuickSort(int a[], int l, int r){    if (l< r)    {        int i = l, j = r, x = a[l];        while (i < j)        {            while (i < j && a[j] >= x) // 从右向左找第一个小于x的数                j--;            if (i < j)                a[i++] = a[j];            while (i < j && a[i]< x) // 从左向右找第一个大于等于x的数                i++;            if (i < j)                a[j--] = a[i];        }        a[i] = x;        QuickSort(a, l, i - 1); // 递归调用        QuickSort(a, i + 1, r);    }}

对快速排序来说，两个指针分别查找相较于基准值大或者小的，所以相同元素的相对位置可能会发生改变，即快排是不稳定的。