C++冒泡排序（包含初级、正宗及改进三种实现）

系统管理员 2022-06-14 20:43 178阅读 0赞

\#include <iostream>  
using namespace std;  
\#define MaxSize 10  
typedef struct   
\{  
int r\[MaxSize+1\];  
int length;  
\}SqList;  
void swap(SqList \*L,int i,int j)  
\{  
int temp=L->r\[i\];  
L->r\[i\]=L->r\[j\];  
L->r\[j\]=temp;    
\}  
//冒泡初级版  
/\*void BubbleSort(SqList \*L)  
\{  
int len=L->length;  
for(int i=0;i<len;i++)  
 \{  
for(int j=i+1;j<len;j++)  
\{  
if(L->r\[i\]>L->r\[j\])  
                swap(L,i,j);  
\}  
 \}  
\}\*/  
//冒泡正宗版  
/\*void BubbleSort(SqList \*L)  
\{  
int len=L->length;  
for(int i=0;i<len;i++)  
 \{  
for(int j=len-2;j>=i;j--)    //注意这里一定是j=len-2，自己可以分析一下  
\{  
if(L->r\[j\]>L->r\[j+1\])  
                swap(L,j,j+1);  
\}  
 \}  
\}\*/  
//冒泡排序优化版  
void BubbleSort(SqList \*L)  
\{  
int len=L->length;  
bool flag=true;                  //和正宗的冒泡排序相比，这里增加了一个标记变量flag  
for(int i=0;i<len&&flag;i++)     //若flag为false，则退出循环，说明已经有序了  
 \{   
flag=false;  
for(int j=len-2;j>=i;j--)    //注意这里一定是j=len-2，自己可以分析一下  
\{  
if(L->r\[j\]>L->r\[j+1\])   //只要有一次数据交换，flag就会为true，否则为初始的false  
                \{  
      swap(L,j,j+1);  
      flag=true;  
   \}   
\}  
 \}  
\}  
//冒泡排序时间复杂度分析  
//当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据改进的代码，可以推断出就是n-1次的比较  
//没有数据交换，时间复杂度为O(n)。当最坏的情况，即待排序表是逆序的情况，此时需要比较1+2+3+...+（n-1）=n\*（n-1）/2次，  
//并作等数量级的记录移动。因此，总的时间复杂度为O(n\*n)。  
void main()  
\{  
   SqList L;  
   SqList \*p=&L;  //定义P为指向SqList数据类型的指针变量，并指向L  
   cin>>L.length;  
   for(int i=0;i<L.length;i++)  
    \{  
  cin>>L.r\[i\];  
    \}   
   BubbleSort(p); //或BubbleSort(&L)  
   for(int j=0;j<L.length;j++)  
    \{  
cout<<L.r\[j\]<<" ";  
    \}  
\}