冒泡排序及冒泡排序的优化算法
#include <iostream> using namespace std; int main() { int a[5]; for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cin >> a[i]; } for (int i = 0; i < sizeof(a) / sizeof(a[0]) - 1; i++) { for (int j = 0; j < (sizeof(a) / sizeof(a[0])) - i - 1; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << " "; } cout << endl; return 0; }进行初级优化，考虑当冒泡进行到后期时，我们可能数组已经有序，但冒泡仍会继续，所以对他进行优化，加入额外标志位，在外层循环使用flag变量，如果在内部循环中发生了交换，我们就认为是循环尚未结束，此时更新flag的值，当某次循环进行时，未发生交换，也就是flag值没有更新，我们就认为是此时数组已经有序，可以推出冒泡
#include <iostream> using namespace std; int main() { int a[5]; int flag; for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cin >> a[i]; } for (int i = 0; i < sizeof(a) / sizeof(a[0]) - 1; i++) { flag = 1; for (int j = 0; j < (sizeof(a) / sizeof(a[0])) - i - 1; j++) { if (a[j] > a[j + 1]) { flag = 0; int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } if (flag) { break; } } for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << " "; } cout << endl; return 0; }上面我们已经得到了一个较优的冒泡排序，接下来继续思考我们是否存在在冒泡排序的过程中出现的部分有序情况，我们在交换完后，后边数据可能已经有序，但我们仍要将冒泡进行到底，所以我们看考虑能否找到每一趟排序之后的乱序数组和有序数组之间的分界线
#include <iostream> using namespace std; int main() { int a[5]; int flag; //用于标识数组是否优秀 int borderIndex = 0; //寻找边界元素 int cnt = sizeof(a) / sizeof(a[0]); //计算数组长度 int lastExchange = cnt - 1; //记录最后交换位置 for (int i = 0; i < cnt; i++) { cin >> a[i]; } for (int i = 0; i < cnt - 1; i++) { flag = 1; for (int j = 0; j < lastExchange; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = 0; borderIndex = j; } } lastExchange = borderIndex; if (flag) { break; } } for (int i = 0; i < cnt; i++) { cout << a[i] << " "; } cout << endl; return 0; }