算法-冒泡排序java实现

冒泡排序

冒泡排序是通过重复地遍历要排序的列表，一次比较两个元素，并且如果它们的顺序错误就将它们交换位置。冒泡排序的时间复杂度为 O(n^2)。

冒泡排序的基本步骤：

1. 从列表的第一个元素开始，向后遍历每一个元素。
2. 对于当前遍历到的元素，再次向后遍历列表中剩余的元素。
3. 比较当前元素与后面的每一个元素，如果当前元素大于(小于)后面的元素，则交换它们的位置。
4. 继续遍历列表中的每一个元素，并重复步骤 2 和步骤 3，直到列表已经完全排序。

代码实现

public class BubbleSort {
    public static void main(String[] args) {
        int []arr = {5,6,7,4,3,2,6,7,4,2,4,5,7,44,33,5,66,775,55};
        new BubbleSort().bubbleSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public void bubbleSort(int []arr){
        for (int i = arr.length-1; i>0;i--) {
        	// 从第一个元素开始,依次比较该元素和该元素的后一个元素
            for (int j = 0; j < i; j++) {
                if (arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }
/*
上面的冒泡排序虽然可以实现效果但是:
如果数组为[9,1,2,3,4,5,6,7,8], 这个时候,第一次循环就可以把
9交换到最后面,数组就为有序,但是程序任然会继续运行,后面的循环根本没有意义,这是可以定义一个变量,用来记录最后一次交换的位置,如果没有执行交换说明
已经有序
*/
        public void bubbleSort2(int []arr){
        int lastTemp=arr.length-1;
        for (int i = lastTemp; i>0;i--) {
             lastTemp = 0;
            for (int j = 0; j < i; j++) {
                if (arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]=temp;
                    lastTemp = j;
                }
            }
            if (lastTemp == 0)break;
        }
    }
}