首页 > 代码库 > 数据结构之冒泡排序

数据结构之冒泡排序

2024-07-15 02:46:10   222人阅读

1.冒泡法原理

原理很简单每一趟排序将最大的或者最小的数往后移动，知道一趟排序过程中没有数据交换为止。

例如：一个序列有n个数据a1，a2……an,第一趟排序为：首先a1和a2比较，如何逆序则交换位置，然后a2,a3比较，以此类推an-1和an比较。然后进入第二趟排序排序的范围为a1~an-1...第3 ，第4.……直到一趟排序过程中没有发生数据交换则停止。

2.冒泡法代码

main.cpp

 1 #include <stdio.h> 2 #include <stdlib.h> 3  4 #define INIT  10000 5 #define INCRENMENT 100 6  7  8 //顺序列表结构体 9 typedef struct List{10     int *elem;//基地址11     int length;//顺序列表的长度12     int size;//总长度13 }List;14 //列表初始化15 void init(List &L)16 {17     L.elem=(int*)malloc(sizeof(int)*INIT);18     L.length=0;19     L.size=INIT;20     printf("初始化成功\n");21 }22 //显示列表数据23 void print(List L)24 {25     for(int i=1;i<=L.length;i++)26         printf("%d\t",L.elem[i]);27     printf("\n");28 29 }30 //插入新数据31 void insert(List &L,int i)32 {33     if(L.length>=L.size)34     {35         L.elem=(int*)realloc(L.elem,sizeof(int)*(L.size+INCRENMENT));36         if(!L.elem)37         {38             printf("内存分配不足\n");39             exit(-1);40 41         }42         L.size+=INCRENMENT;43     }44     L.elem[++L.length]=i;45     //printf("%d插入完毕\n",i);46 47 }48 void BubbleSort(List &L,int &compareCount,int &changeCount)49 {50     bool change;51     int c=0;//比较次数52     int d=0;//交换次数53     for(int i=L.length,change=true;change && i>0;i--)54     {55         change=false;56         for(int j=1;j<i;j++)57         {58             c++;59             if(L.elem[j]>L.elem[j+1])60             {61                 int temp=L.elem[j];62                 L.elem[j]=L.elem[j+1];63                 L.elem[j+1]=temp;64                 change=true;65                 d++;66             }67 68         }69         compareCount=c;70         changeCount=d;71     }72 }73 int main()74 {75     List L;76     init(L);77     for(int i=1;i<=10;i++){78         insert(L,i*239%99);79     }80     printf("初始化10个随机数据\n");81     print(L);82     printf("排序完后数据\n");83     int c,d;84     BubbleSort(L,c,d);85     printf("比较次数=%d，交换次数=%d\n",c,d);86     print(L);87     return 0;88 }

3.运行结果

4.冒泡法效率分析

如果初始序列为“正序”的话，需要比较n-1次；如果初始序列为“逆序”的话，则需要比较n(n-1)/2次，然后交换移动相应的次数，因此冒泡排序的算法的时间复杂度为O(N^2)

最差情况O(n^2),最好情况O(n)

 


联系
我们