01.冒泡排序

冒泡排序

  • 1.基本思想
  • 2.排序过程
  • 3.代码实现
  • 4.如何优化
  • 5.复杂度
  • 6.使用场景

1.基本思想

  • 很好理解，从字面意思就知道类似于冒泡。在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
  • 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

2.排序过程

  • 比较相邻的两个数据，如果第二个数小，就交换位置。
  • 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好。
  • 继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
    • image
      image

3.代码实现

  • 如下所示
    public static void sort(int arr[]) {
	int length = arr.length;
	int temp;
	for(int i=0 ; i<length-1 ; i++) {
		for(int j=0 ; j<length-1 ; j++) {
    		if(arr[j]>arr[j+1]) {
    			//元素互换
    			temp = arr[j];
    			arr[j] = arr[j+1];
    			arr[j+1] = temp;
    		}
    	}
	}
	
	for(int i=0;i<arr.length;i++){
        System.out.println("yc--1--doubi" +arr[i]);
	}
}


//下面这个在第二个for循环做了一些变动
public static void BubbleSort(int[] arr) {
    int temp;//临时变量
    for (int i = 0; i < arr.length - 1; i++) {
        //表示趟数，一共arr.length-1次。
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    for(int i=0;i<arr.length;i++){
        System.out.println("yc1-----" +arr[i]);
    }
}

4.如何优化

  • 遇到问题
    • 数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
  • 解决办法
    • 设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
    • 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
  • 优化代码
    public static void BubbleSort2(int[] arr) {
    int temp;//临时变量
    boolean flag;//是否交换的标志
    for (int i = 0; i < arr.length - 1; i++) {
        //表示趟数，一共arr.length-1次。
        flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag) break;
    }
    for(int i=0;i<arr.length;i++){
        System.out.println("yc2-----" +arr[i]);
    }
}
  • 冒泡排序进一步优化
    • 进一步想象一个场景：现在有一个包含 1000 个数的数组，仅有前面 100 个数无序，后面的 900 个数都比前面的 100 个数更大并且已经排好序。
    • 那么上面优化的方法又会造成一定的时间浪费，所以我们进一步增加一个变量记录最后发生交换的元素的位置，也就是排序的尾边界。

5.复杂度

  • 空间效率：只占用一个辅存单元
  • 时间效率：时间复杂度是O（n²）
    • 待排序元素个数为n,则外层循环的比较次数为n-1次，对j个元素的子序列进行排序，则内层循环为j-1次，考虑最大情况下，则为n-1次，由此，冒泡排序总的比较次数为n（n-1）/2,所以时间复杂度为o(n的平方)。
贡献者: yangchong211