改进后的冒泡排序
/***改进冒泡排序的两个做法 冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 ***/ 现在让我们来提升算法的效率：首先来看一个例子：41 67 34 0 69 24 78 58 62 64第一趟排序为 41 34 0 67 24 69 58 62 64 78第二趟排序为 34 0 41 24 67 58 62 64 69 78第三趟排序为 0 34 24 41 58 62 64 67 69 78第四趟排序为 0 24 34 41 58 62 64 67 69 78每趟排序的结果是最大数移动到最后一个位置：（1）根据此结果我们每次比较之后都可以为下一次减少一次比较，因为最大数已经沉底，所以最后一位就不用比较了。因此在内层循环中我们每次都可以减少一次循环。（2）根据冒泡排序的思想本来按道理是要比较 n-1趟的 上诉的例子为9趟。但是在第四趟中就已经排序完成。如果在继续下去就等于做无用功了，因此我们可以再第四趟排序中就可以退出循环了，所以我们可以增加一个变量 bool flags=true;将其初始化为true，当发生数据的交换时候就赋予false值。如果在本趟排序中就没有发生一次交换则就在外层循环中跳出去。 一个完整的例子：/////////////////////////////////////sort .h filetemplate<typename type>void Swap(type &p,type &q){ type temp=p; p=q; q=temp;}//由小到大进行排序 template<typename type>void bubbling_sort(type a[],int n){ int i,j; bool flags=true; for( i=0; i < n-1; i++ ) { for( j=0; j < n-1-i; j++ ) { if( a[j] > a[j+1] ) { Swap(a[j],a[j+1]); flags=false; } } if( flags ) break; else flags=true; }} //////////////////////////////////////////////////main.cpp file#include <cstdlib>#include <iostream>#include "sort.h"using namespace std;int main(int argc, char *argv[]){ int a[10]; int n; cout<<"排序前"<<endl; for( int i=0;i<10;i++ ) { n=rand()%100; a[i]=n; cout<<a[i]<<" "; } cout<<endl; cout<<"排序后"<<endl; bubbling_sort(a,10); for( int j=0;j<10;j++ ) cout<<a[j]<<" "; cout<<endl; cout << "Press the enter key to continue ..."; cin.get(); return EXIT_SUCCESS;} ?
Arrays.sort()是在Java中，不知道C++有木有 Arrays.sort()是在Java中，不知道C++有木有