排序算法–冒泡排序

冒泡排序时间复杂度是O(N^2)

在有序的时候会优，在乱序的时候消耗的时间很多

1、冒泡排序基本思想：
         通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比较，若发现前一个数大于后一个数则交换，使值较大的元素逐渐从前移向后部，就如果水底下的气泡一样逐渐向上冒。

一趟冒泡就可以把最大的数放在数组的最后一个位置。

2、先以一个数组讲解一下，然后再写代码：
      待排序数组：3，9，-1，10，20
       第一轮排序：
        （1）3，9，-1，10，20      ----3跟9比较，不交换

        （2）3，-1，9，10，20      ----9比 -1大，所以9跟 -1交换

        （3）3，-1，9，10，20      ----9跟10比较，不交换

        （4）3，-1，9，10，20      ----10跟20比较，不交换

           第一轮过后，将20这个最大的元素固定到了最后的位置。

           在第二轮的时候20不参与冒泡。

       第二轮排序：
            因为20的位置已经固定，所以只对前4个进行排序即可：

        （1）-1，3，9，10，20      ----3比 -1大，进行交换

        （2）-1，3，9，10，20      ----3跟9比较，不交换

        （3）-1，3，9，10，20      ----9跟10比较，不交换

            第二轮过后，将第二大的元素固定到了倒数第二个位置

       第三轮排序：
            10和20的位置已经确定，只需对前三个进行排序

        （1）-1，3，9，10，20      ----3和-1比较，不交换

        （2）-1，3，9，10，20      ----3和9比较，不交换

            第三轮过后，将第三大的元素位置确定

       第四轮排序：
            只对前两个元素进行排序

        （1）-1，3，9，10，20      ----3和-1比较，不交换

       第四轮过后，将第四大的元素位置确定，此时总共5个元素，已经排序好4个，从而最后一个自然而然就是排好序的了

小结：
设总的元素个数为n，那么由上边的排序过程可以看出：

（1）总计需要进行（n-1）轮排序，也就是（n-1）次大循环

（2）每轮排序比较的次数逐轮减少

（3）如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序

（4）时间复杂度是O(N^2)      在有序的时候，很快，因为有exchange变量优化了代码

         在乱序的时候很慢很慢。

#include<stdio.h>
void PRINT(int* a,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//冒泡排序
void BubbleSort(int* a, int n)
{
	int end = n - 1;//不能是n，不然会越界
	while(end)
	{
		int exchange = 0;//优化，比较之后没有交换，说明已经排好了，就break循环
		for (int i = 0; i < end; i++)
		{
			if (a[i] < a[i + 1])
			{
				swap(&a[i], &a[i + 1]);
				exchange++;
			}
		}
		if (exchange == 0) break;
		end--;
	}
}
int main()
{
	int arr[] = { 5,1,2,6,7,8,92,4,3,5 };
	int n = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, n);
	PRINT(arr, n);
}