数据结构与算法(17): 排序- 冒泡排序

发表于   |   分类于

  冒泡排序的基本思想：每次比较相邻的两个元素，如果它们顺序错误就把它们交换过来。其中每一趟排序只能将一个数归位。
  时间复杂度是O($N^{2}$)。
  冒泡排序是稳定的。

算法稳定性 – 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    /**
     * 冒泡排序：从大到小
     */
    public class BubbleSort extends Sort{
    public static void sort(int[] a){
        // n个数排序, 只需要n-1趟
        for (int i = 0; i < a.length - 1; i++){
            System.out.println("------第"+(i+1)+"趟-------");
            for (int j = 0; j < a.length - 1 - i; j++){
                if (a[j] < a[j+1]){
                    swap(a, j, j+1);
                }
                print(a);
            }
        }
    }
}

感谢:http://www.cnblogs.com/skywang12345/p/3596232.html