算法基础：排序算法：冒泡排序

冒泡排序是所有排序中最为人所知的排序大概毫不为过，因为其名称中就包含了算法的主要思路，这篇文章介绍一下冒泡排序的主要要点和实现以及简单的优化思路。

算法思路

• 冒泡排序顾名思义，升序排序的时候小的元素像气泡一样一个一个的浮上去，对于N个元素，通过两层循环来完成排序，外层循环N-1次，下标用来记录已排序的元素的位置，升序的要求下每次获取当次排序中的最小值，并将其排在已排序的最后一个。内层循环使用临位相比的方法来确定是否需要进行交换，在内层循环中保证外层循环的当前下标中保存的是当前剩余元素中的最小元素。

算法要点

冒泡排序的主要要点如下所示(N个元素，数组元素从0开始计数)：

• 外层循环：0 <= i < N - 1 (N-1次循环) 递加方式循环即可
• 内层循环：i + 1 <= j <= N - 1 使用降序方式从N-1开始递减模拟气泡上升
• 比较：内层循环如果是i+1为一端，比较元素的下标自然为i和i-1
• 交换：升序的情况下满足[i+1] > [i]的情况下，i+1位置的元素和i位置的元素内容互换

模拟实现

void bubble_sort(int* arr, int num) { for (int i=0; i<num-1; i++) { for (int j=num-1; j>=i+1; j--) { if (arr[j] < arr[j-1]) { int tmp = arr[j]; arr[j]=arr[j-1]; arr[j-1]=tmp; } } } } 

结果验证

加上打印和调用的示例代码，可以使用如下方式进行验证

#include  #include  #include  void bubble_sort(int* arr, int num) { for (int i=0; i<num-1; i++) { for (int j=num-1; j>=i+1; j--) { if (arr[j] < arr[j-1]) { int tmp = arr[j]; arr[j]=arr[j-1]; arr[j-1]=tmp; } } } } void print_array(int* arr, int num) { for (int i=0; i<num; i++) printf("%d ",arr[i]); printf("\n"); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { int* array = (int *)malloc(sizeof(int)*n); memset(array,0,sizeof(int)*n); for (int i=0; i<n; i++) { scanf("%d",&array[i]); } bubble_sort(array,n); print_array(array,n); free(array); array= NULL; } } 

执行结果示例

9
9 8 8 7 6 5 4 4 3
3 4 4 5 6 7 8 8 9

算法优化

冒泡算法还可以进行少许优化，考虑到输入的特殊情况，比如已经是有序的情况之下，还需要进行多次循环和判断，效率较低，引入一个变量的空间使用，用于判断是否已经是有序的，可以提高这种情况下的排序效率。代码稍作修改如下即可。

void bubble_sort(int* arr, int num) { int sorted_flag = 1; for (int i=0; sorted_flag; i++) { for (int j=num-1; j>=i+1; j--) { sorted_flag = 0; if (arr[j] < arr[j-1]) { int tmp = arr[j]; arr[j]=arr[j-1]; arr[j-1]=tmp; sorted_flag = 1; } } } } 

这种写法较为简洁：

• 在外层循环之外设置排序标志变量sorted_flag初值为1，以便首次外层循环能够开始
• 外层循环设定sorted_flag是否为1为外层循环结束条件
• 外层循环中上来就将此flag设定为0，如果内层循环发生了交换说明可能还需要进一步排序，如果没有交换发生，说明排序已经完成，即可退出，不再需要后续的无意义的对已排序的元素序列进行比较的过程