兰州市城市建设设计院官方网站公共服务平台官网

1.冒泡排序(Bubble Sort)

较简单排序算法。

它会遍历若干次要排列的数列，每次遍历，会从前往后比较相邻两个数的大小。

如果前者比后者大，就交换他们位置。遍历一次最大元素在数列末尾。重复直到数列有序。

那么遍历需要一个变量控制范围。一个变量需要在这个范围里控制相邻元素进行比较。将最大的数作为有序数，在进行下一趟

比较就把它"踢出"遍历范围。如此一来，每个"它"都是作为"它"那次遍历的最大数,最后实现有序。

#include<stdio.h>
swap(int* x,int* y)
{int temp;temp = *x;*x = *y;*y = temp;
}
void bubble_sort(int* a, int n)
{int i, j;int flag;for (i = n - 1; i > 0; i--){flag = 0;//标志for (j = 0; j < i; j++){if (a[j] > a[j + 1]){swap(&a[j], &a[j + 1]);flag = 1;//交换，标志设为1}}if (flag == 0){break;//没发生交换，已有序}}
}
void main()
{int str[] = {2,3,4,10,9,8,7,6,5,1};int zf = sizeof(str) / sizeof(str[0]);bubble_sort( str, zf);int i;for (i = 0; i < zf; i++){printf("%3d",str[i]);}
}

2.冒泡排序的时间复杂度和稳定性

2.1冒泡排序的时间复杂度是O(n^2)。

排序算法中有两个for循环。

每个for循环的次数都是n。用数组下标表示范围就是（0，9）

2.2冒泡排序稳定性

它稳定，满足稳定算法定义。

算法稳定性：假设数列中存在a[i]=a[j];若在排序之前，a[i]在a[j]之前，排序后，a[i]还在a[j]之前，那这个算法就是稳定的!