2019-05-17：什么是冒泡排序？如何优化？

[Moosphan]

No description provided.

[whatshappen]

你猜？😏
.
.
.
.
.
.

通过一个标识符，判断内层循环，循环结束时没有进行数据交换操作，表示已经有序，结束循环

[zwonb]

你猜？😏
.
.
.
.
.
.

通过一个标识符，判断内层循环，循环结束时没有进行数据交换操作，表示已经有序，结束循环

你猜我猜不猜

[zhaoerlei1989]

冒泡排序算法原理：（从小到大排序）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，交换一趟后，最后的元素会是最大的数
3.针对所有的元素重复以上的步骤，除了最后一个
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

优化方案1（定义一个变量l来保存一趟交换中两两交换的次数，如果l==0,则说明排序已经完成，退出for循环）
优化方案2（假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了）
定义一个变量n来保存一趟交换中最后一次发生交换的位置，并把它传递给下一趟交换

[xianfeng92]

冒泡排序算法原理：（从小到大排序）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，交换一趟后，最后的元素会是最大的数
3.针对所有的元素重复以上的步骤，除了最后一个
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

优化方案1（定义一个变量l来保存一趟交换中两两交换的次数，如果l==0,则说明排序已经完成，退出for循环）
优化方案2（假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了）
定义一个变量n来保存一趟交换中最后一次发生交换的位置，并把它传递给下一趟交换

很棒～

[guosen]

/**
 * 排序思想:
 * 对一组数字进行从小到大或者从大到小的进行排序。
 * 它是通过让相邻的两个元素进行比较，大的元素向下沉，小的元素向上冒
 * arr[0]与arr[1]进行比较，如果前者大于后者，则交换位置
 * 然后arr[1]与arr[2]进行比较，以此类推。当进行到n-1轮后，排序完成。
 */
import java.util.Arrays;
public class Sort {

    public static void main(String[] args){

        int arr[]= {100,90,101,23,13,75};
        int temp=0;
        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]) {
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
            }
            System.out.println("第["+(i+1)+"]轮，排序结果:"+ Arrays.toString(arr));
        }
        System.out.print("================================");
        int arr2[]= {100,90,101,23,13,75};
        sort2(arr2);
    }

    /**
     * 优化思路：
     * 假如在第1轮比较当中，发现所有的元素都没有进行交换，则说明此原数据就是有序的，不需要再进行排序
     * @param arr
     */
    public static void sort2(int arr[]){

        int temp=0;
        int flag=0;
        for(int i=0;i<arr.length-1;i++) {
            flag=0;
            for(int j=0;j<arr.length-1-i;j++) {
                if(arr[j]>arr[j+1]) {
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                    //如果有交换的行为,则flag=1
                    flag=1;
                }
            }
            //说明上面 内for循环中，没有交换任何元素。
            if(flag==0) {
                break;
            }
            System.out.println("第["+(i+1)+"]轮，排序结果:"+Arrays.toString(arr));
        }

    }
}

[xianfeng92]

有在实践中应用过冒泡排序的吗？

[gabyallen]

冒泡排序：
1.相邻两个元素进行比较，大的元素往下沉，小的元素往上冒。
2.index[i]与index[i+1]进行比较，大的数据在下；小的数据在上；
反复进行比较；直到index[n-1]结束。

[LvKang-insist]

冒泡排序：
首先计算长度。
有两层循环。第一层循环控制比较的趟数，第二层则进行比较。
比较规则如下：
第一个元素和后面的元素挨个比较。完成之后，就是第二个元素和后面元素依次进行比较。知道倒着第一个和倒着的第二元素比较完后， 排序结束.

int[] ints = {52,7,2,9,1,7,653,1,47,55,5};
for (int i = 0; i < ints.length; i++) {
for (int j = i; j < ints.length; j++) {
if (ints[i] > ints[j]){
int temp = ints[i];
ints[i] = ints[j];
ints[j] = temp;
}
}
}

[azhon]

冒泡排序图解

[yangfanggang]

上图 很形象啊

打卡打卡

[ADrunkenLiBai]

很形象，打卡

[GitChenM]

打卡，上图点赞

[yline]

首先冒泡排序，每次都与前一个进行比较，然后交换。所以，它的时间复杂度是：4*O(n^2)
重点解释一下这个常数，它是每次比较以及交换所消耗的次数。

对冒泡排序最直接的优化是：“插入排序”；它的思想是，假设【0，k，n】当前位置是k，那么【0，k-1】是有序的，k在【0，k-1】中的某一个位置插入，假设位置是i，则将【i，k】往后搬移即可。它的时间复杂度是：O(n^2)
因为，它不需要比较然后交换，所以常数系数要小很多。作为同是稳定的排序算法，插入排序比冒泡排序效率高3.5倍左右（有人测试过）

对冒泡排序还有其它的优化方式，但原理已经相差比较大了。例如：并归排序、快速排序、堆排序

另外说明：记录一个flag，满足条件退出，并不算算法上的优化。