算法排序

java 实现冒泡排序，选择排序，插入排序，快速排序（简洁版）及性能测试

冒泡排序是排序里面最简单的了，但性能也最差，数量小的时候还可以，数量一多，是非常慢的它的时间复杂度是O（n*n），空间复杂度是O（1）

// 冒泡排序:
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        // 找出最小要 arr.length - 1 - i 次
        for (int j = arr.length - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

选择排序的时间复杂度还有空间复杂度跟冒泡是一样的。

 // 选择排序：
public void chooseSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

插入排序的时间复杂度也是O(n*n)，空间复杂度也是O(1)

 // 插入排序：
public void insertSort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[j]) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

快速排序通常情况下是最快的，名不虚传啊~平均时间复杂度是 O(Nlog2N)，最差也是O(N*N)，空间复杂度O(Nlog2N)

 // 快速排序
public void quickSort(int[] arr, int head, int tail) {
    int i = head;
    int j = tail;
    if (i > j) {
        return;
    }
    int key = arr[i];
    while (i < j) {
        while (i < j && key <= arr[j]) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (i < j && key >= arr[i]) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[j] = key;
    quickSort(arr, head, j - 1);
    quickSort(arr, j + 1, tail);
} 

测试

@Test
public void TestSort() {
    int[] arr1 = new int[6000];
    for (int i = 0; i < arr1.length; i++) {
        arr1[i] = new Random().nextInt(6000) + 1;
    }
    int[] arr2 = new int[6000];
    for (int i = 0; i < arr2.length; i++) {
        arr2[i] = new Random().nextInt(6000) + 1;
    }
    int[] arr3 = new int[6000];
    for (int i = 0; i < arr3.length; i++) {
        arr3[i] = new Random().nextInt(6000) + 1;
    }
    int[] arr4 = new int[6000];
    for (int i = 0; i < arr4.length; i++) {
        arr4[i] = new Random().nextInt(6000) + 1;
    }
    long m = System.currentTimeMillis();
    bubbleSort(arr1);
    long n = System.currentTimeMillis();
    System.out.println("冒泡排序耗时：" + (n - m) + "ms");

    long p = System.currentTimeMillis();
    int[] arr6 = {77,43,56,78};
    chooseSort(arr2);
    long q = System.currentTimeMillis();
    System.out.println("选择排序耗时：" + (q - p) + "ms");

    long e = System.currentTimeMillis();
    insertSort(arr3);
    long d = System.currentTimeMillis();
    System.out.println("插入排序耗时：" + (d - e) + "ms");

    long a = System.currentTimeMillis();
    quickSort(arr4, 0, arr4.length - 1);
    long b = System.currentTimeMillis();
    System.out.println("快速排序耗时：" + (b - a) + "ms");
}

冒泡排序耗时：106ms
选择排序耗时：107ms
插入排序耗时：47ms
快速排序耗时：2ms