咱们在学 C 语言的时候, 学过冒泡排序, 请参考小朋友学 C 语言 (26): 冒泡排序:https://www.jianshu.com/p/587ff823ba5b
大话数据结构第九章, 讲了一种优化的冒泡排序, 完整代码如下:
- #include<iostream>
- using namespace std;
- #define MAX 5
- typedef struct
- {
- int r[MAX + 1];
- int len;
- }seq;
- void myswap(seq *x, int i, int j)
- {
- int temp = x->r[i];
- x->r[i] = x->r[j];
- x->r[j] = temp;
- }
- void bubbleSort(seq *x)
- {
- bool flag = true;
- // i 表示第几轮比较, 不表示数组下标
- for (int i = 1; i <x->len && flag; i++)
- {
- cout <<"第" << i << "轮排序:";
- flag = false;
- // j 表示数组下标, 这里是从后往前比较, 能同时挪动多个, 提高了效率
- // 比如,{3, 2, 1, 5, 4} 经过一轮比较变成 {1, 3, 2, 4, 5}
- for (int j = x->len - 1; j>= i; j--)
- {
- if (x->r[j]> x->r[j + 1])
- {
- myswap(x, j, j + 1);
- flag = true;
- }
- }
- for(int i = 1; i <= x->len; i++)
- {
- cout <<x->r[i] <<' ';
- }
- cout << endl;
- }
- }
- int main()
- {
- cout << "输入数据:";
- seq s;
- for(int i = 1; i <= MAX; i++)
- {
- cin>> s.r[i];
- }
- s.len = MAX;
- bubbleSort(&s);
- cout << "排序结果:";
- for(int i = 1; i <= s.len; i++)
- {
- cout << s.r[i] << ' ';
- }
- cout << endl;
- return 0;
- }
运行结果:
输入数据: 3 2 1 5 4
第 1 轮排序: 1 3 2 4 5
第 2 轮排序: 1 2 3 4 5
第 3 轮排序: 1 2 3 4 5
排序结果: 1 2 3 4 5
来源: http://www.jianshu.com/p/d264383673b5