[已解决]冒泡的改进

aaron0919

冒泡排序

原版冒泡

冒泡排序

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

例如 1 2 4 3 6 5

你的任务

你需要给他改进。

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

还能显示在我的作品里！

最佳答案

月排行榜 / 总排行榜

weekend2000

2022-8-27 21:31:59

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

1. void bubble_sort(int* arr, int size) {
   
2.         for (int i = 0; i < size; i++) {
   
3.                 int flag = 1; // 0:需要排序  1:不需要排序
   
4.                 for (int j = 0; j < size - i - 1; j++) {
   
5.                         if (arr[j] > arr[j + 1]) {
   
6.                                 flag = 0;
   
7.                                 int temp = arr[j];
   
8.                                 arr[j] = arr[j + 1];
   
9.                                 arr[j + 1] = temp;
   
10.                         }
    
11.                 }
    
12.                 if (flag) break;
    
13.         }
    
14. }

复制代码

跳转到最佳答案楼层

weekend2000

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

1. void bubble_sort(int* arr, int size) {
   
2.         for (int i = 0; i < size; i++) {
   
3.                 int flag = 1; // 0:需要排序  1:不需要排序
   
4.                 for (int j = 0; j < size - i - 1; j++) {
   
5.                         if (arr[j] > arr[j + 1]) {
   
6.                                 flag = 0;
   
7.                                 int temp = arr[j];
   
8.                                 arr[j] = arr[j + 1];
   
9.                                 arr[j + 1] = temp;
   
10.                         }
    
11.                 }
    
12.                 if (flag) break;
    
13.         }
    
14. }

复制代码

人造人

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

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

复制代码

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <functional>
   
4. 
   
5. using std::cout, std::endl;
   
6. using std::vector;
   
7. using std::ostream;
   
8. using std::function;
   
9. 
   
10. template<typename T>
    
11. void swap(T &a, T &b) {
    
12.     T temp = a; a = b; b = temp;
    
13. }
    
14. 
    
15. template<typename T>
    
16. struct less_t {
    
17.     bool operator()(const T &a, const T &b) {
    
18.         return a < b;
    
19.     }
    
20. };
    
21. 
    
22. template<typename T>
    
23. struct greater_t {
    
24.     bool operator()(const T &a, const T &b) {
    
25.         return a > b;
    
26.     }
    
27. };
    
28. 
    
29. template<typename T>
    
30. using compare_t = function<bool (const T &a, const T &b)>;
    
31. 
    
32. template<typename T>
    
33. void sort(vector<T> &data, compare_t<T> comp = less_t<T>()) {
    
34.     for(size_t i = 0; i < data.size(); ++i) {
    
35.         for(size_t j = i + 1; j < data.size(); ++j) {
    
36.             if(!comp(data[i], data[j])) swap(data[i], data[j]);
    
37.         }
    
38.     }
    
39. }
    
40. 
    
41. template<typename T>
    
42. ostream &operator<<(ostream &os, const vector<T> &data) {
    
43.     for(size_t i = 0; i < data.size(); ++i) {
    
44.         os << data[i] << " ";
    
45.     }
    
46.     return os;
    
47. }
    
48. 
    
49. int main() {
    
50.     {
    
51.         vector<size_t> data = {1, 2, 4, 3, 6, 5};
    
52.         sort<size_t>(data);
    
53.         cout << data << endl;
    
54.     }
    
55.     {
    
56.         vector<size_t> data = {1, 2, 4, 3, 6, 5};
    
57.         sort<size_t>(data, less_t<size_t>());
    
58.         cout << data << endl;
    
59.     }
    
60.     {
    
61.         vector<size_t> data = {1, 2, 4, 3, 6, 5};
    
62.         sort<size_t>(data, [](const size_t &a, const size_t &b) {return a < b;});
    
63.         cout << data << endl;
    
64.     }
    
65.     {
    
66.         vector<size_t> data = {1, 2, 4, 3, 6, 5};
    
67.         sort<size_t>(data, greater_t<size_t>());
    
68.         cout << data << endl;
    
69.     }
    
70.     return 0;
    
71. }
    

复制代码

人造人

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

人造人

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

weekend2000

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

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

1. void selection_sort2(int *arr, int size) {
   
2.         for (int i = 0; i < size; i++) {
   
3.                 int min = i;
   
4.                 for (int j = i + 1; j < size; j++) {
   
5.                         if (arr[j] < arr[min]) {
   
6.                                 min = j;
   
7.                         }
   
8.                 }
   
9.                 // 判定是否需要交换
   
10.                 if (min == i) {
    
11.                         continue;
    
12.                 } else {
    
13.                         int temp = arr[i];
    
14.                         arr[i] = arr[min];
    
15.                         arr[min] = temp;
    
16.                 }
    
17.         }
    
18. }

复制代码

人造人

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
是选择排序的思路，但是你的遍历方式似乎并不是选择排序的最优解，因为其中有大量不必要的元素交换，感 ...

因为其实懒得写啦