<span>排序算法(一) 冒泡排序</span>

BubbleSort

1.动图演示

2.代码实现

2.1 测试工具类

import java.lang.reflect.Method;

/**
 * 测试排序的工具类
 * 后续测试其他排序时也会用到
 */
public class SortTestHelper {

    // private 修饰构造方法。不允许产生任何该类实例
    private SortTestHelper() {
    }

    /**
     * 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
     */
    public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {

        assert rangeL <= rangeR;

        Integer[] arr = new Integer[n];

        for (int i = 0; i < n; i++)
            arr[i] = new Integer((int) (Math.random() * (rangeR - rangeL + 1) + rangeL));
        return arr;
    }

    /**
     *  打印arr数组的所有内容
     */
    public static void printArray(Object arr[]) {

        for (int i = 0; i < arr.length; i++) {

            System.out.print(arr[i]);
            System.out.print(' ');
            if (i > 0 && i % 50 == 0)
                System.out.println();

        }
        System.out.println();
        return;
    }


    /**
     * 测试sortClassName所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间
     * 这里通过反射调用某个排序的sort()方法
     * 具体调用哪一个类的sort 通过传入的类名来决定。
     * 不了解Java反射机制的话可以跳过，这对于测试排序算法来说不重要。
     */
    public static void testSort(String sortClassName, Comparable[] arr) {
        // 通过Java的反射机制，通过排序的类名，运行排序函数

        try {
            // 通过sortClassName获得排序函数的Class对象
            Class sortClass = Class.forName(sortClassName);
            //通过类对象获取排序方法
            Method sortMethod = sortClass.getMethod("sort", Comparable[].class);//new Class[]{   }
            //排序参数，可比较对象的数组
            Object[] params = new Object[]{arr};

            long startTime = System.currentTimeMillis();
            //调用排序方法
            sortMethod.invoke(null, params);
            long endTime = System.currentTimeMillis();
            assert isSorted(arr);
            System.out.println(sortClass.getSimpleName() + " : " + (endTime - startTime) + "ms");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    /**
     * 判断arr数组是否有序
     */
    private static boolean isSorted(Comparable[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i].compareTo(arr[i + 1]) > 0) {
                throw new RuntimeException("排序失败");
            }
        }

        return true;
    }

    /**
     * 先生产一个有序数组，随机挑选几个交换位置，返回一个近乎有序的数组。
     */
    public static Integer[] generateNearlyOrderedArray(int n, int swapTimes) {
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        for (int i = 0; i < swapTimes; i++) {
            int x = (int) (Math.random() * n);
            int y = (int) (Math.random() * n);
            Integer t = arr[x];
            arr[x] = arr[y];
            arr[y] = t;
        }
        return arr;

    }

    /**
     * 数组中index为 i 和 j 的元素 交换位置
     */
    public static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}

2.2 冒泡排序代码

/**
 * 冒泡排序
 */
public class BubbleSort {

    // 算法类不允许产生任何实例
    private BubbleSort(){}

    public static void sort(Comparable[] arr){

        int n = arr.length;
        int newn;

        do{
            newn = 0;
            for( int i = 1 ; i < n ; i ++ )
                if( arr[i-1].compareTo(arr[i]) > 0 ){
                    swap( arr , i-1 , i );
                    // 可以记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                    newn = i;
                }
            n = newn;
        }while(newn > 0);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
  public static void main(String[] args) {
        int N = 10000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 1000);
        SortTestHelper.testSort("sort.BubbleSort", arr);
        int N2 = 20000;
        Integer[] arr2 = SortTestHelper.generateRandomArray(N2, 0, 1000);
        SortTestHelper.testSort("sort.BubbleSort", arr2);
        int N3 = 30000;
        Integer[] arr3 = SortTestHelper.generateRandomArray(N3, 0, 1000);
        SortTestHelper.testSort("sort.BubbleSort", arr3);
    }
}

3.测试结果

这里是初步的测试，后续文章会结合多个类型的排序，对于不同类型的数组排序，比较各个排序算法的性质。

4.算法分析

4.1描述

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

4.2分析

in-place 不占用额外的空间。显然，若数组存在相同元素，不会交换位置，因此冒泡排序是稳定的。