校招算法之冒泡排序的优化

      冒泡排序算法的基础见：冒泡排序。但是冒泡排序的复杂度最好的情况是O(n)，这种情况是怎么出现的呢？

      这就是冒泡排序的优化。原理：设定一个标志值（flag），判断此时排序是否已经完成不需要再次排序。

       C++版代码：

#include<iostream> using namespace std; void bubbleSort(int* bubble,int num); int main() { int num;//输入排序数组大小 cout << "please inputh the num:" ; cin >> num; cout << endl; int * bubble = new int[num]; cout << "please input the integers:" << endl; for (int i = 0; i < num; i++) cin >> bubble[i]; bubbleSort(*&bubble,num); for (int i = 0; i < num; i++) { cout << bubble[i] << endl; } system("pause"); delete[]bubble; return 0; } void bubbleSort(int* bubble,int num) { int swap_value = 0; int temp = 0; int flag = 1;//标志 for (int i = 0; i < num&&flag; i++)//判断需要仍要遍历吗 { flag = 0; for (int j = 0; j < num - i - 1; j++) { if (bubble[j]>bubble[j + 1]) { temp = bubble[j]; bubble[j] = bubble[j + 1]; bubble[j + 1] = temp; flag = 1; } } } }

       注意bubbleSort是稳定的呢，相同的元素是不会交换相对位置。同时java版的可以自己实现。