冒泡排序法原理分析

冒泡排序法的原理解析

preface: 参考链接：【C语言】深入理解冒泡排序算法（优化+详解）_c语言冒泡排序程序-CSDN博客 | 【排序算法】史上最通俗易懂的【冒泡排序】详解-CSDN博客

正文

 C语言中，有两种排序方式，分别是选择排序和冒泡排序法。选择排序非常容易理解，就是从第一个位置开始，不断比较，放入第一大（二、三…）

for(int i = 0; i < n-1; i++){
	for(int j = i+1; j < n; j++){
	//交换
	//对 i —— j 交换
	}
}//选择排序

分析一下：i代表对第i个格子进行排序，然后将其与后面的未排序的数字j分别比较，并交换数值。i < n-1是因为前面n-1个排完了，那第n个自然也完了（当然，写i < n 也没问题

  那冒泡排序是什么呢？

冒泡排序的步骤：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
• 针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

我们可以发现，冒泡排序每次结束后，排序好的是从最后一位计数，并非选择排序上面的从第一位开始计数。

for (i = 0; i < n - 1; i++){
		for (j = 0; j < n - 1 - i; j++){
			// 排序
			// 对 j和j+1交换
		}
}

分析一下，冒泡排序是相邻元素交换，所以，只有j代表着格子数，而i代表着最大排序次数，因为每排序一次，最少有一个拍好，共n个元素，所以要循环n-1次（减1同选择排序）。i同时也代表目前有几个元素已经排好了（也就是限定了j的最大值，要小于n - i - 1）。

下面为引用的优化代码。

    //定义一个标志位，用于判定元素之间是否进行了交换
    boolean flag = false;
 
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                //进入这个if分支里边，则说明有元素进行了交换
                //所以将flag=true
                flag = true;
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        
        //在进行完一轮的排序之后，判断本轮是否发生了元素之间的交换
        //如果没有发生交换，说明数组已经是有序的了，则直接结束排序
        if (!flag) {
            break;
        } else {
            //如果发生了交换，那么在下一轮排序之前将flag再次置为false
            //以便记录下一轮排序的时候是否会发生交换
            flag = false;
        }
    }