hinsyeow: 排序算法

在计算机科学领域，排序算法是一类基础且核心的算法，用于将一组数据按照特定顺序排列。不同的排序算法在时间复杂度、空间复杂度和稳定性等方面各有优劣，选择合适的算法对于提升程序性能至关重要。本文将详细介绍七种常见排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序，并对其复杂度进行分析。

复杂度分析概述

在评估排序算法时，主要关注以下几个指标：

时间复杂度：描述算法执行所需的时间随数据规模增长的变化趋势，通常用大O表示法。
空间复杂度：指算法执行过程中所需的额外存储空间。
稳定性：如果排序前后相等元素的相对顺序不变，则称该算法是稳定的。

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O (n^{2})$	$O (n)$	$O (n^{2})$	$O (1)$	稳定
选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	不稳定
插入排序	$O (n^{2})$	$O (n)$	$O (n^{2})$	$O (1)$	稳定
希尔排序	$O (n^{1.3})$	$O (n)$	$O (n^{2})$	$O (1)$	不稳定
归并排序	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (n)$	稳定
快速排序	$O (n l o g n)$	$O (n l o g n)$	$O (n^{2})$	$O (l o g n)$	不稳定
堆排序	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (1)$	不稳定

冒泡排序（Bubble Sort）

算法原理

冒泡排序是一种简单直观的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

适用场景

数据量较小且基本有序的情况。

代码实现

#include <iostream>
using namespace std;

// 冒泡排序函数
void bubbleSort(int arr[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        bool swapped = false;
        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;
                swapped = true;
            }
        }
        // 如果没有发生交换，说明数组已经有序，提前退出
        if (!swapped) break;
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：平均和最坏情况下为 $O (n^{2})$ ，最好情况下（数组已经有序）为 $O (n)$ 。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。
稳定性：稳定，因为只有在相邻元素逆序时才交换，相等元素不会交换位置。

选择排序（Selection Sort）

算法原理

选择排序是一种简单直观的排序算法。它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

适用场景

数据量较小的情况，对稳定性要求不高。

代码实现

#include <iostream>
using namespace std;

// 选择排序函数
void selectionSort(int arr[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < len; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：无论最好、最坏还是平均情况，时间复杂度均为 $O (n^{2})$ 。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。
稳定性：不稳定，例如 [5, 8, 5, 2] 排序后第一个 5 会和 2 交换位置，导致两个 5 的相对顺序改变。

插入排序（Insertion Sort）

算法原理

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

适用场景

数据量较小且基本有序的情况。

代码实现

#include <iostream>
using namespace std;

// 插入排序函数
void insertionSort(int arr[], int len) {
    for (int i = 1; i < len; ++i) {
        int temp = arr[i];
        int j = i - 1;
        // 从后向前扫描，找到合适的插入位置
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：平均和最坏情况下为 $O (n^{2})$ ，最好情况下（数组已经有序）为 $O (n)$ 。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。
稳定性：稳定，因为插入时遇到相等元素不会交换位置。

希尔排序（Shell Sort）

算法原理

希尔排序是插入排序的一种更高效的改进版本。它的基本思想是将待排序的序列分割成若干个子序列，分别对这些子序列进行插入排序，随着增量逐渐减小，子序列的长度逐渐增加，整个序列变得越来越接近有序，最后对整个序列进行一次插入排序。

适用场景

数据量较大且基本无序的情况。

代码实现

#include <iostream>
using namespace std;

// 希尔排序函数
void shellSort(int arr[], int len) {
    for (int gap = len / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < len; ++i) {
            int temp = arr[i];
            int j = i;
            // 对每个子序列进行插入排序
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：希尔排序的时间复杂度与增量序列的选择有关，平均情况下约为 $O (n^{1.3})$ ，最坏情况下为 $O (n^{2})$ 。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。
稳定性：不稳定，因为不同子序列的插入操作可能会改变相等元素的相对顺序。

归并排序（Merge Sort）

算法原理

归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。它的基本思想是将一个序列分成两个子序列，分别对这两个子序列进行排序，然后将排好序的子序列合并成一个最终的有序序列。

适用场景

数据量较大且对稳定性有要求的情况。

代码实现

#include <iostream>
using namespace std;

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    // 复制数据到临时数组
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    // 合并临时数组到原数组
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左右子数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并排好序的子数组
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, len - 1);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：无论最好、最坏还是平均情况，时间复杂度均为 $O (n l o g n)$ 。
空间复杂度： $O (n)$ ，主要用于合并操作时的临时数组。
稳定性：稳定，在合并过程中，相等元素会保持原有的相对顺序。

快速排序（Quick Sort）

算法原理

快速排序也是采用分治法的一种排序算法。它的基本思想是通过选择一个基准元素，将序列分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于基准元素，然后分别对左右两部分进行递归排序。

适用场景

数据量较大且基本无序的情况。

代码实现

#include <iostream>
using namespace std;

// 分区函数
int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; ++j) {
        if (arr[j] < pivot) {
            i++;
            // 交换元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准元素放到正确的位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[right];
    arr[right] = temp;
    return i + 1;
}

// 快速排序函数
void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        // 递归排序左右子数组
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, len - 1);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：平均和最好情况下为 $O (n l o g n)$ ，最坏情况下（例如数组已经有序）为 $O (n^{2})$ 。
空间复杂度：平均情况下为 $O (l o g n)$ ，主要是递归调用栈的深度，最坏情况下为 $O (n)$ 。
稳定性：不稳定，在分区过程中可能会改变相等元素的相对顺序。

堆排序（Heap Sort）

算法原理

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序的基本思想是先将数组构建成一个最大堆（升序排序）或最小堆（降序排序），然后将堆顶元素与最后一个元素交换，再对剩余元素重新调整为堆，重复这个过程直到整个数组有序。

适用场景

数据量较大且对空间复杂度有要求的情况。

代码实现

#include <iostream>
using namespace std;

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    // 找出左右子节点和根节点中的最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        // 交换元素
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // 递归调整子树
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(arr, n, i);
    }
    // 依次取出堆顶元素并调整堆
    for (int i = n - 1; i > 0; --i) {
        // 交换堆顶元素和最后一个元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 调整剩余元素为堆
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {6, 1, 5, 2, 4, 3};
    int len = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, len);
    for (int i = 0; i < len; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：无论最好、最坏还是平均情况，时间复杂度均为 $O (n l o g n)$ 。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。
稳定性：不稳定，在堆调整过程中可能会改变相等元素的相对顺序。

总结

不同的排序算法在不同的场景下有各自的优势。在实际应用中，需要根据数据规模、数据初始状态和对稳定性的要求等因素来选择合适的排序算法。以下是一些选择建议：

当数据量较小时，冒泡排序、选择排序和插入排序都是不错的选择，其中插入排序在数据基本有序时性能较好。
当数据量较大且基本无序时，希尔排序、快速排序和堆排序的性能相对较好。
当对稳定性有要求时，归并排序是一个合适的选择。

希望本文能帮助你深入理解各种排序算法的原理和应用场景，在实际编程中做出更合适的选择。

Thursday, October 2, 2025

排序算法

复杂度分析概述

冒泡排序（Bubble Sort）

算法原理

适用场景

代码实现

复杂度分析

选择排序（Selection Sort）

算法原理

适用场景

代码实现

复杂度分析

插入排序（Insertion Sort）

算法原理

适用场景

代码实现

复杂度分析

希尔排序（Shell Sort）

算法原理

适用场景

代码实现

复杂度分析

归并排序（Merge Sort）

算法原理

适用场景

代码实现

复杂度分析

快速排序（Quick Sort）

算法原理

适用场景

代码实现

复杂度分析

堆排序（Heap Sort）

算法原理

适用场景

代码实现

复杂度分析

总结

No comments:

Post a Comment

排序算法