[已解决]冒泡的改进

aaron0919

冒泡排序

原版冒泡

冒泡排序

他有一个问题，就是有些排序只要不止 n-1 次，甚至一次就行了。

例如 1 2 4 3 6 5

你的任务

你需要给他改进。

如果对了，可以获得十鱼币！！！

还能显示在我的作品里！

最佳答案

月排行榜 / 总排行榜

weekend2000

2022-8-27 21:31:59

其实就是每次遍历加一个判断：未排序部分是否全部已经是顺序，如果是就说明已经完全顺序了
没有楼上那么强，我直接用int类型写了

void bubble_sort(int* arr, int size) {
        for (int i = 0; i < size; i++) {
                int flag = 1; // 0:需要排序  1:不需要排序
                for (int j = 0; j < size - i - 1; j++) {
                        if (arr[j] > arr[j + 1]) {
                                flag = 0;
                                int temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
                }
                if (flag) break;
        }
}

跳转到最佳答案楼层

weekend2000

其实就是每次遍历加一个判断：未排序部分是否全部已经是顺序，如果是就说明已经完全顺序了
没有楼上那么强，我直接用int类型写了

void bubble_sort(int* arr, int size) {
        for (int i = 0; i < size; i++) {
                int flag = 1; // 0:需要排序  1:不需要排序
                for (int j = 0; j < size - i - 1; j++) {
                        if (arr[j] > arr[j + 1]) {
                                flag = 0;
                                int temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
                }
                if (flag) break;
        }
}

人造人

没看懂 “你的任务”
我是这样写冒泡排序的
我比较喜欢从前往后遍历
两层循环的结束条件都是小于data.size()
外层从0开始，内层从 i + 1 开始

template<typename T>
void sort(vector<T> &data, compare_t<T> comp = less_t<T>()) {
    for(size_t i = 0; i < data.size(); ++i) {
        for(size_t j = i + 1; j < data.size(); ++j) {
            if(!comp(data[i], data[j])) swap(data[i], data[j]);
        }
    }
}

另外，趁此机会再学习一下C++的模板，还有std::function

#include <iostream>
#include <vector>
#include <functional>

using std::cout, std::endl;
using std::vector;
using std::ostream;
using std::function;

template<typename T>
void swap(T &a, T &b) {
    T temp = a; a = b; b = temp;
}

template<typename T>
struct less_t {
    bool operator()(const T &a, const T &b) {
        return a < b;
    }
};

template<typename T>
struct greater_t {
    bool operator()(const T &a, const T &b) {
        return a > b;
    }
};

template<typename T>
using compare_t = function<bool (const T &a, const T &b)>;

template<typename T>
void sort(vector<T> &data, compare_t<T> comp = less_t<T>()) {
    for(size_t i = 0; i < data.size(); ++i) {
        for(size_t j = i + 1; j < data.size(); ++j) {
            if(!comp(data[i], data[j])) swap(data[i], data[j]);
        }
    }
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &data) {
    for(size_t i = 0; i < data.size(); ++i) {
        os << data[i] << " ";
    }
    return os;
}

int main() {
    {
        vector<size_t> data = {1, 2, 4, 3, 6, 5};
        sort<size_t>(data);
        cout << data << endl;
    }
    {
        vector<size_t> data = {1, 2, 4, 3, 6, 5};
        sort<size_t>(data, less_t<size_t>());
        cout << data << endl;
    }
    {
        vector<size_t> data = {1, 2, 4, 3, 6, 5};
        sort<size_t>(data, [](const size_t &a, const size_t &b) {return a < b;});
        cout << data << endl;
    }
    {
        vector<size_t> data = {1, 2, 4, 3, 6, 5};
        sort<size_t>(data, greater_t<size_t>());
        cout << data << endl;
    }
    return 0;
}

人造人

嗯，我看了一下你讲的冒泡排序
我这个排序算法应该不能叫冒泡排序，这个排序算法叫什么名字？选择排序？
我对这些概念不是很了解，^_^

人造人

我看了一下你讲的选择排序，这个应该是选择排序，^_^
解释一下 “你的任务”
我想想怎么改

weekend2000

人造人 发表于 2022-8-28 00:24
我看了一下你讲的选择排序，这个应该是选择排序，^_^
解释一下 “你的任务”
我想想怎么改

是选择排序的思路，但是你的遍历方式似乎并不是选择排序的最优解，因为其中有大量不必要的元素交换，感觉挺浪费时间的。
下面是我的选择排序

void selection_sort2(int *arr, int size) {
        for (int i = 0; i < size; i++) {
                int min = i;
                for (int j = i + 1; j < size; j++) {
                        if (arr[j] < arr[min]) {
                                min = j;
                        }
                }
                // 判定是否需要交换
                if (min == i) {
                        continue;
                } else {
                        int temp = arr[i];
                        arr[i] = arr[min];
                        arr[min] = temp;
                }
        }
}

人造人

weekend2000 发表于 2022-8-28 00:55
是选择排序的思路，但是你的遍历方式似乎并不是选择排序的最优解，因为其中有大量不必要的元素交换，感 ...

我就是按照冒泡排序的样子写的，我一直以为这个是冒泡排序，^_^

人造人

weekend2000 发表于 2022-8-28 00:55
是选择排序的思路，但是你的遍历方式似乎并不是选择排序的最优解，因为其中有大量不必要的元素交换，感 ...

嗯，这个我看懂了，感谢，^_^

aaron0919

人造人 发表于 2022-8-28 00:21
嗯，我看了一下你讲的冒泡排序
我这个排序算法应该不能叫冒泡排序，这个排序算法叫什么名字？选择排序？
...

选择第二个

aaron0919

weekend2000 发表于 2022-8-28 00:55
是选择排序的思路，但是你的遍历方式似乎并不是选择排序的最优解，因为其中有大量不必要的元素交换，感 ...

因为其实懒得写啦