Java 10种排序算法的实现和比较

作者: rome753 | 来源:发表于2022-04-22 14:23 被阅读0次

https://www.cnblogs.com/hokky/p/8529042.html
这篇文章总结得非常好，图表很详细，是Python的。下面我用Java实现一下。

1 比较类排序

1.1 冒泡排序

比较和交换相邻两个数，每一趟将最大的数移动到最后一位（参与比较的）。下一趟最后一位不动，对剩下的数重复前面的操作。

    static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

1.2 选择排序

每一趟比较出最小的数，放到第一位（参与比较的）。下一趟，第一位不动，对剩下的数重复前面的操作。

    static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int minI = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minI = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minI];
            arr[minI] = temp;
        }
    }

1.3 插入排序

从第一位开始，将左边数组视为排好序的，把左边数组的右边第一个数插入到左边数组中。插入方法是对左边数组从右向左比较和右移。每一趟左边数组向右扩大一位。

    static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int cur = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > cur) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = cur;
        }
    }

1.4 希尔排序

选一个gap（间隔），将数组分成gap组（k = 0 ~ gap-1）

0, 0 + gap, 0 + gap * 2...
1, 1 + gap, 1 + gap * 2...
k, k + gap, k + gap * 2...

对每组进行插入排序。然后gap缩减，重复前面的操作。

gap的选择对算法效率是有影响的，简单的做法是初始值使用数组长度n/2，下一次gap减半，直到gap=1。有兴趣可以研究选择不同gap的效率。

希尔排序是插入排序的高级版。也可以说插入排序是 gap = 1 的希尔排序，插入排序是希尔排序的最后一步。下面的算法我特意使用了跟前面插入排序相同的循环变量i、j，可以明显看出内部的插入排序。

    static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while(gap >= 1) {
            // 分为gap组
            for (int k = 0; k < gap; k++) {
                // 对每组进行插入排序
                for (int i = k + gap; i < arr.length; i += gap) {
                    int cur = arr[i];
                    int j = i - gap;
                    for (; j >= 0; j -= gap) {
                        if (arr[j] > cur) {
                            arr[j + gap] = arr[j];
                        } else {
                            break;
                        }
                    }
                    arr[j + gap] = cur;
                }
            }
            gap /= 2;
        }
    }

1.5 快速排序

选一个base（基准值），一般选数组第一位，从左右两边同时往中间比较和交换，保证数组左边的数都小于base，右边的都大于base。然后分别将左边和右边当成子数组递归调用前面的操作，直到数组长度为1。

快速排序跟冒泡排序一样是基于交换的，可以当做冒泡排序的高级版。它的代码非常对称有规律，边界值的判断需要非常严谨。

    private static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = low;
        int j = high;
        int base = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= base) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
            }
            while (i < j && arr[i] < base) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
            }
        }
        arr[i] = base;
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }

1.6 堆排序

将数组看做一种特殊的数据结构：大顶堆。它是一颗完全二叉树，每个节点的值都大于它的左右子节点（如果有的话）的值。构建完大顶堆后，根节点就是数组最大值，把它跟最后一位交换。这样最大值就放到最后不动，对剩下的数重新整堆（注意是整堆不是建堆！），然后交换最大值，重复前面的操作。

我看的几乎所有的资料都没有强调“建堆”和“整堆”是两个不同的过程。

建堆（创建堆）只有第一次需要，它是从下向上遍历节点（从最后一个非叶子节点开始，位置是数组长度n / 2 - 1），对每一个节点进行整堆。建堆完成后，后面的操作不会彻底打乱堆，不需要重新建堆，只需要整堆。
整堆（调整堆）是将左右子节点的最大值和当前节点比较，如果子节点的值更大，就跟当前节点交换，然后对交换后的子节点进行递归整堆。

因为完全二叉树的子节点位置可以直接计算 —— 节点位置 i，左子节点是 i * 2 + 1，右子节点是 i * 2 + 2，所以可以用循环代替递归。

堆排序跟选择排序一样每次选出最大值放到末尾，可以当作选择排序的高级版。

   static void heapSort(int[] arr) {
        heapBuild(arr, arr.length);
        for (int len = arr.length; len > 0; len--) {
            int temp = arr[0];
            arr[0] = arr[len - 1];
            arr[len - 1] = temp;
            heapAdjust(arr, 0, len - 1);
        }
    }

    // 建堆
    private static void heapBuild(int[] arr, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, len);
        }
    }

    // 整堆
    private static void heapAdjust(int[] arr, int i, int len) {
        // if (i >= len) { // 没有子节点
        //     return;
        // }
        while (i < len) {
            int left = i * 2 + 1;
            if (left >= len) {
                return;
            }
            int right = left + 1;
            int iNext = i;
            if (right >= len || arr[left] > arr[right]) { // 没有右节点或左边大于右边
                if (arr[left] > arr[i]) {
                    iNext = left;
                }
            } else { // 有右节点且右边不小于左边
                if (arr[right] > arr[i]) {
                    iNext = right;
                }
            }
            if (iNext == i) {
                return;
            }
            int temp = arr[iNext];
            arr[iNext] = arr[i];
            arr[i] = temp;

            i = iNext;
        }
        // heapAdjust(arr, iNext, len);
    }

1.7 归并排序

将数组分成左右两个子数组，对它们分别进行递归归并排序，排序之后再将两个有序数组合并，合并方法是：从左向右同时遍历两个数组，比较大小，将小的放进缓存数组里，坐标右移；同时遍历完后再从当前位置分别遍历两个数组一次，将上次没遍历完的元素全部放进缓存数组，然后将缓存数组复制到原数组。

归并排序利用递归思想，非常巧妙：合并子数组前，认为子数组排序好了；子数组认为子子数组排序好了...直到碰到数组长度1的递归收敛条件，才真正开始合并数组，合并完后上层数组开始合并，然后上上层...直到最外层合并完成。

    static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
    }

    private static void mergeSort(int[] arr, int low, int high, int[] temp) {
        if (low >= high) {
            return;
        }
        int mid = (high + low) / 2;
        mergeSort(arr, low, mid, temp);
        mergeSort(arr, mid + 1, high, temp);
        merge(arr, low, mid, high, temp);
    }

    private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
        int i0 = low, j0 = mid;
        int i1 = mid + 1, j1 = high;
        int k = low;
        while(i0 <= j0 && i1 <= j1) {
            if (arr[i0] < arr[i1]) {
                temp[k++] = arr[i0++];
            } else {
                temp[k++] = arr[i1++];
            }
        }
        while(i0 <= j0) {
            temp[k++] = arr[i0++];
        }
        while(i1 <= j1) {
            temp[k++] = arr[i1++];
        }
        for (int i  = low; i <= high; i++) {
            arr[i] = temp[i];
        }
    }

1.8 算法效率比较

    public static void main(String[] args) {
        check("bubble");
        check("select");
        check("insert");
        check("shell");
        check("quick");
        check("merge");
        check("heap");
    }

    static void check(String name) {
        int n = 10000;
        int[] arr = new int[n];
        Random r = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = r.nextInt(n);
        }
        long t = System.currentTimeMillis();
        switch (name) {
            case "bubble":
                bubbleSort(arr);
                break;
            case "select":
                selectSort(arr);
                break;
            case "insert":
                insertSort(arr);
                break;
            case "shell":
                shellSort(arr);
                break;
            case "quick":
                quickSort(arr);
                break;
            case "merge":
                mergeSort(arr);
                break;
            case "heap":
                heapSort(arr);
                break;
            default:
                break;
        }
        t = System.currentTimeMillis() - t;
        System.out.println(name + "Sort\t" + "time(ms): " + t);
    }

生成一个长度n的随机数组，计算不同排序算法的运行时间，n从一万增加到一千万（超过十万后只计算高级排序的）。

n = 10000
bubbleSort      time(ms): 50
selectSort      time(ms): 19
insertSort      time(ms): 26
shellSort       time(ms): 4
quickSort       time(ms): 2
mergeSort       time(ms): 2
heapSort        time(ms): 3

n = 100000
bubbleSort      time(ms): 10922
selectSort      time(ms): 1068
insertSort      time(ms): 1974
shellSort       time(ms): 19
quickSort       time(ms): 29
mergeSort       time(ms): 17
heapSort        time(ms): 24

n = 1000000
shellSort       time(ms): 153
quickSort       time(ms): 105
mergeSort       time(ms): 117
heapSort        time(ms): 144

n = 10000000
shellSort       time(ms): 2393
quickSort       time(ms): 948
mergeSort       time(ms): 1195
heapSort        time(ms): 1849

从耗时可以简单分析出几点：

简单排序（冒泡、选择、插入）的耗时远远超过高级排序。几种简单排序耗时接近，几种高级排序耗时也接近。
简单排序里：数量增加后冒泡排序耗时是其他的几倍，因为它执行了更多无效的交换操作。
高级排序里：数量十万左右时，希尔排序和归并排序更快，其他数量都是快速排序和归并排序最快（这两种排序都是递归分治的思想）。

2 非比较排序

2.1 计数排序

遍历一遍数组，用另一个数组记录每个数出现的次数，然后把次数转换成数字数组。

它只能用来给数字排序，而且排序后的数组元素并不是原来的数组元素，相当于全部换了一遍，虽然数值相同。

    static void countSort(int[] arr) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int a : arr) {
            if (a < min) {
                min = a;
            }
            if (a > max) {
                max = a;
            }
        }
        int[] bucket = new int[max - min + 1];
        for (int a : arr) {
            bucket[a - min]++;
        }
        int cur = min;
        int i = 0;
        for (int b: bucket) {
            while(b-- > 0) {
                arr[i++] = cur;
            }
            cur++;
        }
    }

2.2 桶排序

先遍历一遍数组，根据数字大小给数字分组，也就是放到不同的“桶”里。再对桶里的数字用某种方法排序。由于每个桶的大小不确定，只能用高级数据结构List保存。

为了方便，桶里的数字我直接用Collections.sort方法排序了。

    static void bucketSort(int[] arr) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int a : arr) {
            if (a < min) {
                min = a;
            }
            if (a > max) {
                max = a;
            }
        }
        int dis = max - min;
        if (dis == 0) {
            return;
        }
        int bMAX = 1000;
        int bn = dis < bMAX ? dis : bMAX;
        int gap = dis / bn + 1;
        List<List<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i < bn; i++) {
            bucket.add(new ArrayList<>());
        }
        for (int a: arr) {
            int i = (a - min) / gap;
            bucket.get(i).add(a);
        }
        int k = 0;
        for (int i = 0; i < bn; i++) {
            List<Integer> bi = bucket.get(i);
            Collections.sort(bi);
            for (int b: bi) {
                arr[k++] = b;
            }
        }
    }

2.3 基数排序

把数字按十进制的每一位排序。建立0~9十个桶，先按个位是几把数字放进对应的桶里；然后按桶里顺序取出来，按数字的十位放进桶里...直到最大数字的最高位为止。

它也是一种桶排序，每个桶的大小也不确定，需要用List保存。它遍历的次数是最大数字的十进制位数，每次遍历需要把数字从数组倒进桶里，遍历完再放回数组。

    static void radixSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int a : arr) {
            if (a > max) {
                max = a;
            }
        }
        List<List<Integer>> bucket;
        int m = 1;
        while(m < max) {
            bucket = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                bucket.add(new ArrayList<>());
            }
            for (int a: arr) {
                int i = a / m % 10;
                bucket.get(i).add(a);
            }
            int k = 0;
            for (List<Integer> list: bucket) {
                for (int a: list) {
                    arr[k++] = a;
                }
            }
            m *= 10;
        }
    }

2.4 算法效率比较

n = 10000
countSort       time(ms): 2
bucketSort      time(ms): 22
radixSort       time(ms): 10

n = 100000
countSort       time(ms): 11
bucketSort      time(ms): 79
radixSort       time(ms): 26

n = 1000000
countSort       time(ms): 20
bucketSort      time(ms): 280
radixSort       time(ms): 238

n = 10000000
countSort       time(ms): 168
bucketSort      time(ms): 2172
radixSort       time(ms): 2726

简单分析

因为只遍历一遍，所以计数排序的速度非常快，比另外两种快10倍，比前面表现最好的快速排序还快5倍！
因为需要用高级数据结构，桶排序和基数排序比其他的高级排序至少慢一倍。

3 搞笑类排序

3.1 睡眠排序

遍历一遍数组，每个数开启子线程，按数字大小设置不同的延时，按延时结束的时间将数字放到一个新的集合中。

虽然是搞笑类，但是睡眠排序的确是可以工作的！并且是将时间转换成空间的思想。为了并发安全，新的集合使用了线程安全的Vector。睡眠时间不能设置得太小，需要统一放大一些，否则会受到CPU调度等时间影响。

    static void sleepSort(int[] arr) {
        Vector<Integer> temp = new Vector<>();
        for (int a: arr) {
            Thread t = new Thread(){
                @Override
                public void run() {
                    try {
                        Thread.sleep(a * 10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    temp.add(a);
                    if (temp.size() == arr.length) {
                        for (int i = 0; i < arr.length; i++) {
                            arr[i] = temp.get(i);
                        }
                    }
                };
            };
            t.start();
        }
    }