0%

冒泡排序

发表于 分类于

文章字数：213,阅读全文大约需要1分钟

冒泡排序的思想就是将所有的元素和边上其它元素比较，按照比对结果替换位置。（如果比后一个元素大就替换位置，继续和下一个比）本质上是大的向后移动，小的向前移动。

时间复杂度 o(n^2)

实现

1
2
3
4
5
6
7
8
9
10
11
12
public static void sort(int arr[]){
    for( int i = 0 ; i < arr.length - 1 ; i++ ){
        for(int j = 0;j < arr.length - 1 - i ; j++){
            int temp = 0;
            if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

优化

如果已经是顺序数组，就不要进行后面的遍历了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void sort(int arr[]){
    for( int i = 0;i < arr.length - 1 ; i++ ){
        boolean isSort = true;
        for( int j = 0;j < arr.length - 1 - i ; j++ ){
            int temp = 0;
            if(arr[j] < arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSort = false;
            }
        }
        if(isSort){
            break;
        }
    }
}