论坛 › C\C++交流 › 冒泡的改进

aaron0919 发表于 2022-8-27 21:31:58

冒泡的改进

本帖最后由 aaron0919 于 2022-8-28 08:14 编辑

冒泡排序

原版冒泡

冒泡排序

他有一个问题，就是有些排序只要不止 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 > arr) {
                                flag = 0;
                                int temp = arr;
                                arr = arr;
                                arr = temp;
                        }
                }
                if (flag) break;
        }
}

人造人 发表于 2022-8-27 23:36:15

没看懂 “你的任务”
我是这样写冒泡排序的
我比较喜欢从前往后遍历
两层循环的结束条件都是小于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, data)) swap(data, data);
      }
    }
}


另外，趁此机会再学习一下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, data)) swap(data, data);
      }
    }
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &data) {
    for(size_t i = 0; i < data.size(); ++i) {
      os << data << " ";
    }
    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;
}

人造人 发表于 2022-8-28 00:21:53

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

人造人 发表于 2022-8-28 00:24:50

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

weekend2000 发表于 2022-8-28 00:55:06

人造人 发表于 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 < arr) {
                                min = j;
                        }
                }
                // 判定是否需要交换
                if (min == i) {
                        continue;
                } else {
                        int temp = arr;
                        arr = arr;
                        arr = temp;
                }
        }
}

人造人 发表于 2022-8-28 01:12:20

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

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

人造人 发表于 2022-8-28 01:15:54

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

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

aaron0919 发表于 2022-8-28 08:13:05

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

选择第二个

aaron0919 发表于 2022-8-28 08:14:49

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

因为其实懒得写啦

查看完整版本: 冒泡的改进