冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：
比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
分类--------------内部比较排序
数据结构----------数组
最差时间复杂度---- O(n^2)
最优时间复杂度----如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
平均时间复杂度---- O(n^2)
所需辅助空间------ O(1)
稳定性------------稳定
#include
usingnamespacestd;
voidexchange(intA[],inti,intj)//交换A[i]和A[j]
{
inttemp = A[i];
A[i] = A[j];
A[j] = temp;
}
intmain()
{
intA[] = {6,5,3,1,8,7,2,4};//从小到大冒泡排序
intn =sizeof(A) /sizeof(int);
for(intj =0; j < n -1; j++)//每次最大元素就像气泡一样"浮"到数组的最后
{
for(inti =0; i < n -1- j; i++)//依次比较相邻的两个元素,使较大的那个向后移
{
if(A[i] > A[i +1])//如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
{
exchange(A, i, i +1);
}
}
}
printf("冒泡排序结果：");
for(inti =0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
return0;
}
网友评论