简单排序之冒泡排序

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 1.7k | 阅读时长 ≈ 2 分钟

冒泡排序： T=O(N^2)


　　

基本思想：

　第一趟在序列A[0]~A[n-1]中从前往后进行相邻两个元素的比较，若后者小则交换位置，
　第一趟排序结束后，最大元素会被交换到A[n-1]中，即下沉；
　下一趟排序在A[0]~A[n-2]中进行…
　如果在某趟排序中未交换元素，说明子序列已经有序，则并不再进行下一趟排序。所以最多进行n-1次排序。 　　

代码：

//（正统）冒泡排序1，从前往后，前后元素两两比较，前大后小则交换，每趟循环一个最大元素沉底

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void bubbleSort1(int[] arr){
    int i=arr.length-1;
    int last; //flag
    while(i>0){
        last=0; //每次进入循环就将last置0
        for(int j=0; j<i; j++){
            if(arr[j]>arr[j+1]){
                Swap(arr,j,j+1);
                last=j; //变量last用于记录上次发生元素调换的位置下标
            }
        }
        i=last; //（i--）若在某趟排序中未发生元素交换，则last=0
                //此时i=last=0（说明当前序列已经有序，排序无需再往下进行）则while循环终止，排序完成
    }
}

//（1.1）由程序（1）去掉last变量后的精简版（最大/平均时间复杂度都是O(n^2)）

1
2
3
4
5
6
7
8
9
public static void bubbleSort1_1(int[] arr){
    for(int i=arr.length-1; i>0; i-- ){
        for(int j=0; j<i; j++){
            if(arr[j]>arr[j+1]){
                Swap(arr,j,j+1);
            }
        }
    }
}

//（不正统）冒泡排序2，从前往后，arr[i]分别与arr[i+1]~arr[n-1]相比较，小于arr[i]则调换，每趟循环有一个最小元素浮顶

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

//调换数组中两元素的位置

1
2
3
4
5
private static void Swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

　　

冒泡排序的效率：

　　选择排序改进了冒泡排序，将必要的交换次数从O(N^2)减少到O(N)，不幸的是比较次数依然是O(N^2)级。

　　然而，选择排序依然为大数据量的排序提出了一个非常重要的改进，因为这些大量的记录需要在内存中移动，这就使交换的时间和比较的时间相比起来，交换的时间更为重要。

　　一般来说，Java语言中不是这种情况，Java中只是改变了引用位置，而实际对象的位置并没有发生改变。

---------------- The End ----------------
0%