排序算法

术语解释

内排序

所有排序操作都在内存中完成；

外排序

由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度

一个算法执行所耗费的时间。

空间复杂度

运行完一个程序所需内存的大小。
O(1) : 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量.
O(n) : 如果算法执行所需要的临时空间随n大小而变化,则为O(n). 举栗,需要一个n大小的临时数组作为交换区.

算法比较

	空间复杂度	时间复杂度	平均时间复杂度	最好	最坏	排序方式
冒泡排序	O(1)	O(n2)	O(n2)	O(n2)	O(n2)	内排序
选择排序	O(1)	O(n2)	O(n2)	O(n2)	O(n2)	内排序
插入排序	O(1)	O(n2)	O(n2)	O(n)	O(n2)	内排序
希尔排序						内排序
快速排序						内排序
堆排序						内排序

算法实现

冒泡排序

import java.util.Arrays;
/**
 * 冒泡排序
 * 1.每次比较相邻2个数的大小,然后按照规则(升序,还是降序)决定是否交换位置.
 * 2.循环"1"过程,直到完成n次(每次只确定一个数在已排序部分的位置).
 *
 * 花费:
 * avg time: O(n^2)
 * min time: O(n^2)
 * max time: O(n^2)
 * space: O(1)
 * <p>
 * 时间复杂度:
 * 最好情况是待排序数组已经有序O(n^2).
 * 最坏情况是待排序数组是完全倒序O(n^2).
 * 空间复杂度: 算法实现只需1个变量,因此是稳定的O(1).
 * <p>
 * 算法解析:
 * U 表示待排序数组长度. U 最开始为 n,最后一个数为 1,是一个等差数列.
 * 外层循环需要遍历 n 次,每次确定一个数排序后的位置,每次 U=U-1.
 * 内层循环需要从待排序数组中找出最值,需要比较 n 次.
 * <p>
 * 因此,算法是
 * ((n + 1) / 2) * n
 * = (n^2 - n)/2
 * ≈ n^2
 */
public class BubbleSort {
    /**
     * 升序排序
     * @param source 未排序的数组
     * @return 已排序的数组
     */
    static int[] sort(int[] source) {
        int times = 0;
        int tmp;
        // 循环次数
        for (int i = 1; i < source.length; i++) {
            // 单次循环所需遍历的范围
            for (int j = 0; j < source.length - i; j++) {
                times++;
                if (source[j] > source[j + 1]) {
                    tmp = source[j];
                    source[j] = source[j + 1];
                    source[j + 1] = tmp;
                }
            }
        }
        System.out.println("times:" + times);
        return source;
    }
    public static void main(String[] args) {
        System.out.println("最差情况,反向有序:");
        System.out.println(Arrays.toString(sort(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0})));
        System.out.println("最好情况,有序:");
        System.out.println(Arrays.toString(sort(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9})));
    }
}

结果:
to do.

最差情况,反向有序:
times:45
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最好情况,有序:
times:45
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

选择排序

import java.util.Arrays;
/**
 * 选择排序
 * 原理:
 * 1.每次从待排序数组中选出最(大/小)的值,放到待排序数组后面.
 * 2.循环"1"过程,直到没有待排序的数字.
 * <p>
 * 花费:
 * avg time: O(n^2)
 * min time: O(n^2)
 * max time: O(n^2)
 * space: O(1)
 * <p>
 * 时间复杂度:
 * 最好情况是待排序数组已经有序O(n^2).
 * 最坏情况是待排序数组是完全倒序O(n^2).
 * <p>
 * 空间复杂度:
 * 算法实现只需2个变量,因此是稳定的O(1).
 * <p>
 * 解析:
 * 同冒泡类似.
 */
public class SelectSort {
    /**
     * 升序排序
     *
     * @param source 未排序的数组
     * @return 已排序的数组
     */
    static int[] sort(int[] source) {
        int times = 0;
        // 待排序部分
        for (int j = 0; j < source.length; j++) {
            int min = Integer.MAX_VALUE;
            int idx = -1;
            // 从未排序部分选择最值
            for (int i = j; i < source.length; i++) {
                times++;
                if (min > source[i]) {
                    min = source[i];
                    idx = i;
                }
            }
            source[idx] = source[j];
            source[j] = min;
        }
        System.out.println("times:" + times);
        return source;
    }
    public static void main(String[] args) {
        // 最坏情况
        System.out.println(Arrays.toString(sort(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0})));
        // 最好情况
        System.out.println(Arrays.toString(sort(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9})));
    }
}

结果:

最差情况,反向有序:
times:55
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最好情况,有序:
times:55
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

动画演示:
to do.

插入排序

import java.util.Arrays;
/**
 * 插入排序
 * 原理:
 * 从未排序部分中每次取一个数,插入到待排序部分的合适位置.
 * <p>
 * 步骤:
 * 1.从待排序数组中的一段取数.
 * 2.取出的数与已排序部分比较,找到适合插入的位置.
 * 3.循环"1,2"过程,直到待排序部分为空.
 * <p>
 * 花费:
 * avg time: O(n^2)
 * min time: O(n)
 * max time: O(n^2)
 * space: O(1)
 * <p>
 * 时间复杂度:
 * 最好情况是待排序数组已排序,时间为O(n),仅需遍历一遍.
 * 最坏情况是待排序数组反向有序,时间为O(n^2).
 * <p>
 * 空间复杂度:
 * 算法实现只需1个变量,因此是稳定的O(1).
 * <p>
 * 解析:
 * 是选择排序的反过程.
 */
public class InsertSort {
    /**
     * 升序
     *
     * @param source 未排序的数组
     * @return 已排序的数组
     */
    static int[] sort(int[] source) {
        int times = 0; //统计次数
        // i为无序部分分界
        for (int i = 1; i < source.length; i++) {
            // j为有序部分分界
            for (int j = 0; j < i; j++) {
                times++;
                if (source[i] < source[j]) {
                    int tmp = source[i];
                    source[i] = source[j];
                    source[j] = tmp;
                } else {
                    // 提前重点,避免无效的遍历
                    break;
                }
            }
        }
        System.out.println("times:" + times);
        return source;
    }
    public static void main(String[] args) {
        System.out.println("最差情况,反向有序:");
        System.out.println(Arrays.toString(sort(new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0})));
        System.out.println("最好情况,有序:");
        System.out.println(Arrays.toString(sort(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9})));
    }
}

结果:

最差情况,反向有序:
times:45
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最好情况,有序:
times:9
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

动画演示:
to do.