经典排序算法-----冒泡排序（C语言实现）

算法描述：

冒泡排序是一种较为简单的排序算法，其基本思想为从头开始依次比较相邻的两个元素大小，将较大（较小）的元素移至右端，最终使最大（最小）的元素移至序列最后，再次重复上述过程，直到最终序列完全有序为止。

算法执行过程分析：

例如：有一行数分别是26、10，83，56，28，66，7 说明：按照从小到大的顺序进行排序，方框数为比较的次数，以下图示为比较完交换的结果。

(1)第一躺排序：

此时已将此行数中最大的那个数字放在末尾。 (2)第二躺排序：

此时将倒数第二大的数字放在后面。 (3)第三趟排序：

此时将倒数第三大的数字放在后面。 以此类推，可以得到最终结果为：7、10、26、28、56、66、83。 备注：n个数要比较n - 1趟，第一躺比较n - 1次，第 j 趟需要比较n - j 次。

在分析完上述过程之后，下面给出具体的代码实现：

void Bubble_Sort(int *arr,int len) //其中len是数组的长度 { for(int i = 0;i < len - 1;i++) //i表示趟数 { for(int j = 0;j < len-i-1;j++) //j表示次数 { //如果相邻两个数，前一个数大于后面那个数则进行交换，将大数右移 if(arr[j] > arr[j+1]) { int temp; //交换 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }

以上代码是在给出任意一个无序的序列基础上进行排序。计算的出其时间复杂度为O（n^2）。那如果给出的序列自身本身就有序呢？通过对以上代码的分析发现，如果序列自身有序的话，则只需要对序列进行一趟遍历，此时的序列就是有序的。至于后面的比较完全就是效率上的浪费。对此，对上述代码进行优化。

void Butter_Sort2(int *arr,int len) { bool swap = false; //设置一个标志位 for(int i = 0;i < len - 1;i++) //i表示趟数 { for(int j = 0;j < len-i-1;j++) //j表示次数 { if(arr[j] > arr[j+1]) { int temp; //交换 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; swap = true; //标志位置为true } } if(!swap) //当一次躺比较没有一次进入第一个if语句时，才会 { //进入到这个if语句，说明此时序列已经是有序数列 return; } } }

此时计算在序列自身有序的基础上其时间复杂度为O（n）。

总结：

总的来说冒泡算法是一种较为简单的排序算法。在有序情况下其时间复杂度为O（n^2）,在无序情况下其时间复杂度为O（n）。由于算法中借助了temp进行交换，因此其空间复杂度为O（1）。冒泡排序算法是一种稳定的排序算法。