【排序算法详细介绍】桶排序（Bucket Sort）冒泡排序（Bubble Sort）快速排序（Quick Sort）

本文介绍: 详细介绍了桶排序,冒泡排序以及快速排序,std::sort

今天学习了一些简单的排序算法,其实在我们平时解决问题中经常用到,今天正好一起看了看,记录一下。如果对你也有帮助,我很开心~

桶排序是一种排序算法，它将数组划分为一些有序的桶，然后每个桶再分别排序。最后，将所有的桶合并起来，得到一个有序的数组。桶排序的核心思想是将数据分散到不同的桶中，每个桶内部进行排序，最后将所有桶的数据合并。

小唐有话说:我感觉桶排序也是拿空间换时间的感觉,和哈希表有点像有没有!!!但是他们的主要的区别在于桶排序是一种排序算法，重于对元素的排序，而哈希表是一种数据结构，用于快速查找和插入

// 桶排序函数
void bucketSort(vector<float>& arr) {
    // 找到最大值和最小值
    //*max_element,*min_element是 C++ 标准库 <algorithm> 头文件中的函数，分别用于找到范围内的最大值和最小值。
    float max_val = *max_element(arr.begin(), arr.end());
    float min_val = *min_element(arr.begin(), arr.end());
    int bucket_count = 10; // 这里假设使用 10 个桶
    vector<vector<float>> buckets(bucket_count);// 创建桶
    // 将元素放入桶中
    for (float num : arr) {//是 C++11 引入的一种基于范围的 for 循环语法，也称为范围-based for循环
        //表示遍历浮点数数组 arr 中的每个元素，并将每个元素赋值给变量 num，然后执行循环体内的操作。
        int index = int(bucket_count * (num - min_val) / (max_val - min_val));
        buckets[index].push_back(num);
    }
    // 对每个桶内部进行排序，这里使用标准库的排序函数
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
    }
    // 将所有桶的元素合并
    arr.clear();
    for (const auto& bucket : buckets) {
        arr.insert(arr.end(), bucket.begin(), bucket.end());
    }
}

对于此处的例子,时间复杂度: O(n + 10 * log(10)),其中10是是因为分了10个桶,分桶的过程时间复杂度是 O(n),std::sort是一种改进的快速排序算法,它的平均时间复杂度是O(n log n)

冒泡排序是一种简单的排序算法，其基本思想是通过不断地交换相邻元素，将较大的元素逐渐移到右侧（或较小的元素逐渐移到左侧），从而达到排序的目的。
小唐有话说:不知道大家有没有印象!反正小唐印象超级无敌深刻,大一学C语音的时候就对它印象深刻,到现在仍然记忆尤新,当初看了好多好多遍才弄懂的算法,现在看简直简单的不能再简单,这就是轻舟已过万重山叭!

冒泡排序的时间复杂度为 O(n^2),因为时间复杂度较高，在实际应用中较少使用，特别是对于大规模数据集。

// 冒泡排序函数
void bubbleSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) { //这里注意,内层循环只用到n-i-1,因为后面的已经排过啦
            // 如果当前元素大于下一个元素，则交换它们
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {

        int pivot = arr[high];// 选择最右边的元素作为基准元素
        int i = low - 1;
        cout << i << endl;

        // 将小于等于基准元素的元素移动到左边
        for (int j = low; j < high; ++j) {
            if (arr[j] <= pivot) {
                ++i;
                swap(arr[i], arr[j]);
            }
        }

        // 将基准元素移动到正确的位置
        swap(arr[i + 1], arr[high]);
        int pivotIndex = i + 1;

        // 递归排序左右子数组
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}