常见的排序算法（一）

冒泡排序是一种直观且易于理解的排序算法，适合于小规模数据和教学演示。但由于其时间复杂度较高，在面对大规模数据时并不高效。在实际应用中，常常会用更高效的排序算法，如快速排序、归并排序等，来代替冒泡排序。尽管如此，冒泡排序因其稳定性和简单性，仍然在一些特殊场景下有其价值，特别是在数据集较小或几乎已经有序的情况下。选择排序虽然是一种简单且易于理解的排序算法，但它的时间复杂度为 (O(n^2))，对于大规

m0_63903713

1105人浏览 · 2024-11-05 18:18:53

m0_63903713 · 2024-11-05 18:18:53 发布

一、冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，最早由 Edward N. L. Dijkstra 提出，广泛应用于初学者的排序学习中。它通过重复遍历待排序元素列，依次比较相邻元素的大小并交换位置，使得较大的元素“浮”到序列的末端，就像水泡一样向上浮动，逐渐完成排序的过程。

（一）、冒泡排序的基本思想

冒泡排序的工作原理是通过两两比较相邻元素的大小，如果顺序错误，则交换这两个元素的位置。每一轮遍历完成后，最大（或最小）元素都会被“冒泡”到序列的末端，故得名“冒泡排序”。每次遍历都会把当前未排序部分的最大元素排到已排序部分的末尾。

具体步骤如下：

初始状态：从待排序序列的第一个元素开始，依次与其后面的元素进行比较，若前者比后者大，则交换位置。
一轮遍历：完成一次对整个序列的遍历后，最大的元素会被移动到最后的位置。
逐渐减少范围：每次遍历完成后，已排序部分的元素不再参与下一轮比较，因此下次比较的范围会缩小一位。
终止条件：当一轮遍历没有发生交换时，说明序列已经排好序，可以提前终止排序。

（二）、冒泡排序的代码示例

以下是用实现的冒泡排序算法的代码示例：

#include <stdio.h>

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    // 外层循环控制排序的轮数
    for (int i = 0; i < n - 1; i++) {
        // 标记这一轮是否有交换发生
        int swapped = 0;

        // 内层循环进行相邻元素比较
        for (int j = 0; j < n - 1 - i; j++) {
            // 如果前一个元素大于后一个元素，交换它们
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                
                // 标记发生了交换
                swapped = 1;
            }
        }
        
        // 如果这一轮没有发生交换，说明数组已经有序，提前退出
        if (swapped == 0) {
            break;
        }
    }
}

// 打印数组的函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("排序后的数组: ");
    printArray(arr, n);

    return 0;
}

（三）、代码解析

bubbleSort 函数：该函数接受两个参数，arr[]是待排序的数组，n是数组的大小。它通过两层循环来完成排序。外层循环控制排序的轮数，每轮结束时确定一个最大值的元素到达数组末端；内层循环逐个比较相邻元素，如果前一个元素比后一个元素大，则交换它们的位置。
优化：代码中使用了一个 swapped 标志来判断是否在这一轮遍历中发生了交换。如果没有交换，说明数组已经有序，可以提前终止排序，从而提高算法的效率。
printArray 函数：该函数用于打印数组，帮助我们查看排序前后的数组状态。

（四）、冒泡排序的时间复杂度

最坏情况（完全逆序）：每一次比较都需要交换，因此冒泡排序的最坏时间复杂度是 O(n²)，其中 n 是待排序元素的数量。
最佳情况（已经有序）：如果数组已经是升序排列，在没有交换的情况下，冒泡排序会提前终止，因此最佳时间复杂度是 O(n)。
平均情况：无论数组的初始状态如何，冒泡排序的平均时间复杂度依然是 O(n²)，因为它仍然需要逐个比较元素。
空间复杂度：冒泡排序是一个原地排序算法，只需要常数级的额外空间，因此空间复杂度是 O(1)。

（五）、冒泡排序的优缺点

优点：

简单易懂：冒泡排序是一种非常简单且易于理解的排序算法，适合用作教学工具。
稳定性：冒泡排序是稳定的排序算法，即相等的元素在排序后相对位置不变。
原地排序：不需要额外的存储空间，节省空间。

缺点：

效率低：冒泡排序在大数据量下效率非常低，最坏情况和平均情况的时间复杂度是 O(n²)。
不适用于大规模数据：由于其低效性，冒泡排序通常不适合用在大规模数据排序中。

（六）、冒泡排序的优化

虽然标准的冒泡排序已经很简单，但它仍然可以做一些优化：

提前终止：如前所述，如果在某一轮遍历中没有发生任何交换，说明数组已经是有序的，可以提前终止排序，这就是上面代码中 swapped 标志的作用。
双向冒泡排序（又称鸡尾酒排序）：这种方法是在每一轮中从前向后进行一遍冒泡排序，然后再从后向前进行一次冒泡排序。这样可以让较小的元素也能快速地“冒泡”到前面，从而减少不必要的比较。

（七）、适用场景

小规模数据：对于规模较小的数据集，冒泡排序的简单性使其成为一个可行的选择。尤其是在数据接近有序时，它能够很快地终止，从而具有较高的效率。
教学和演示：由于其简单易懂，冒泡排序是学习排序算法时的常用例子，有助于学生理解排序的基本概念。
无需额外空间的原地排序：如果需要原地排序且不关心效率，冒泡排序也能胜任。

（八）、总结

冒泡排序是一种直观且易于理解的排序算法，适合于小规模数据和教学演示。但由于其时间复杂度较高，在面对大规模数据时并不高效。在实际应用中，常常会用更高效的排序算法，如快速排序、归并排序等，来代替冒泡排序。

尽管如此，冒泡排序因其稳定性和简单性，仍然在一些特殊场景下有其价值，特别是在数据集较小或几乎已经有序的情况下。

二、插入排序

插入排序是一种简单的排序算法，概念来源于扑克牌的排序方法。在这个过程中，假设已排序的部分和未排序的部分不断交替，直到整个数据集合都被排序完毕。

插入排序的基本思想是：将一个数据元素插入到已排序的序列中，使得插入后的序列仍然是有序的。插入排序通常用于数据量较小或几乎已排序的情况下，因为它的时间复杂度较高。

（一）、插入排序的工作原理

假设我们有一个待排序的序列：

[7, 2, 4, 8, 3, 5]

插入排序从第二个元素开始，逐步将每个元素插入到它前面的已排序部分中。以下是插入排序的具体步骤：

初始化：将第一个元素看作已经排好序的部分，剩下的部分为未排序部分。
遍历未排序部分：从第二个元素开始，依次取出每个元素（称为“当前元素”）。
插入操作：将当前元素与已排序部分进行比较，找到合适的位置插入。插入时，已经比当前元素大的元素向后移动，为当前元素腾出位置。
重复步骤2和3：直到遍历完所有元素，整个序列就会被排序好。

（二）、示例

我们对上面提到的数组 [7, 2, 4, 8, 3, 5] 进行插入排序，详细的过程如下：

初始状态：[7, 2, 4, 8, 3, 5]
- 选择 2 作为当前元素，将其与已排序的部分 [7] 比较，发现 2 比 7 小，因此交换它们。
- 排序后的部分为 [2, 7]，未排序部分为 [4, 8, 3, 5]。
第二步：[2, 7, 4, 8, 3, 5]
- 选择 4 作为当前元素，将其与已排序部分 [2, 7] 比较，4 比 7 小，但大于 2，因此将 4 插入到 2 和 7 之间。
- 排序后的部分为 [2, 4, 7]，未排序部分为 [8, 3, 5]。
第三步：[2, 4, 7, 8, 3, 5]
- 选择 8 作为当前元素，发现 8 已经在正确的位置，因此无需交换。
- 排序后的部分为 [2, 4, 7, 8]，未排序部分为 [3, 5]。
第四步：[2, 4, 7, 8, 3, 5]
- 选择 3 作为当前元素，发现 3 小于 8，7，4，2，因此将 3 插入到最前面。
- 排序后的部分为 [2, 3, 4, 7, 8]，未排序部分为 [5]。
第五步：[2, 3, 4, 7, 8, 5]
- 选择 5 作为当前元素，将其与已排序部分 [2, 3, 4, 7, 8] 比较，5 插入到 4 和 7 之间。
- 排序后的部分为 [2, 3, 4, 5, 7, 8]，未排序部分为空，排序结束。

最终排序后的数组为 [2, 3, 4, 5, 7, 8]。

（三）、插入排序的时间复杂度分析

插入排序的时间复杂度取决于序列的初始状态。如果数据几乎是有序的，那么插入排序的性能非常好；如果数据是逆序的，那么性能最差。

最佳情况（已经排序好的数组）：每次插入操作不需要交换，所有元素已经在正确的位置，时间复杂度为 ( O(n) )。
最坏情况（逆序数组）：每次插入操作都需要移动所有已排序的元素，时间复杂度为 ( O(n^2) )。
平均情况：对于随机排列的数据，时间复杂度通常为 ( O(n^2) )，因为在大部分情况下需要比较和移动多次。

（四）、插入排序的空间复杂度

插入排序是一种 原地排序算法，即它只需要常数级别的额外空间，因此其空间复杂度为 ( O(1) )。

（五）、插入排序的优缺点

优点：

实现简单：插入排序非常简单，容易理解和实现。
稳定性：插入排序是一种稳定的排序算法，即如果两个元素相等，它们的相对顺序不会改变。
适用于小规模数据：对于小规模的数组或已经接近排序好的数组，插入排序的性能很好。
局部有序数组：对于局部已经有序的数组，插入排序可以高效地完成排序。

缺点：

时间复杂度较高：在大规模数据情况下，插入排序的时间复杂度为 ( O(n^2) )，性能差。
不适用于大规模数据：因为时间复杂度较高，当待排序的元素较多时，插入排序效率低下，不适合大规模数据集。

（六）插入排序的优化

二分查找优化插入位置：在每次插入操作时，可以使用 二分查找 来定位插入位置，从而减少比较次数。虽然插入排序的时间复杂度依然是 ( O(n^2) )，但减少比较的次数可以提升性能。

（七）插入排序的代码示例

下面是插入排序的代码实现：

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    // 从第二个元素开始
    for (i = 1; i < n; i++) {
        key = arr[i];  // 当前元素
        j = i - 1;
        
        // 将比key大的元素右移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // 插入key
        arr[j + 1] = key;
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {7, 2, 4, 8, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    printf("排序后数组: ");
    printArray(arr, n);
    
    return 0;
}

（八）代码解析

insertionSort 函数实现了插入排序的主要逻辑。外层循环遍历数组的每个元素，内层循环用于将当前元素插入到已排序的部分。
printArray 函数用于输出数组，便于查看排序结果。
main 函数初始化一个整数数组，调用排序函数并输出排序前后的数组。

（九）插入排序与其他排序算法的对比

插入排序与其他常见排序算法（如冒泡排序、快速排序、归并排序）相比，在不同的应用场景下有不同的优势和劣势：

与冒泡排序比较：两者的时间复杂度相同（最坏情况均为 ( O(n^2) )），但是插入排序的操作次数通常较少，因为它只在需要时才进行元素交换，而冒泡排序在每次比较时都会进行交换。
与快速排序比较：快速排序的时间复杂度为 ( O(n \log n) )，远优于插入排序，尤其是在处理大量数据时。但快速排序是非稳定的，而且它的空间复杂度较高。而插入排序稳定，空间复杂度低，适合小规模数据。
与归并排序比较：归并排序的时间复杂度为 ( O(n \log n) )，且是稳定排序算法，但它的空间复杂度较高（需要 ( O(n) ) 的额外空间）。插入排序的空间复杂度为 ( O(1) )，适合需要节省空间的应用。

（十）、结论

插入排序是一种简单、直观且易于实现的排序算法，尤其适用于小规模数据或几乎已排序的情况。然而，对于大规模数据，插入排序的效率较低，因此在实际应用中往往结合其他高效的排序算法，如快速排序、归并排序等使用。

三、选择排序

选择排序是一种简单的排序算法，其基本思想是通过反复选择最小（或最大）的元素，并将其放到已排序部分的末尾（或开头），逐步将无序的部分缩小，直到整个序列排序完成。选择排序是一种不稳定排序算法，时间复杂度为 (O(n^2))，因此在大规模数据排序时效率较低。

（一）、算法的基本思想

选择排序的核心思想是：每一轮都从未排序部分选出一个最小的元素，并将其放到已排序部分的末尾。

具体步骤如下：

从待排序的数组中找到最小的元素。
将该最小元素与数组的第一个元素交换位置。
继续对剩余的部分进行相同的操作：从剩余未排序部分找出最小的元素，交换到未排序部分的第一个位置。
重复这一过程，直到整个数组排序完成。

（二）、选择排序的工作原理

假设我们有一个待排序的数组：

[64, 25, 12, 22, 11]

第一轮排序：

查找最小值，最小值是 11，与第一个元素 64 交换，得到：[11, 25, 12, 22, 64]

第二轮排序：

查找剩余部分中最小值，最小值是 12，与 25 交换，得到：[11, 12, 25, 22, 64]

第三轮排序：

查找剩余部分中最小值，最小值是 22，与 25 交换，得到：[11, 12, 22, 25, 64]

第四轮排序：

查找剩余部分中最小值，最小值是 25，与 25 交换，数组没有变化：[11, 12, 22, 25, 64]

至此，整个数组已经排好序。

（三）、选择排序的时间复杂度分析

选择排序的时间复杂度可以从两个方面进行分析：

外层循环执行 (n-1) 次（每次从未排序部分选出一个元素）。
每次外层循环内，内层循环执行的次数是递减的，具体为：(n-1, n-2, \ldots, 1)。

因此，选择排序的时间复杂度为： [ O(n^2) ] 其中 (n) 是数组的元素个数。

（四）、选择排序的空间复杂度

选择排序是就地排序（in-place sort），即它只需要常数级别的额外空间来交换元素。因此，它的空间复杂度为： [ O(1) ]

（五）、选择排序的优缺点

优点：

算法实现简单，代码量少。
适用于较小规模的排序任务。
空间复杂度低，属于就地排序。

缺点：

时间复杂度较高，对于大规模数据排序时效率较低。
是不稳定的排序算法，即相等的元素在排序后相对位置可能会发生变化。

（六）、选择排序的优化版本

选择排序可以做一些简单的优化。比如，如果在一轮排序过程中没有发生任何交换，说明数组已经是有序的，算法可以提前终止。这个优化称为“提前终止”。

（七）、C语言代码示例

下面是一个用代码实现的选择排序的示例：

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;

    // 遍历整个数组
    for (i = 0; i < n - 1; i++) {
        // 假设当前索引 i 处的元素为最小值
        minIndex = i;

        // 找到最小值的索引
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;  // 更新最小值的索引
            }
        }

        // 如果最小值的索引不是 i，进行交换
        if (minIndex != i) {
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

（八）、代码解析

selectionSort 函数：实现了选择排序的核心逻辑。
- 外层循环 for (i = 0; i < n - 1; i++) 负责从未排序的部分选出一个元素，并将最小的元素放到已排序部分的末尾。
- 内层循环 for (j = i + 1; j < n; j++) 查找未排序部分的最小元素，并更新最小元素的索引 minIndex。
- 如果最小值的索引不是当前的 i，则交换这两个元素。
printArray 函数：用于打印数组中的元素。
main 函数：定义了一个待排序数组，调用 selectionSort 进行排序，并输出排序前后的数组。

（九）选择排序的总结

选择排序虽然是一种简单且易于理解的排序算法，但它的时间复杂度为 (O(n^2))，对于大规模数据集并不高效，因此在实际应用中一般只用于小规模数据排序或对时间要求不严格的场合。在选择排序中，我们每一次都要找出最小值并交换，这使得它在最坏情况下的性能始终保持一致。

在许多情况下，诸如快速排序、归并排序等更高效的算法（时间复杂度为 (O(n \log n))）会被优先考虑使用，但选择排序仍然因其简单性和易于实现的特点，在一些学习和应用场景中有其价值。

四、快速排序

快速排序（QuickSort）是一种基于分治法（Divide and Conquer）的排序算法，最早由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排序的数据分割成两部分，其中一部分的所有元素都比另一部分的所有元素小。然后递归地对这两部分继续进行排序，最终得到一个有序序列。

（一）、快速排序的核心步骤

选择基准（Pivot）：在快速排序中，首先选择一个基准元素（pivot）。通常可以从数组中选取一个元素作为基准，常见的选择策略包括：
- 选择数组的第一个元素
- 选择数组的最后一个元素
- 选择数组的中间元素
- 使用随机选择或三数取中（即选择数组中的第一个、最后一个、和中间一个元素的中位数作为基准）
分区（Partition）：接下来，通过一趟排序将数组中的元素分为两部分：一部分元素小于基准，另一部分元素大于基准。具体的做法是：
- 维护两个指针，分别从数组的两端开始扫描。
- 左指针从左往右扫描，直到找到一个大于基准的元素。
- 右指针从右往左扫描，直到找到一个小于基准的元素。
- 如果左指针小于右指针，则交换这两个元素，然后继续扫描。
- 如果左指针大于或等于右指针，分区完成。
递归排序：在分区完成后，基准元素已经被放到了正确的位置（即它的左边元素都小于它，右边元素都大于它）。此时，递归地对基准元素左边和右边的子数组进行快速排序。
结束条件：当子数组的大小为1或者0时，递归结束，因为此时数组已经有序。

（二）、快速排序的性能分析

时间复杂度：
- 最好情况：O(n log n)，当每次选择的基准都能将数组大致均分时。
- 平均情况：O(n log n)，这是快速排序在大多数情况下的时间复杂度。
- 最坏情况：O(n^2)，当每次选择的基准总是数组中的最大值或最小值（例如已排序的数组）时，导致每次只能减少一个元素。
空间复杂度：快速排序是一种原地排序算法，不需要额外的存储空间，因此空间复杂度是O(log n)，用于递归栈的空间。

（三）、快速排序的代码示例

以下是快速排序的C语言实现：

#include <stdio.h>

// 交换函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
int partition(int arr[], int low, int high) {
    // 选择基准，通常选择高位元素作为基准
    int pivot = arr[high];
    int i = low - 1; // i是小于基准的元素的右边界

    for (int j = low; j < high; j++) {
        // 如果当前元素小于基准，则交换元素
        if (arr[j] < pivot) {
            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);
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原数组：\n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("排序后的数组：\n");
    printArray(arr, n);
    
    return 0;
}

（四）、代码解释

swap函数：交换两个整数的位置。
partition函数：执行分区操作，选择最后一个元素作为基准，并将比基准小的元素移到基准的左边，比基准大的元素移到右边。最后返回基准元素的最终位置。
quickSort函数：递归地对数组的两部分进行快速排序。
printArray函数：打印数组元素。
main函数：演示如何使用快速排序对数组进行排序。

优化建议

三数取中法（Median of Three）：在选择基准时，使用三数取中法来减少出现最坏情况的概率。三数取中法选取数组的第一个元素、最后一个元素和中间元素的中位数作为基准。
尾递归优化：在递归中，尽可能先递归较小的子数组，较大的子数组使用迭代来避免栈溢出。
切换到插入排序：当子数组的大小较小时（如小于10），可以考虑切换到插入排序，因为插入排序在小数组中通常比快速排序更高效。