【算法系列】排序算法（1）冒泡排序

“排序”在数据处理中经常都会看到，它作为数据结构和算法中的重要组成部分，还是需要我们系统地进行学习。

对于排序的认知，我一直都处于就是对数据进行由大到小或者由小到大的排序，但具体是怎样进行的，却一直都没办法描述清楚，希望通过这次深入的学习，可以掌握更多关于排序的认知。

以下学习内容是学习多个网站博主的一些摘抄内容，非个人总结，若有侵权，联系博主进行删除，多处转载网址如下：

1.程序员内功：八大排序算法 http://cuijiahua.com/blog/2018/01/alogrithm_9.html

2.排序算法学习总结 http://blog.csdn.net/cauchyweierstrass/article/details/49948091

1、排序的概念

排序，其目的就是将一组“无序”的记录序列调整为“有序”的记录序列。

它分为内部排序和外部排序。 若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序。 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

2、排序分类

八大排序算法均属于内部排序。如果按照策略来分类，大致可分为：交换排序、插入排序、选择排序、归并排序和基数排序。如下图所示：

3、算法分析

下表给出各种排序的基本性能：

下面开始各个算法的学习，对于每种排序算法，需要理解以下问题： 1、算法思想是什么 2、时间复杂度 3、稳定性 4、什么情况下使用？

排序（1）冒泡排序

一、前言

冒泡排序是一种交换排序。

交换排序就是两两比较待排序的关键字，并交换不满足次序要求那对数，直到整个表都满足次序要求为止。

二、算法思想

从第一个元素开始，重复走访需要排序的数列，每次比较相邻的两个元素，若顺序错误则进行交换，直到数列结束开始下一轮。

当数列中的元素全部遍历之后排序完成，算法结束。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。

时间复杂度： O(n^2)，改进后再最好情况下达到O(n)

稳定性： 稳定

适用场景： 比较元素较少时都可以使用。

三、代码

/* 排序（1）冒泡排序 Time：2018-02-18 Author：Stella Chen Content： A simple example about Bubble Sort */ #include<stdio.h> #define N 10 int main() { int ary[10] = { 10,2,3,1,5,15,7,9,20,11 }; int t; printf("The original sequence:\n"); for (int i = 0; i < N; i++) printf("%d ", ary[i]); printf("\n\n"); //N-1轮完成排序 for (int i = 0; i < N-1; i++) { printf("第%d趟排序：\n",i+1); //每轮比较N-1-i个，因为已经排好的最后i个不用比较 for (int j = 0; j < N-1-i; j++) { printf("排序中："); if (ary[j+1] < ary[j]) { t = ary[j+1]; ary[j+1] = ary[j]; ary[j] = t; } for (int i = 0; i < N; i++) printf("%d ", ary[i]); printf("\n"); } printf("排序结束：\n"); for (int i = 0; i < N; i++) printf("%d ", ary[i]); printf("\n\n"); } return 0; }

运行结果:

四、优化

从上面的例子可以看出来，当数列已经正序时，排序仍将继续进行全扫描。所以，对冒泡排序的改进方法是加入**标志性变量flag**，用于标记某一趟排序过程中是否有数据交换。

如果进行**某一趟排序时没有进行数据交换，则说明所有数据已经有序**，可立即结束排序，避免不必要的比较过程。

从上面的例子可以看出来，当数列已经正序时，排序仍将继续进行全扫描。所以，对冒泡排序的改进方法是加入**标志性变量flag**，用于标记某一趟排序过程中是否有数据交换。

如果进行**某一趟排序时没有进行数据交换，则说明所有数据已经有序**，可立即结束排序，避免不必要的比较过程。

**代码如下：**

//优化后，加入flag #include<stdio.h> #define N 10 int main() { int ary[10] = { 10,2,3,1,5,15,7,9,20,11 }; int t; printf("The original sequence:\n"); for (int i = 0; i < N; i++) printf("%d ", ary[i]); printf("\n\n"); //N-1轮完成排序 for (int i = 0; i < N - 1; i++) { int flag = 1; //进行标记 printf("第%d趟排序：\n", i + 1); //每轮比较N-1-i个，因为已经排好的最后i个不用比较 for (int j = 0; j < N - 1 - i; j++) { printf("排序中："); if (ary[j + 1] < ary[j]) { t = ary[j + 1]; ary[j + 1] = ary[j]; ary[j] = t; flag = 0; //进行了数据交换 } for (int i = 0; i < N; i++) printf("%d ", ary[i]); printf("\n"); } printf("排序结束：\n"); for (int i = 0; i < N; i++) printf("%d ", ary[i]); printf("\n\n"); if (flag) break; } return 0; }

运行结果：