冒泡排序 - C++分析实现

 

冒泡排序：

 

 

 

 

 

◆实例：农民选种子的时候会把所有的种子放到水里，颗粒饱满的下沉 ，颗粒不饱满的漂到上面这类似于一种冒泡排序。

 

 

 

 

 

 

 

◆特点：1：每次只能比相邻的两个元素

（a[i]<a[i+1]）相比

2：如果顺序不合适就交换

 

 

 

 

 

☞：　适合少量数据的情况，如果乱序　数据量大　最好不要用

 

 

 

 

 

 

 

◆:算法描述：

 

 

1：一轮比较所有相邻数据，如果顺序不对就发生交换； =>for(`````````````)

 

 

 

2：本轮只要发生了交换、就再来一轮如果没有发生交换排序成功。　 =>先做后判断所以适合dowhile

 

 

 

 

 

 

　3: 算法优化，每次可以少比较一个比较的个数减一：

 

 

 

 

 

 

 

 

 

 

 

 

◆：代码：

#include <iostream> 
#include <ctime> 
using namespace  std; 
//算出运算所用事件 
 
//定义 BubbleSort 方法   
typedef  int    T; 
void    BubbleSort (T*  arr, int num) 
{ 
     //比较一组数据 如果出现了交换 则继续排序  直到没有出现则表示排序成功 
        //=> do while循环 
//定义标记 每一次循环的比较 
        bool    bDoSwap = false;  // 
    do { 
        bDoSwap = false; //每次循环设置默认为没有发生交换 
        //循环遍历 
        for ( int i =0; i<num-1; i++) 
        { 
            //大的后移 
            if(arr[i] > arr[i+1]) { 
                swap(arr[i], arr[i+1]); 
                //修改标记 
                bDoSwap = true; 
            } 
        } 
        //算法优化  令num - 1  因为每次比较结束后  最后一个是最大的 所以最后一个无需再次比较 
         num--; 
    }while(bDoSwap); 
} 
     
 
int main() 
{ 
    cout << "冒泡排序:"<<endl; 
 //定义102400长度的数组 越长越能计算所需世间   赋值 
    const int kNum = 10240; 
    T arr[kNum]; 
    for (int i=0; i<kNum; i++) 
    { 
        arr[i] = kNum - i; 
    } 
    time_t tStart = time(NULL); 
    BubbleSort(arr, kNum); 
    time_t tEnd = time(NULL); 
     
    cout<<"require time:"<<tEnd-tStart <<endl; 
    //打印前十个看看是否完成排序 
    for(int i =0; i<10; i++) 
    { 
        cout<<arr[i]<<"     "; 
    } 
    system("pause"); 
    return 0; 
 
} 

 

结果：