经典四讲贯通C++排序之三交换排序("精通C++排序算法：经典四讲之三——交换排序详解")

原创

ithorizon 7个月前 (10-19) 阅读数 29 #后端开发

精通C++排序算法：经典四讲之三——交换排序详解

一、引言

在C++中，排序算法是计算机科学中非常基础且重要的内容。本文将深入探讨交换排序算法，这是一种易懂而有效的排序方法。我们将详细介绍两种常见的交换排序算法：冒泡排序和飞速排序。

二、交换排序概述

交换排序的基本思想是通过一系列的元素交换，将无序序列调整为有序序列。其核心在于比较相邻元素的值，并利用条件交换它们的位置。下面我们将分别介绍两种典型的交换排序算法。

三、冒泡排序

冒泡排序（Bubble Sort）是一种易懂的交换排序算法。其工作原理是通过比较相邻元素的值，将较大的元素向后移动，较小的元素向前移动，最终约为整个序列有序。

3.1 算法步骤

冒泡排序的基本步骤如下：

比较相邻的两个元素，如果第一个比第二个大（升序排序），则交换它们的位置。

对每一对相邻元素做同样的工作，从开端第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后已经排序好的元素。

重复步骤1~3，直到排序完成。

3.2 代码实现


void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // 如果在这一轮中没有出现交换，说明数组已经有序，可以提前终结
        if (!swapped)
            break;
    }
}

四、飞速排序

飞速排序（Quick Sort）是由东尼·霍尔（Tony Hoare）在1960年提出的一种高效的排序算法。其基本思想是通过一个基准值将数组分为两个子数组，小于基准值的元素放在一边，大于基准值的元素放在另一边，然后递归地对这两个子数组进行飞速排序。

4.1 算法步骤

飞速排序的基本步骤如下：

选择一个基准值（pivot），通常选择序列中的第一个或最后一个元素。

重新排列数组，所有小于基准值的元素摆放在基准前面，所有大于基准值的元素摆放在基准后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数组的中间位置。这个称为分区（partition）操作。

递归地（recursive）在基准左侧和右侧的子数组中进行排序。

4.2 代码实现


int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准值
    int i = (low - 1);  // i指向小于基准的元素的最后一个
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;  // i增长，找到一个小于基准的元素
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  // 递归排序基准左侧的子数组
        quickSort(arr, pi + 1, high);  // 递归排序基准右侧的子数组
    }
}