冒泡排序 两次优化
(1)bubble sort的定义是：进行n-1次排序，每次排序都要比较所有相邻的两个元素，但第i次排序时array尾部的i-1个元素都是排序好的，所以内层循环的长度是n-i。算法实现如下
[java]
void bubbleSort( int array[]) {
for (int i = 1; i < array. length; ++i ) {
for (int j = 0; j < array. length - i ; ++j) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
(2)一次优化。我们可以想到这种极端情况：array本身就是排序好的，但是依照如上算法，我们仍然要遍历n平方/2次。原因在于，我们没有机制检查数组是否是排序好的。解决办法就是加入标识项，如果发现一次内层循环没有经过任何交换，则说明array已经排序完毕。算法实现如下：
[java]
void bubbleSort( int array[]) {
boolean exchange = false ;
for (int i = 1; i < array. length; ++i) {
for (int j = 0; j < array. length - i; ++j) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
exchange = true;
}
}
if (!exchange) {
break ;
}
}
(3)二次优化。我们再想象一种极端情况：array长度为n，但是只有0,1元素未排序，那么依照上一种优化算法我们依然要遍历2*n次。原因在于我们内层循环长度的设定依据是，i次排序array的后i-1个元素是排序好的，但实际上i次排序的循环长度取决于i-1次排序时最后的交换位置，例如i-1次排序的最后交换位置是index，则表明index之后的元素都已经排序完毕，我们只需要记录这个Index就得到了下次(i次)的循环长度。算法实现如下：
[java]
void bubbleSort( int array[]) {
boolean exchange = false;
int index = 0;
int mark = array.length - 1;
for (int i = 1; i < array. length; ++i) {
for (int j = 0; j < mark; ++j) {
if (array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
exchange = true ;
index = j;
}
}
if (!exchange) {
break ;
}
mark = index;
}
summary:
当然这种所谓的优化知识学院派的说法，实际工作中自己的水准在哪个级别上全靠自己。例如我本身就是个菜鸟，所以我向来只是停留在定义级别的bubble sort上。当然，学习的动力也来源于此。比如说这次学习、总结之后，也许还不能够一下子上升到quick sort的级别，但是起码可以把优化后的bubble sort运用到工作中去。
补充：软件开发 , C++ ,
