排序算法全解

@llx

2025-03-14 10:58:04

发布于：浙江

6阅读

0回复

0点赞

C++排序算法全解析(并不全请见谅)

在编程中，排序是一种常见的操作，用于将数据按照一定的顺序排列。每种排序算法都有其特点和适用场景。本文将详细介绍几种常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序，并通过代码示例帮助理解。（~~爆肝4天的杰作~~）

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数组，比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数组的工作是重复地进行，直到没有再需要交换的元素为止。

算法步骤

比较相邻的元素，如果第一个比第二个大（升序），就交换它们。
对每一对相邻元素做同样的工作，从数组的开始到结尾，这样在最后一趟比较后，最大的元素会“冒泡”到数组的末尾。
重复上述过程，每次遍历都会将未排序部分的最大元素放到其最终位置。

代码示例

#include <bits/stdc++.h>
using namespace std;

void bs(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { // 外层循环控制趟数
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) { // 内层循环控制每趟的比较次数
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 如果某趟没有发生交换，说明已经有序
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bs(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

特点

优点：实现简单，容易理解。
缺点：效率较低，时间复杂度为 O(n²)，即使数组已经有序，也需要进行 n-1 趟比较。
适用场景：适用于数据量较小的排序。

二、选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中找到最小（或最大）的元素，存放到排序序列的末尾。

算法步骤

在未排序的数组中找到最小元素的索引。
将找到的最小元素与未排序部分的第一个元素交换。

代码示例

#include <bits/stdc++.h>
using namespace std;

void ss(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { // 外层循环控制趟数
        int minIndex = i; // 假设当前索引是最小值的索引
        for (int j = i + 1; j < n; j++) { // 内层循环找到最小值的索引
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) { // 如果找到更小的值，则交换
            swap(arr[i], arr[minIndex]);
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    ss(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

特点

优点：实现简单，容易理解（emm......个人还是喜欢冒泡

）。

缺点：时间复杂度为 O(n²)，效率较低。
适用场景：适用于数据量较小的排序。

三、插入排序（Insertion Sort）

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

算法步骤

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤 2~5。

代码示例

#include <bits/stdc++.h>
using namespace std;

void ise(int arr[], int n) {
    for (int i = 1; i < n; i++) { // 外层循环控制每个元素
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) { // 内层循环找到插入位置
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入元素
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    ise(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

特点

优点：简单易懂，对于小规模数据排序效率较高。
缺点：时间复杂度为 O(n²)，效率较低。
适用场景：适用于数据量较小且基本有序的排序。

四、快速排序（Quick Sort）

快速排序是一种高效的排序算法(~~真正实用的算法~~)，采用分治法的思想。它通过一个基准值将数组分为两部分，左边部分的所有元素都不大于基准值，右边部分的所有元素都不小于基准值，然后递归地对左右两部分进行排序。

算法步骤

选择一个基准值（pivot）。
将数组分为两部分，左边部分的所有元素都不大于基准值，右边部分的所有元素都不小于基准值。
对左右两部分递归地进行快速排序。

代码示例

#include <bits/stdc++.h>
using namespace std;

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 qs(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 对数组进行划分
        qs(arr, low, pi - 1); // 递归地对左半部分排序
        qs(arr, pi + 1, high); // 递归地对右半部分排序
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    qs(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

特点

优点：平均时间复杂度为 O(nlogn)，在实际应用中效率较高。
缺点：最坏情况下时间复杂度为 O(n²)，但这种情况很少出现。
适用场景：适用于大规模数据的排序。

五、归并排序（Merge Sort）

归并排序是一种采用分治法（~~666上强度了~~）的排序算法。它将数组分成两部分，分别对两部分进行排序，然后将排序好的两部分合并成一个有序数组。

算法步骤

将数组分成两部分，分别对两部分进行归并排序。
将排序好的两部分合并成一个有序数组。

代码示例

#include <bits/stdc++.h>
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[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}