十种排序算法(C++)

C++ 十种排序算法

前言

先写一个输入输出的模版，中间调用对应的函数进行排序

#include <iostream>
#include <vector>
#include <sstream>

int main() {
    std::cout << "请输入要排序的数字，使用逗号隔开，然后按回车结束输入：" << std::endl;

    // 读取输入并解析为向量
    std::string input;
    std::getline(std::cin, input);
    std::vector<int> numbers;
    std::stringstream ss(input);
    int num;
    char comma;

    while (ss >> num) {
        numbers.push_back(num);
        ss >> comma; // 读取逗号
    }

    // 调用排序函数
    bubbleSort(numbers); //冒泡为例

    // 输出排序后的结果
    std::cout << "排序后的结果：" << std::endl;
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1. 时间复杂度\(O(n^2)\)
   1. 冒泡排序
   2. 选择排序
   3. 插入排序
2. 时间复杂度\(O(nlog_n)\)
   1. 归并排序
   2. 快速排序
   3. 堆排序
   4. 希尔排序
3. 时间复杂度\(O(n)\)
   1. 基数排序
   2. 桶排序
   3. 计数排序

1. 冒泡排序

冒泡排序是一种简单的排序算法。它重复地遍历待排序的元素列表，比较相邻的两个元素，并在需要时交换它们的位置，直到整个列表都排序完成。

算法描述

1. 初始状态：假设我们有一个未排序的数组或列表。
2. 从列表的第一个元素开始，依次比较相邻的两个元素。
3. 如果当前元素大于后面的元素，交换这两个元素的位置，使较大的元素“浮”到列表的末尾。
4. 继续依次比较相邻元素，重复步骤 3，直到达到列表的倒数第二个元素。
5. 一轮比较完成后，最大的元素已经位于列表的末尾，可以将其视为“已排序部分”。
6. 重复步骤 2-5，但不包括已经排好序的末尾元素。每一轮比较都会将当前未排序部分的最大元素浮到末尾。
7. 重复执行步骤 2-6，直到所有元素都被排好序。

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    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;
            }
        }
    }
}

特点

每一轮比较都会将当前未排序部分的最大元素“冒泡”到末尾。它通过不断交换相邻元素来达到排序的目的。

复杂度

冒泡排序的时间复杂度为 O(\(n^2\))，在大部分情况下不如其他高效的排序算法。它通常适用于排序元素个数较少的情况，

2. 选择排序

选择排序每次从待排序的元素中选择最小（或最大）的元素，然后将其放到已排序部分的末尾。

算法描述

1. 初始状态：假设我们有一个未排序的数组或列表。
2. 找到当前未排序部分中的最小（或最大）元素。
3. 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
4. 此时，第一个元素是已排序部分的最后一个元素。
5. 将已排序部分的长度加一，未排序部分的长度减一。
6. 重复步骤 2-5，直到未排序部分为空，所有元素都被排好序

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    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) {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

特点

每次从未排序部分选择一个最小（或最大）的元素，放置在已排序部分的末尾。

复杂度

选择排序在时间复杂度上也是 O(\(n^2\))，但是由于其每一轮只需要一次交换操作，因此在某些情况下，它可能相对冒泡排序更快一些。不过，它依然不如快速排序、归并排序等更高效的排序算法。

3. 插入排序

算法描述

1. 初始状态：假设我们有一个未排序的数组或列表。
2. 从第二个元素开始，将当前元素视为“待插入元素”。
3. 将待插入元素与已排序的部分进行比较，找到其在已排序部分中的正确位置。
4. 依次将已排序部分中比待插入元素大的元素往后移动一个位置，为待插入元素腾出位置。
5. 将待插入元素放入正确的位置，使得已排序部分仍然保持有序。
6. 重复步骤 2-5，直到所有元素都被插入到已排序部分。

类似于手动整理一副牌

void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    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;
    }
}

特点

随着每个元素的插入，已排序部分会不断扩大，直到整个列表都排好序

算法复杂度

虽然插入排序的时间复杂度在最坏情况下为 O(\(n^2\))，但在部分有序的情况下，插入排序的性能会较好。它适用于数据量较小或已基本有序的情况。

4. 归并排序

算法描述

1. 分治策略：归并排序采用分治策略，将一个大问题分成两个或更多的小问题，然后递归地解决这些小问题。在排序中，它将一个未排序的数组分成两个相等大小的子数组。
2. 递归排序：对每个子数组递归应用归并排序，直到子数组的长度为1，即已排序。
3. 合并：将已排序的子数组合并成一个大的有序数组。合并过程中，从两个子数组中选择较小的元素，依次放入结果数组，直到两个子数组都合并完毕。
4. 递归回溯：不断回溯到更高层次的递归调用，合并更大的子数组，直到整个数组都排序完毕。

// 合并两个有序子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组来存放两个子数组
    std::vector<int> leftArr(n1);
    std::vector<int> rightArr(n2);

    // 将数据复制到临时数组 leftArr[] 和 rightArr[]
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
        rightArr[i] = arr[mid + 1 + i];
    }

    // 归并两个子数组到原数组 arr[]
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 处理剩余的元素
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// 归并排序函数
void mergeSort(std::vector<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);
    }
}

特点

归并排序是一种稳定的排序算法，其时间复杂度稳定在O(\(n log_n\))，适用于各种不同大小的数据集。它的主要优点之一是能够处理大规模数据集，但缺点是需要额外的内存来存储临时数组。

（搜索深度是O(logn)，合并操作是O(n)）

算法复杂度

5. 快速排序 ✨

算法描述

1. 选择基准元素：从待排序的元素中选择一个基准元素。通常选择第一个元素，但也可以选择任何其他元素。
2. 分区：将元素分成两个子序列，小于基准元素的子序列和大于基准元素的子序列。这个过程称为分区。
3. 递归排序：对小于基准元素和大于基准元素的两个子序列分别递归应用快速排序。
4. 合并：将排序好的子序列合并在一起，整个序列就变成了有序的。

void quickSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivot = arr[left]; // 选择基准元素
        int i = left, j = right;

        while (i < j) {
            // 从右向左找小于基准的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }//跳出此循环，代表right找到了比temp小的数字，所以此时arr[left]=arr[right]
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }

            // 从左向右找大于基准的元素
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }

        arr[i] = pivot; // 将基准元素放入正确的位置

        // 递归排序基准左右两部分
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

特点

1. 分治策略：快速排序是一种分治策略，即把大的问题分成小的，然后递归地解决这些小问题。
2. 原地排序：快速排序是一种原地排序算法，对于大规模数据的性能通常很好，它不需要额外的空间来存储临时数据，因为它通过交换元素在原数组上进行排序。
3. 不稳定性：快速排序在分区过程中不保持相同元素的相对顺序，所以是不稳定的排序算法。这意味着如果原始数组中存在相同值的元素，它们在排序后可能会改变相对位置。

算法复杂度

快速排序的平均时间复杂度为O(\(n log_n\))，其中n是待排序的元素个数。这使得它在大多数情况下比冒泡排序和插入排序更快。不过，最坏情况下的时间复杂度是O(\(n^2\))，但通过合理选择基准元素可以避免最坏情况的发生。

6. 堆排序

算法描述

1. 建立堆：首先，将待排序的数组视为一个二叉堆。二叉堆通常采用数组来表示，其中父节点的值总是不小于（或不大于，具体取决于是最大堆还是最小堆）其子节点的值。
2. 建堆：通过对数组进行一次“堆化”操作，将数组构建为一个合法的堆结构。堆化操作会从最后一个非叶子节点开始，逐个将子树调整为符合堆性质的状态。
3. 排序：一旦堆构建完毕，堆的根节点就是最大（或最小）值。将根节点与最后一个叶子节点交换，然后将剩余部分重新堆化。这会将最大（或最小）的元素移动到正确的位置。重复这个过程，每次将最大（或最小）的元素放置到已排序部分的末尾。
4. 重复排序：重复步骤3，逐渐缩小堆的规模，直到整个数组都排序完成。

#include <iostream>
#include <vector>

// 调整堆，确保以i为根节点的子树满足堆的性质
void heapify(std::vector<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) {
        std::swap(arr[i], arr[largest]);

        // 递归调整子树
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 建立最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 一个接一个地提取最大值并缩小堆
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]); // 将最大元素移到最后
        heapify(arr, i, 0); // 对剩下的部分重新堆化
    }
}

特点

堆排序是一种原地排序算法，它具有稳定的O(\(nlog_n\))时间复杂度，适用于大规模数据集。但需要注意，堆排序对于小规模数据集来说，相对于其他排序算法，性能可能不如其他简单的算法。

7. 希尔排序

算法描述

1. 选择间隔序列：希尔排序的核心是选择一个或多个间隔（增量）序列。这些增量是一系列递减的整数，用于控制排序过程的分组。不同的增量序列可以影响排序的性能。
2. 分组排序：根据所选增量序列，将数组分成多个子数组，每个子数组包含间隔为增量的元素。然后对每个子数组应用插入排序或其他排序算法。
3. 逐渐缩小增量：重复步骤2，逐渐减小增量，最终减小到1。
4. 最终排序：当增量减小到1时，整个数组被分成一个大组，进行最终的排序。通常，此时的数组已经在前几轮排序中变得部分有序，因此最终排序的工作量相对较小。

#include <iostream>
#include <vector>

// 希尔排序函数
void shellSort(std::vector<int>& arr) {
    int n = arr.size();

    // 选择增量序列，这里使用经典的希尔增量序列
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子数组应用插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

特点

希尔排序是一种改进的插入排序算法，通过选择不同的增量序列可以在性能和排序效率之间取得平衡。希尔排序的平均时间复杂度通常介于O(\(nlog_n\))和O(\(n^2\))之间，取决于增量序列的选择。希尔排序在某些情况下，特别是对于中等大小的数据集，性能优于常规的插入排序。希尔排序的优势在于其原地排序性质。

算法复杂度

8. 基数排序

算法描述 特点 算法复杂度

9. 桶排序

算法描述 特点 算法复杂度

10. 计数排序

算法描述 特点 算法复杂度