数据结构（C语言篇）：（十八）交换排序

_OP_CHEN

发布于 2026-01-14 09:39:29

650

文章被收录于专栏：C++C++

前言

交换排序是一类经典的排序算法，其核心思想是通过不断比较和交换元素的位置，将数据序列按照特定顺序重新排列。这类算法以其直观的逻辑和易于理解的实现方式，在计算机科学的基础教学中占据重要地位。常见的交换排序算法包括冒泡排序和快速排序，它们虽然效率差异显著，但均体现了分治与迭代的思想。随着数据规模的扩大和实际应用场景的多样化，交换排序的优化与改进持续推动着算法效率的提升。本文将从基础原理出发，逐步探讨不同交换排序的实现细节、性能分析及适用场景。下面就让我们正式开始吧！

一、交换排序的基本思想

交换排序的基本思想是通过两两比较待排序元素的关键字，若发现两个元素的相对次序不符合要求（即逆序），则交换它们的位置，直到所有元素都满足排序规则（升序或降序）为止。

交换排序的特点是：将键值较大的记录向记录向序列的尾部移动，键值较小的记录向序列的前部移动。其核心逻辑可概括为：“比较→判断逆序→交换→重复”，通过逐步消除元素间的逆序对，最终实现整个序列的有序排列。

二、冒泡排序

冒泡排序是一种最基础的交换排序。之所以称之为冒泡排序，是因为每一个元素都可以像小气泡一样，根据自身的大小一点一点地向数组的一侧移动。

2.1 冒泡排序的原理

冒泡排序的原理其实是非常直观的：

算法重复地走访要排序的数组，一次比较两个相邻的元素；
如果它们的顺序错误（比如在升序排序中，前一个比后一个大），就把它们交换过来；
重复这个过程，直到没有再需要交换的元素为止，这意味着数组已经排序完成。

2.2 冒泡排序的实现逻辑

1. 外层循环：控制需要进行多少轮比较，对于有n个元素的数组，需要进行n-1轮比较。

2. 内层循环：负责每一轮中的相邻元素的比较和交换：

每完成一轮，最大的元素会 "浮" 到数组的末尾；
因此每轮比较的次数会递减（n-i-1 次）。

3. 交换操作：当发现相邻元素顺序错误时，通过临时变量实现两个元素的交换。

代码实现如下：

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    // 外层循环控制需要进行多少轮比较
    for (int i = 0; i < n - 1; i++) {
        // 内层循环控制每轮比较的次数
        // 每轮结束后，最大的元素已经"浮"到了末尾，所以下一轮可以少比较一次
        for (int j = 0; j < n - i - 1; j++) {
            // 如果当前元素大于下一个元素，则交换它们
            if (arr[j] > arr[j + 1]) {
                // 交换操作
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2.3 冒泡排序的时间复杂度

最坏情况：当数组完全逆序时，需要进行最多的比较和交换：
- 比较次数：
$(n-1) + (n-2) + ... + 1 = n (n-1)/2 \approx n^{2}/2$
(n-1) + (n-2) + ... + 1 = n (n-1)/2 \approx n^{2}/2
；
- 交换次数：与比较次数相同（每次比较都需要交换）；
- 时间复杂度：
$O (n^{2})$
O (n^{2})
。
最好情况：当数组已经有序时：
- 如果进行优化（加入标志位检测是否发生交换），只需进行 n-1 次比较，0 次交换；
- 优化后的时间复杂度：
O (n)
；
- 未优化的时间复杂度仍为
$O (n^{2})$
O (n^{2})
。
平均情况：时间复杂度为

。

三、快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按找该排序码将待排序集合分割成两个子序列，左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值，然后最左右子序列重复该过程，直到所有的元素都排列在相应的位置上。

关于快速排序的实现，在这里我给出四个版本供大家参考，它们分别是：Hoare版本、挖坑法版本、lomuto前后指针法版本和非递归版本。

3.1 Hoare版本（左右指针法）

3.1.1 算法思路

（1）创建左右指针，确定基准值；

（2）从右向左找出比基准值更小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环。

这种方法交换次数较少，是最经典的快速排序实现。

在这我给出代码如下：

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 1. Hoare版本（左右指针法）
int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选择最左元素作为基准
    int i = low;
    int j = high;
    
    while (i < j) {
        // 从右向左找小于基准的元素
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        // 从左向右找大于基准的元素
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        // 交换找到的两个元素
        if (i < j) {
            swap(&arr[i], &arr[j]);
        }
    }
    // 将基准元素放到最终位置
    swap(&arr[low], &arr[i]);
    return i;  // 返回基准元素的位置
}

void hoareQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = hoarePartition(arr, low, high);
        hoareQuickSort(arr, low, pivotPos - 1);  // 递归排序左子数组
        hoareQuickSort(arr, pivotPos + 1, high); // 递归排序右子数组
    }
}

3.1.2 问题分析

问题1：为什么跳出循环后right位置的值⼀定不⼤于key？

当 left > right 时，即 right 走到 left 的左侧，而 left 扫描过的数据均不大于 key，因此 right 此时指向的数据一定不大于 key。我们可以画图分析讨论：

问题2：为什么left 和 right指定的数据和key值相等时也要交换？

相等的值参与交换确实会有一些额外的消耗。实际上还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。同样我们也可以画图分析：

3.2 挖坑法

3.2.1 算法思路

创建左右指针。首先从右向左找出比基准值小的数据，找到后就立即放入左边的坑中，当前位置变为新的“坑”，然后从左向右找出比基准值大的数据，找到之后立即放入右边的坑中，当前的位置变为新的“坑”，结束循环之后将最开始存储的分界值放入当前的“坑”中，返回当前的“坑”下标（即分界值下标）。如下图所示：

完整代码实现如下：

// 2. 挖坑法
int holePartition(int arr[], int low, int high) {
    int pivot = arr[low];  // 选择最左元素作为基准，形成第一个"坑"
    int i = low;
    int j = high;
    
    while (i < j) {
        // 从右向左找小于基准的元素，填到左边的坑
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];  // 将找到的元素填入坑中，形成新坑
        
        // 从左向右找大于基准的元素，填到右边的坑
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];  // 将找到的元素填入坑中，形成新坑
    }
    arr[i] = pivot;  // 将基准元素填入最后一个坑
    return i;        // 返回基准元素的位置
}

void holeQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = holePartition(arr, low, high);
        holeQuickSort(arr, low, pivotPos - 1);
        holeQuickSort(arr, pivotPos + 1, high);
    }
}

3.3 Lomuto前后指针法

3.3.1 算法思路

这种算法的原理在于维护一个小于基准元素的区域边界。首先选择最右边的元素作为基准，接着遍历数组，将小于基准的元素交换到左侧区域。在遍历结束之后，将基准元素放到左侧区域的右侧。

总体而言这种算法实现简单，代码简洁，但交换次数可能较多，消耗时间较多。

完整代码实现如下：

// 3. Lomuto前后指针法
int lomutoPartition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最右元素作为基准
    int i = low - 1;        // i表示小于基准区域的边界
    
    // j遍历数组，将小于基准的元素放到左侧区域
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;  // 扩展小于基准的区域
            swap(&arr[i], &arr[j]);
        }
    }
    // 将基准元素放到最终位置
    swap(&arr[i + 1], &arr[high]);
    return i + 1;  // 返回基准元素的位置
}

void lomutoQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotPos = lomutoPartition(arr, low, high);
        lomutoQuickSort(arr, low, pivotPos - 1);
        lomutoQuickSort(arr, pivotPos + 1, high);
    }
}

3.4 非递归版本

3.4.1 算法思路

这种算法的核心原理在于使用栈模拟递归的过程，存储子数组的边界信息。

首先将初始数组边界入栈，当栈不为空的时候，弹出边界并进行分区，再将分区之后的子数组边界入栈，这样重复直到栈为空为止。

非递归版本能够避免递归调用的栈溢出问题，比较适合处理大规模数据。

完整代码实现如下所示：

// 4. 非递归版本（使用栈模拟递归）
void nonRecursiveQuickSort(int arr[], int low, int high) {
    if (low >= high) return;
    
    // 创建栈用于存储子数组的边界
    int* stack = (int*)malloc(sizeof(int) * (high - low + 1));
    int top = -1;
    
    // 入栈初始边界
    stack[++top] = low;
    stack[++top] = high;
    
    // 栈不为空时处理
    while (top >= 0) {
        // 出栈获取当前子数组的边界
        high = stack[top--];
        low = stack[top--];
        
        // 分区操作
        int pivotPos = lomutoPartition(arr, low, high);
        
        // 左子数组入栈
        if (pivotPos - 1 > low) {
            stack[++top] = low;
            stack[++top] = pivotPos - 1;
        }
        
        // 右子数组入栈
        if (pivotPos +1 < high) {
            stack[++top] = pivotPos + 1;
            stack[++top] = high;
        }
    }
    free(stack);
}

3.5 四种方法时间性能比较

为了让大家更加直观清晰地观察到四种方法在时间维度的性能差异，博主在这又专门写了一段代码，分别输出四种方法的时间消耗结果，如下所示：

// 生成随机数组
void generateRandomArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        arr[i] = rand() % 100000;  // 生成0-99999的随机数
    }
}

// 打印数组（仅用于小规模测试）
void printArray(int arr[], int size) {
    if (size > 20) {  // 数组太大时不打印
        return;
    }
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 计算并返回排序所用的时间（毫秒）
double calculateSortTime(void (*sortFunc)(int[], int, int), int arr[], int size) {
    clock_t start, end;
    double cpu_time_used;
    
    start = clock();
    sortFunc(arr, 0, size - 1);
    end = clock();
    
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC * 1000;  // 转换为毫秒
    return cpu_time_used;
}

int main() {
    srand(time(NULL));  // 设置随机数种子
    
    // 可以修改数组大小来测试不同规模数据的排序时间
    const int size = 100000;  // 10万个元素
    int* originalArray = (int*)malloc(sizeof(int) * size);
    int* testArray = (int*)malloc(sizeof(int) * size);
    
    // 生成随机数组
    generateRandomArray(originalArray, size);
    printf("数组大小: %d个元素\n\n", size);
    
    // 测试Hoare版本
    memcpy(testArray, originalArray, sizeof(int) * size);
    double hoareTime = calculateSortTime(hoareQuickSort, testArray, size);
    printf("Hoare版本排序时间: %.4f 毫秒\n", hoareTime);
    
    // 测试挖坑法
    memcpy(testArray, originalArray, sizeof(int) * size);
    double holeTime = calculateSortTime(holeQuickSort, testArray, size);
    printf("挖坑法排序时间: %.4f 毫秒\n", holeTime);
    
    // 测试Lomuto版本
    memcpy(testArray, originalArray, sizeof(int) * size);
    double lomutoTime = calculateSortTime(lomutoQuickSort, testArray, size);
    printf("Lomuto版本排序时间: %.4f 毫秒\n", lomutoTime);
    
    // 测试非递归版本
    memcpy(testArray, originalArray, sizeof(int) * size);
    double nonRecursiveTime = calculateSortTime(nonRecursiveQuickSort, testArray, size);
    printf("非递归版本排序时间: %.4f 毫秒\n\n", nonRecursiveTime);
    
    // 比较结果
    printf("性能比较:\n");
    printf("Hoare版本 > 挖坑法: %.2f%%\n", (hoareTime / holeTime - 1) * 100);
    printf("Hoare版本 > Lomuto版本: %.2f%%\n", (hoareTime / lomutoTime - 1) * 100);
    printf("Hoare版本 > 非递归版本: %.2f%%\n", (hoareTime / nonRecursiveTime - 1) * 100);
    
    // 释放内存
    free(originalArray);
    free(testArray);
    
    return 0;
}

代码的运行结果如下：

数组大小: 100000个元素

Hoare版本排序时间: 11.1510 毫秒

挖坑法排序时间: 10.3340 毫秒

Lomuto版本排序时间: 11.7720 毫秒

非递归版本排序时间: 12.2220 毫秒

性能比较:

Hoare版本 > 挖坑法: 7.91%

Hoare版本 > Lomuto版本: -5.28%

Hoare版本 > 非递归版本: -8.76%

可以看到，挖坑法快速排序所消耗的时间是明显少于其他三种方法的。Hoare 版本通常表现最佳，因为它的交换操作最少；挖坑法与 Hoare 版本性能接近，但实现方式更直观；Lomuto 版本由于交换次数较多，通常比前两种稍慢；非递归版本由于使用栈模拟递归，会有一定的额外开销，通常比递归版本稍慢，但可以有效避免栈溢出问题。在实际情况中使用哪种方法实现快速排序，就需要大家根据具体使用需求来进行选择了。