【排序算法】冒泡排序

一、定义：

冒泡排序（Bubble Sort）是一种简单直观的算法>排序算法。重复走访过要排序的元素列，相邻的元素依次比较将无序的一组数据变成有序（升序或者降序）。走访元素的工作是重复地进行，一直到没有相邻元素可以进行交换，此时该元素列已经排序完成。（对于冒泡排序主要是具有教学意义，新手入门）

二、原理：

如果要将数据从小到大排序（升序），我们从第一个元素与相邻的元素比较（下一个和前一个比较），如果第一个元素大于第二个元素，则2个元素发生交换，如果小于则不动；然后接着是第二个元素和后一个元素比较，依次类推。（紧挨着比较）到在最后一个元素时，最大的元素会被放到最后一位。此时最后一位就是最大的元素，排好了一个元素，这个过程也可以称为一趟。然后接着冒泡，此时n-1个数据中会剩下一个第二大元素的，通过上述过程就会将其放到数组的倒数第二个位置，依次类推；当进行了n-1趟时，顺序也就排好了，所以冒泡排序说只要进行n-1趟排序

总结：就是相邻的2个元素两两进行比较！！！！满足情况进行交换

动图：更直观的了解冒泡的机制

每一趟的结果，还有右侧走一趟的过程

其实你写n趟也没关系，因为第n趟不会再动了，已经有序了，从上图也能看出来！！

三、时间复杂度:

时间复杂度是算的这个程序最坏的情况：当这个数组为逆序数组时，整个数组全部都要遍历进行比较；最坏的情况：O(N^2)

最好的情况：当然就是这个数组已经有序了为O(N); 这里有人会觉得是O(1),但是你不要想当然的看出来就是有序了不用走，还是要走完n-1趟的，要遍历一下，让计算机去确认

四、代码：

有2层循环，先看内部的，j从1开始（j=0也可以，但是要注意不要越界，也就比较的时候）去和前一个元素比较，j<n-i是因为最后一个会放入最大值，然后下一趟接着是找到第二大的元素，要放入倒数第二个位置，所以j的范围根据趟数在不断减小；外层循环是也就是用来控制趟数的；

//冒泡排序：
void BubbleSort(int* a, int n)
{int i;for (i = 0; i < n - 1; i++){//从前往后冒泡，第一趟最后一个为最大值；只要n-1趟即可for (int j=1; j < n-i; j++){if (a[j] < a[j - 1]){int tmp = a[j];a[j] = a[j - 1];a[j - 1] = tmp;}}}}

冒泡排序的优化：

其实，上面的冒泡排序是基于最坏的情况是要走n-1趟写的，但是当走到某一趟不会发生变化了以后（不会发生交换了），后面循环比较已经没有意义了，因为此时此刻已经有序了，所以为了减少消耗，我们可以将代码进行优化：设置一个flag做标记，当内循环（比较）一次也没有进行时就打破循环。

//冒泡排序：
void BubbleSort(int* a, int n)
{int i;for (i = 0; i < n - 1; i++){//若是某趟没有进行交换，此时已经排好序了int flag = 0;//从前往后冒泡，第一趟最后一个为最大值；只要n-1趟即可for (int j=1; j < n-i; j++){if (a[j] < a[j - 1]){int tmp = a[j];a[j] = a[j - 1];a[j - 1] = tmp;flag = 1;}}if (flag == 0){break;}}}