利用交换数据元素的位置进行排序的方法称为交换排序。常见的交换排序方法有冒泡排序和快速排序。

1. 冒泡排序

1.1 冒泡排序的基本思想

设数组a中存放了n个数据元素，循环进行n-1趟如下的排序过程：第1趟依次比较相邻的两个数据元素a[i]和a[i+1]（0in-2），若a[i]a[i+1]，则交换两个数据元素的位置，否则不交换，这样数值最大的数据元素将被放置在a[n-1]中；第2趟，数据元素个数减1，即数据元素个数为n-1，操作方法和第1趟类似，这样整个n个数据元素集合中数值次大的数据元素将被放置在a[n-2]中；当n-1趟结束后，整个n个数据元素集合中次小的数据元素将被放置在a[1]中，a[0]放置了最小的数据元素。
如下图所示是对于数组序列{9,3,1,4,2,7,8,6,5}的冒泡排序过程。

1.2 冒泡排序代码实现

void BuddleSort() {
    int arr[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for (int k = 0; k < len; ++k) {
        printf("%d ", arr[k]);
    }
}

有时，待排序的数据元素序列已经基本排序，这样实际上并不需要全部执行完外部循环的n-1次循环过程，数据元素就已经全部排序就绪。那么就可以定义一个变量flag充当标记，用于标记本次交换排序过程中是否有交换动作。若本次交换排序过程没有交换东西，即本次交换排序过程后，flag不等于1，则说明数据元素集合已经全部排序，就可以提前结束排序过程。
优化后的代码如下：

void BuddleSort() {
    int arr[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < len; ++i) {
        int flag = 0;//设置标记
        for (int j = 0; j < len - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                flag = 1;//有数据交换修改标记flag的值
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        //当标记变量的值为0时，表明待排序列已经排序，结束排序过程。
        if (flag == 0) {
            break;
        }
    }
    for (int k = 0; k < len; ++k) {
        printf("%d ", arr[k]);
    }
}

1.3、冒泡排序的时间效率分析

冒泡排序算法的最好情况是数据元素集合已经全部排好序，这时循环n-1次，每次循环因为没有交换动作而退出，因此冒泡排序算法最好情况的时间复杂度为；冒泡排序算法的最坏情况是数据元素集合全部逆序存放，这时循环n-1次，比较次数和交换移动次数共计为：

因此冒泡排序最坏情况的时间复杂度为。冒泡排序算法的空间复杂度为。冒泡排序算法是一种稳定的排序方法。

2、快速排序

2.1、快速排序的基本思想

快速排序是一种二叉树结构的交换排序方法。快速排序算法的基本思想，设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个数据元素（通常取a[low]）作为标准，调整数组a中各个元素的位置，使排在标准元素前面元素均小于标准元素，排在标准元素后面元素均大于或等于标准元素。这样一次过程结束后，一方面将标准元素放在未来排好序的数组中该标准元素应在的位置，另一方面将数组中的元素以标准元素为中心分成两个子数组，位于标准元素左边子数组中元素均小于标准元素，位于标准元素右边子数组中的元素均大于或等于标准元素。对于这两个子数组中的元素分别再进行类似的递归快速排序。递归算法的结束条件是lowhigh，即上界下标小于等于下界下标。

2.1、快速排序的代码实现

void QuickSort(int a[], int low, int high) {
    if (low >= high) {
        return;
    }
    int i = low;
    int j = high;
    int temp = a[low];
    while (i < j) {
        //从数组的右端向左边移动，找到大于等于基准数值的元素
        while (i < j && temp <= a[j]) {
            j--;
        }
        if (i < j) {
            a[i] = a[j];
            I++;
        }
        //从数组的左端向右移动，找到小于基准数值的元素
        while (i < j && a[i] < temp) {
            I++;
        }
        if (i < j) {
            a[j] = a[I];
            j--;
        }
    }
    a[i] = temp;
    if (low < i) {//对左边子数组进行递归
        QuickSort(a, low, i - 1);
    }
    if (i < high) {//对右边子数组进行递归
        QuickSort(a, j + 1, high);
    }
}

快速排序算法过程是递归的过程，我们首先看第一次递归调用的执行过程。把a[low]看做是标准元素，标准元素存放在临时变量temp中，把标准元素的定位过程分为两个子过程，在数组的右端扫描定位和数组的左边扫描定位。

1. 在数组的右边扫描定位时，从数组的右端（下标j）开始，比较标准元素和数组右端的元素，若标准元素的值小于或等于数据右端元素的值，则数组右端下标j减1后继续比较；否则a[j]赋值给a[i]并且下标i加1后，转到在数组的左边扫描定位。
2. 在数组的左边扫描定位时，从数组的左端（下标i）开始，比较标准元素的值和数组左端元素的值，若标准元素的值大于数组左端元素的值，则数组左端下标i加1后继续比较；否则a[i]赋值给a[j]并且下标j减1后转到在数组的右端扫描定位。
3. 上述在数组的左端扫描定位和右端扫描定位反复进行，直到数组左端下标i大于或等于数组右端下标j为止。此时把标准元素（即临时存放在变量temp的值）赋值给a[i]。数组的位置a[i]即为标准元素最终应在的位置。这时处于标准元素左边的元素均小于标准元素，处于标准元素右边的元素均大于或等于标准元素。

2.1、快速排序的效率分析

快速排序算法的时间复杂度和各次标准数据元素的值有很大关系。如果每次选取的标准数据元素都能均分两个子数组区间的长度，这样的快速排序过程是一个完全二叉树结构。即每个结点都把当前数组分成两个大小相等的数组结点，n个元素数组的根结点的分解次数就构成一棵完全二叉树。这时分解次数等于完全二叉树的深度。每次快速排序过程无论怎么样划分数组，全部比较次数都接近n-1次，所以最好情况下快速排序算法的时间复杂度为。快速排序最坏的情况是数据元素已全部有序，此时数组根结点的分解次数构成一棵二叉退化树，一棵二叉退化树的深度是n，所以最坏情况下快速排序算法的时间复杂度为。在一般情况下，标准元素值的分布是随机的，数组的分解次数构成一棵二叉树，这样的二叉树的深度接近lbn，所以快速排序算法的平均时间复杂度为。
快速排序算法需要堆栈空间临时保存递归调用参数，堆栈空间的使用个数和递归的次数有关，由于二叉树有可能是单支二叉树，而单支二叉树的深度为n-1，所以最坏情况下快速排序算法的空间复杂度为。