关于面试:7-天时间我整理并实现了这-9-种最经典的排序算法

104次阅读

共计 16299 个字符，预计需要花费 41 分钟才能阅读完成。

回顾

咱们后面曾经介绍了 3 种最常见的排序算法：

java 实现冒泡排序解说

QuickSort 疾速排序到底快在哪里？

SelectionSort 抉择排序算法详解（java 实现）

然而天下排序千千万，明天老马就和大家一起把最常见的几种都学习一遍。

堆排序

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆是一个近似齐全二叉树的构造，并同时满足堆的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

基础知识 JCIP-11- 二叉堆

最大堆

若以升序排序阐明，把数组转换成最大堆 (Max-Heap Heap)，这是一种满足最大堆性质(Max-Heap Property) 的二叉树：对于除了根之外的每个节点 i, A[parent(i)] ≥ A[i]。

堆是具备以下性质的齐全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为 大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

反复从最大堆取出数值最大的结点(把根结点和最初一个结点替换，把替换后的最初一个结点移出堆)，并让残余的堆维持最大堆性质。

同时，咱们对堆中的结点按层进行编号，将这种逻辑构造映射到数组中就是上面这个样子:

堆节点的拜访

通常堆是通过一维数组来实现的。

在数组起始地位为 0 的情景中：

则父节点和子节点的地位关系如下：

(01) 索引为 i 的左孩子的索引是 (2*i+1);

(02) 索引为 i 的左孩子的索引是 (2*i+2);

(03) 索引为 i 的父结点的索引是 floor((i-1)/2);

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中应用堆的话堆中的最小值位于根节点）。

堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

创立最大堆（Build Max Heap）：将堆中的所有数据从新排序

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

堆排序算法图解

这个图解来自 图解排序算法 (三) 之堆排序，画的十分丑陋。

根本思维

将待排序序列结构成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。

将其与开端元素进行替换，此时开端就为最大值。

而后将残余 n - 1 个元素从新结构成一个堆，这样会失去 n 个元素的次小值。如此重复执行，便能失去一个有序序列了。

步骤

步骤一 结构初始堆

将给定无序序列结构成一个大顶堆（个别升序采纳大顶堆，降序采纳小顶堆)。

a. 假如给定无序序列构造如下

b. 此时咱们从最初一个非叶子结点开始（叶子结点天然不必调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是上面的 6 结点），从左至右，从下至上进行调整。

c. 找到第二个非叶节点 4，因为 [4,9,8] 中 9 元素最大，4 和 9 替换。

d. 这时，替换导致了子根 [4,5,6] 构造凌乱，持续调整，[4,5,6]中 6 最大，替换 4 和 6。

此时，咱们就将一个无序的序列结构成了一个大顶堆。

步骤二 调整堆

将堆顶元素与开端元素进行替换，使开端元素最大。

而后持续调整堆，再将堆顶元素与开端元素替换，失去第二大元素。如此重复进行替换、重建、替换。

a. 将堆顶元素 9 和开端元素 4 进行替换

b. 从新调整结构，使其持续满足堆定义

c. 再将堆顶元素 8 与开端元素 5 进行替换，失去第二大元素 8.

后续过程，持续进行调整，替换，如此重复进行，最终使得整个序列有序

简略总结

再简略总结下堆排序的基本思路：

a. 将无需序列构建成一个堆，依据升序降序需要抉择大顶堆或小顶堆;

b. 将堆顶元素与开端元素替换，将最大元素 ” 沉 ” 到数组末端;

c. 从新调整结构，使其满足堆定义，而后持续替换堆顶元素与以后开端元素，重复执行调整 + 替换步骤，直到整个序列有序。

java 实现

阐明

为了和后面的逻辑保持一致，咱们临时仍然应用 list 去实现这个堆排序。

实现

package com.github.houbb.sort.core.api;

import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.List;

/**
 * 堆排序
 *
 * @author binbin.hou
 * @since 0.0.4
 */
public class HeapSort extends AbstractSort {private static final Log log = LogFactory.getLog(HeapSort.class);

    @Override
    @SuppressWarnings("all")
    protected void doSort(List<?> original) {final int maxIndex = original.size() - 1;

        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。*  从第一个非叶子节点开始即可。无需从最初一个叶子节点开始。*  叶子节点能够看作已合乎堆要求的节点，根节点就是它本人且本人以下值为最大。*/
        int beginIndex = original.size() / 2 - 1;
        for (int i = beginIndex; i >= 0; i--) {maxHeapify(original, i, maxIndex);
        }

        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点 A[0]，与最尾部节点地位调换，同时遍历长度 - 1。* 而后从新整顿被换到根节点的开端元素，使其合乎堆的个性。* 直至未排序的堆长度为 0。*/
        for (int i = maxIndex; i > 0; i--) {InnerSortUtil.swap(original, 0, i);
            maxHeapify(original, 0, i - 1);
        }
    }

    /**
     * 调整索引为 index 处的数据，使其合乎堆的个性。*
     * @param list  列表
     * @param index 须要堆化解决的数据的索引
     * @param len   未排序的堆（数组）的长度
     * @since 0.0.4
     */
    @SuppressWarnings("all")
    private void maxHeapify(final List list, int index, int len) {int li = (index * 2) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。// 左子节点索引超出计算范畴，间接返回。if (li > len) {return;}

        // 先判断左右子节点，哪个较大。if (ri <= len && InnerSortUtil.gt(list, ri, li)) {cMax = ri;}

        if (InnerSortUtil.gt(list, cMax, index)) {InnerSortUtil.swap(list, cMax, index);      // 如果父节点被子节点调换，maxHeapify(list, cMax, len);  // 则须要持续判断换下后的父节点是否合乎堆的个性。}
    }

}

插入排序

插入排序（英语：Insertion Sort）是一种简略直观的排序算法。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。

插入排序在实现上，通常采纳 in-place 排序（即只需用到 O(1) 的额定空间的排序），因此在从后向前扫描过程中，须要重复把已排序元素逐渐向后挪位，为最新元素提供插入空间。

算法步骤

一般来说，插入排序都采纳 in-place 在数组上实现。具体算法形容如下：

  1. 从第一个元素开始，该元素能够认为曾经被排序
  2. 取出下一个元素，在曾经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一地位
  4. 反复步骤 3，直到找到已排序的元素小于或者等于新元素的地位
  5. 将新元素插入到该地位后
  6. 反复步骤 2~5

java 实现

java 实现

package com.github.houbb.sort.core.api;

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.List;

/**
 * 冒泡排序
 * @author binbin.hou
 * @since 0.0.5
 */
@ThreadSafe
public class InsertSort extends AbstractSort {private static final Log log = LogFactory.getLog(InsertSort.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {for(int i = 1; i < original.size(); i++) {Comparable current = (Comparable) original.get(i);

            int j = i-1;
            // 从后向前遍历，把大于以后元素的信息全副向后挪动。while (j >= 0 && InnerSortUtil.gt(original, j, current)) {
                // 元素向后挪动一位
                original.set(j+1, original.get(j));
                j--;
            }

            // 将元素插入到对应的地位
            original.set(j+1, current);
        }
    }

}

希尔排序（Shellsort）

也称递加增量排序算法，是插入排序的一种更高效的改良版本。

希尔排序是非稳固排序算法。

希尔排序是基于插入排序的以下两点性质而提出改良办法的：

  1. 插入排序在对简直曾经排好序的数据操作时，效率高，即能够达到线性排序的效率
  2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据挪动一位

算法实现

希尔排序通过将比拟的全副元素分为几个区域来晋升插入排序的性能。

这样能够让一个元素能够一次性地朝最终地位后退一大步。而后算法再取越来越小的步长进行排序，算法的最初一步就是一般的插入排序，然而到了这步，需排序的数据简直是已排好的了（此时插入排序较快）。

假如有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为 O(n^2)的排序（冒泡排序或插入排序），可能会进行 n 次的比拟和替换能力将该数据移至正确地位。

而希尔排序会 用较大的步长挪动数据，所以小数据只需进行多数比拟和替换即可到正确地位。

一个更好了解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。反复这过程，不过每次用更长的列来进行。最初整个表就只有一列了。

将数组转换至表是为了更好地了解这算法，算法自身仅仅对原数组进行排序（通过减少索引的步长，例如是用 i += step_size 而不是 i ++）。

例子

例如，假如有这样一组数[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果咱们以步长为 5 开始进行排序，咱们能够通过将这列表放在有 5 列的表中来更好地形容算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

而后咱们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时咱们失去：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]。

这时 10 曾经移至正确地位了，而后再以 3 为步长进行排序：

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最初以 1 步长进行排序（此时就是简略的插入排序了）。

步长序列如何抉择？

Donald Shell 最后倡议步长抉择为 n/2 并且对步长取半直到步长达到 1。

尽管这样取能够比 O(n^2) 类的算法（插入排序）更好，但这样依然有缩小均匀工夫和最差工夫的余地。

已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…)，

另一个在大数组中体现优异的步长序列是（斐波那契数列除去 0 和 1 将残余的数以黄金分割比的两倍的幂进行运算失去的数列）：

(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

java 代码实现

实现

这里为了简略，咱们步长间接抉择列表长度的一半，并且顺次折半。

import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.List;

/**
 * 希尔排序
 *
 * @author binbin.hou
 * @since 0.0.6
 */
public class ShellSort extends AbstractSort {private static final Log log = LogFactory.getLog(ShellSort.class);

    @Override
    @SuppressWarnings("all")
    protected void doSort(List<?> original) {
        // 步长从大到小
        for(int step = original.size()/2; step > 0; step /= 2) {
            // 从第 step 个元素，一一执行插入排序
            for(int i = step; i < original.size(); i++) {
                int j = i;

                while ((j-step >= 0) && InnerSortUtil.lt(original, j, j-step)) {
                    // 执行替换
                    InnerSortUtil.swap(original, j, j-step);

                    if(log.isDebugEnabled()) {log.debug("step: {}, j: {}, j-step: {}, list: {}",
                                step, j, j-step, original);
                    }

                    // 更新步长
                    j -= step;
                }
            }
        }
    }

}

整体实现也不难，大家能够回顾下 插入排序

这里为了便于大家了解，咱们特意增加了日志。

归并排序（英语：Merge sort，或 mergesort）

是创立在归并操作上的一种无效的排序算法，效率为 O(nlogn)（大 O 符号）。1945 年由约翰·冯·诺伊曼首次提出。

该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用，且各层分治递归能够同时进行。

概述

采纳分治法:

宰割：递归地把以后序列均匀宰割成两半。

集成：在放弃元素程序的同时将上一步失去的子序列集成到一起（归并）。

java 实现递归法

递归法（Top-down）

  1. 申请空间，使其大小为两个曾经排序序列之和，该空间用来寄存合并后的序列
  2. 设定两个指针，最后地位别离为两个曾经排序序列的起始地位
  3. 比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间，并挪动指针到下一地位
  4. 反复步骤 3 直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素间接复制到合并序列尾

java 实现

实际上代码实现也不难，不过递归多多少少让人看起来不太习惯。

咱们前面会联合测试日志，再进行解说。

package com.github.houbb.sort.core.api;

import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.ArrayList;
import java.util.List;

/**
 * 归并排序 - 递归实现
 *
 * @author binbin.hou
 * @since 0.0.7
 */
public class MergeRecursiveSort extends AbstractSort {private static final Log log = LogFactory.getLog(MergeRecursiveSort.class);

    @Override
    @SuppressWarnings("all")
    protected void doSort(List<?> original) {
        // 寄存归并的后果
        // 间接将数组填满，防止 set 呈现越界
        List<?> resultList = new ArrayList<>(original);
        sortRecursive(original, resultList, 0, original.size()-1);
    }

    /**
     * 递归排序
     * @param originalList 原始列表
     * @param resultList 寄存后果的列表
     * @param startIx 开始
     * @param endIx 后果
     * @since 0.0.7
     */
    @SuppressWarnings("all")
    private void sortRecursive(List originalList,
                               List resultList,
                               int startIx,
                               int endIx) {
        // 循环完结
        if(startIx >= endIx) {return;}

        // 找到两头地位，将列表一分为二
        int midIx = (startIx+endIx) / 2;
        int leftStart = startIx;
        int leftEnd = midIx;
        int rightStart = midIx+1;
        int rightEnd = endIx;

        if(log.isDebugEnabled()) {log.debug("拆分：ls: {}, le: {}, rs: {}, re: {}",
                    leftStart, leftEnd, rightStart, rightEnd);
        }

        // 递归调用
        sortRecursive(originalList, resultList, leftStart, leftEnd);
        sortRecursive(originalList, resultList, rightStart, rightEnd);

        if(log.isDebugEnabled()) {log.debug("操作：ls: {}, le: {}, rs: {}, re: {}",
                    leftStart, leftEnd, rightStart, rightEnd);
        }

        // 这里须要通过 k 记录一下开始的地位
        int k = startIx;
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            // 绝对小的元素放入到合并空间，并挪动指针到下一地位
            Comparable left = (Comparable) originalList.get(leftStart);
            Comparable right = (Comparable) originalList.get(rightStart);

            // 右边较小，则放入合并空间
            if(left.compareTo(right) < 0) {resultList.set(k++, left);
                leftStart++;
            } else {resultList.set(k++, right);
                rightStart++;
            }
        }

        // 如果列表比拟完结，将剩下的元素，全副放入到队列中。while (leftStart <= leftEnd) {resultList.set(k++, originalList.get(leftStart++));
        }
        while (rightStart <= rightEnd) {resultList.set(k++, originalList.get(rightStart++));
        }

        // 将后果对立拷贝到原始汇合中
        for(int i = startIx; i <= endIx; i++) {originalList.set(i, resultList.get(i));
        }
    }

}

java 迭代实现

置信很多小伙伴都晓得迭代能够使得代码变得简洁，然而会让调试和了解变得复杂。

咱们来一起学习一下迭代的实现形式。

迭代法（Bottom-up）

原理如下（假如序列共有 n 个元素）：

  1. 将序列每相邻两个数字进行归并操作，造成 ceil(n/2) 个序列，排序后每个序列蕴含两 / 一个元素
  2. 若此时序列数不是 1 个则将上述序列再次归并，造成 ceil(n/4) 个序列，每个序列蕴含四 / 三个元素
  3. 反复步骤 2，直到所有元素排序结束，即序列数为 1

迭代实现

绝对递归，这个代码就要显得简单很多。

不过这种迭代的形式性能更好，实现如下。

package com.github.houbb.sort.core.api;

import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 归并排序 - 迭代实现
 *
 * @author binbin.hou
 * @since 0.0.7
 */
public class MergeSort extends AbstractSort {private static final Log log = LogFactory.getLog(MergeSort.class);

    @Override
    protected void doSort(List<?> original) {
        // 寄存归并的后果
        // 间接将数组填满，防止 set 呈现越界
        List<?> resultList = new ArrayList<>(original);

        // 起始，子序列长度为 1。对长度为 1 的序列进行两两合并
        int k = 1;
        final int length = original.size();
        while (k < length) {mergePass(original, resultList, k, length);// 将原先无序的数据两两归并入归并数组
            k = 2 * k;// 子序列长度加倍
            mergePass(resultList, original, k, length);// 将归并数组中曾经两两归并的有序序列再归并回数组 original
            k = 2 * k;// 子序列长度加倍
        }
    }

    /**
     * 负责将数组中的相邻的有 k 个元素的字序列进行归并
     *
     * @param original 原始列表
     * @param results 后果列表
     * @param s  子序列长度
     * @param len 长度
     * @since 0.0.7
     */
    @SuppressWarnings("all")
    private static void mergePass(List original, List results, int s, int len) {
        int i = 0;

        // 写成(i + 2 * k - 1 < len)，就会把（i+2*k-1）当做一个整体对待
        // 从前往后, 将 2 个长度为 k 的子序列合并为 1 个。// 对于序列{3, 4, 2, 5, 7, 0, 9, 8, 1, 6}，当 k = 8 的时候，因为 i >(len-2*k+1), 所以基本没有进入 while 循环
        while (i < len - 2 * s + 1) {merge(original, results, i, i + s - 1, i + 2 * s - 1);// 两两归并
            i = i + 2 * s;
        }

        // 将那些“落单的”长度有余两两 merge 的局部和后面 merge 起来。// (连接起来之前也是要进行排序的，因而有了上面的 merge 操作)
        if (i < len - s + 1) {merge(original, results, i, i + s - 1, len - 1);// 归并最初两个序列
        } else {for (int j = i; j < len; j++) {// 若最初只剩下单个子序列
                results.set(j, original.get(j));
            }
        }
    }

    /**
     * 将两个有序数组合并成一个有序数组
     * @param original 原始
     * @param result 后果
     * @param low 开始
     * @param mid 两头
     * @param high 完结
     * @since 0.0.7
     */
    @SuppressWarnings("all")
    private static void merge(List original, List result, int low, int mid, int high) {
        int j, k, l;

        // 将记录由小到大地放进 temp 数组
        for (j = mid + 1, k = low; low <= mid && j <= high; k++) {if (InnerSortUtil.lt(original, low, j)) {result.set(k, original.get(low++));
            } else {result.set(k, original.get(j++));
            }
        }

        // 接下来两循环是为了将残余的（比另一边多进去的个数）放到 temp 数组中
        if (low <= mid) {for (l = 0; l <= mid - low; l++) {result.set(k + l, original.get(low + l));
            }
        }
        if (j <= high) {for (l = 0; l <= high - j; l++) {result.set(k + l, original.get(j + l));
            }
        }
    }

}

counting sort 计数排序

计数排序（Counting sort）是一种稳固的线性工夫排序算法。

该算法于 1954 年由 Harold H. Seward 提出。

通过计数将工夫复杂度降到了 O(N)。

根底版

算法步骤

  1. 找出原数组中元素值最大的，记为 max。
  2. 创立一个新数组 count，其长度是 max 加 1，其元素默认值都为 0。
  3. 遍历原数组中的元素，以 原数组中的元素作为 count 数组的索引，以原数组中的元素呈现次数作为 count 数组的元素值。
  4. 创立后果数组 result，起始索引 index。
  5. 遍历 count 数组，找出其中元素值大于 0 的元素，将其对应的索引作为元素值填充到 result 数组中去，每解决一次，count 中的该元素值减 1，直到该元素值不大于 0，顺次解决 count 中剩下的元素。
  6. 返回后果数组 result。

java 实现

package com.github.houbb.sort.core.api;

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;
import com.github.houbb.sort.core.util.InnerSortUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 计数排序
 *
 * @author binbin.hou
 * @since 0.0.8
 */
@ThreadSafe
public class CountingSortBasic extends AbstractSort {private static final Log log = LogFactory.getLog(CountingSortBasic.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {
        //1. 获取最大的元素
        int max = Integer.MIN_VALUE;
        for (Object object : original) {Integer integer = (Integer) object;
            max = Math.max(max, integer);
        }

        //2. 构建 count 列表
        int[] counts = new int[max + 1];
        //3. 遍历原数组中的元素，以原数组中的元素作为 count 数组的索引，以原数组中的元素呈现次数作为 count 数组的元素值。for (Object object : original) {Integer integer = (Integer) object;
            counts[integer]++;
        }

        //4. 后果构建
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到后果数组中
        for (int i = 0; i < counts.length; i++) {while (counts[i] > 0) {
                // i 实际上就是元素的值
                // 从左到右遍历，元素天然也就排序好了。// 雷同的元素会呈现屡次，所以才须要循环。original.set(index++, i);
                counts[i]--;

                if(log.isDebugEnabled()) {log.debug("后果数组：{}", original);
                }
            }
        }
    }

}

改良版

空间节约

实际上咱们创立一个比最大元素还要大 1 的数组，只是为了放下所有的元素而已。

然而它有一个缺点，那就是存在 空间节约 的问题。

比方一组数据 {101,109,102,110}，其中最大值为 110，依照根底版的思路，咱们须要创立一个长度为 111 的计数数组，然而咱们能够发现，它后面的[0,100] 的空间齐全节约了，那怎么优化呢？

将数组长度定为 max-min+1，即不仅要找出最大值，还要找出最小值，依据两者的差来确定计数数组的长度。

改进版本实现

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.Arrays;
import java.util.List;

/**
 * 计数排序
 *
 * @author binbin.hou
 * @since 0.0.8
 */
@ThreadSafe
public class CountingSort extends AbstractSort {private static final Log log = LogFactory.getLog(CountingSort.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {
        //1. 获取最大、最小的元素
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (Object object : original) {Integer integer = (Integer) object;
            max = Math.max(max, integer);
            min = Math.min(min, integer);
        }

        //2. 构建 count 列表
        int[] counts = new int[max-min + 1];
        //3. 遍历原数组中的元素，以原数组中的元素作为 count 数组的索引，以原数组中的元素呈现次数作为 count 数组的元素值。for (Object object : original) {Integer integer = (Integer) object;
            // 元素要减去最小值，再作为新索引
            counts[integer-min]++;
        }

        if(log.isDebugEnabled()) {log.debug("counts.length: {}", counts.length);
        }
        //4. 后果构建
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到后果数组中
        for (int i = 0; i < counts.length; i++) {while (counts[i] > 0) {
                // i 实际上就是元素的值
                // 从左到右遍历，元素天然也就排序好了。// 雷同的元素会呈现屡次，所以才须要循环。// 这里将减去的最小值对立加上
                original.set(index++, i+min);
                counts[i]--;

                if(log.isDebugEnabled()) {log.debug("后果数组：{}", original);
                }
            }
        }
    }

}

本人的思考

算法的实质

这个算法的实质是什么呢？

集体了解只须要保障两点：

（1）每一个元素，都有本人的一个元素地位

（2）雷同的元素，次数会减少。

算法的奇妙之处在于 间接利用数值自身所谓索引，间接跳过了排序比拟；利用技数，解决了反复数值的问题。

算法的有余

这个算法的奇妙之处，同时也是对应的限度：那就是只能间接比拟数字。如果是字符串呢？

一点想法

我最后的想法就是能够应用相似于 HashMap 的数据结构。这样能够解决元素过滤，次数统计的问题。

然而无奈解决排序问题。

当然了，如果应用 TreeMap 就太赖皮了，因为自身就是利用了树进行排序。

TreeMap 版本

咱们这里应用 TreeMap 次要有上面的目标：

（1）让排序不局限于数字。

（2）大幅度降低内存的节约，不多一个元素，也不少一个元素。

思维实际上仍然是技术排序的思维。

package com.github.houbb.sort.core.api;

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * 计数排序 -TreeMap
 *
 * @author binbin.hou
 * @since 0.0.8
 */
@ThreadSafe
public class CountingSortTreeMap extends AbstractSort {private static final Log log = LogFactory.getLog(CountingSortTreeMap.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {TreeMap<Comparable, Integer> countMap = new TreeMap<>();

        // 初始化次数
        for (Object object : original) {Comparable comparable = (Comparable) object;

            Integer count = countMap.get(comparable);
            if(count == null) {count = 0;}
            count++;
            countMap.put(comparable, count);
        }

        //4. 后果构建
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到后果数组中
        for (Map.Entry<Comparable, Integer> entry : countMap.entrySet()) {int count = entry.getValue();
            Comparable key = entry.getKey();
            while (count > 0) {
                // i 实际上就是元素的值
                // 从左到右遍历，元素天然也就排序好了。// 雷同的元素会呈现屡次，所以才须要循环。original.set(index++, key);
                count--;
            }
        }
    }

}

桶排序（Bucket sort）

或所谓的箱排序，是一个排序算法，工作的原理是将数组分到无限数量的桶里。

每个桶再个别排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排序）。

桶排序是鸽巢排序的一种演绎后果。当要被排序的数组内的数值是平均调配的时候，桶排序应用线性工夫 O(n)。

桶排序是计数排序的扩大版本，计数排序能够看成每个桶只存储雷同元素，而桶排序每个桶存储肯定范畴的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最初将非空桶中的元素一一放入原序列中。

桶排序须要尽量保障元素扩散平均，否则当所有数据集中在同一个桶中时，桶排序生效。

算法流程

桶排序以下列程序进行：

  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列，并且把我的项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把我的项目再放回原来的序列中。

java 实现

实现

package com.github.houbb.sort.core.api;

import com.github.houbb.heaven.annotation.ThreadSafe;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序
 *
 * @author binbin.hou
 * @since 0.0.9
 */
@ThreadSafe
public class BucketSort extends AbstractSort {private static final Log log = LogFactory.getLog(BucketSort.class);

    @Override
    @SuppressWarnings("all")
    public void doSort(List original) {
        final int step = 10;

        // 计算最小值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(Object object : original) {Integer integer = (Integer) object;
            min = Math.min(min, integer);
            max = Math.max(max, integer);
        }

        //2. 计算桶的个数
        int bucketNum = (max-min) / step + 1;;
        //2.1 初始化长期列表
        List<List<Integer>> tempList = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++) {tempList.add(new ArrayList<Integer>());
        }

        //3. 将元素放入桶中
        // 这里有一个限度：要求元素必须一个右边的桶元素，要小于左边的桶。// 这就限度了只能是数字类的比拟，不然没有范畴的概念
        for(Object o : original) {Integer integer = (Integer) o;
            int index = (integer-min) / step;

            tempList.get(index).add(integer);
        }

        // 4. 针对单个桶进行排序
        // 能够抉择任意你喜爱的算法
        for(int i = 0; i < bucketNum; i++) {Collections.sort(tempList.get(i));
        }

        //5. 设置后果
        int index = 0;
        for(int i = 0; i < bucketNum; i++) {List<Integer> integers = tempList.get(i);

            for(Integer val : integers) {original.set(index++, val);
            }
        }
    }

}

开源地址

为了便于大家学习，下面的排序曾经开源，开源地址：

https://github.com/houbb/sort

欢送大家 fork/star，激励一下作者~~

小结

心愿本文对你有帮忙，如果有其余想法的话，也能够评论区和大家分享哦。

各位 极客 的点赞珍藏转发，是老马继续写作的最大能源！

正文完
面试
发表至： 面试
2020-11-23
 0
关于面试:大厂面试选择排序的特点与适用场景是什么
关于面试:2021Java后端工程师面试指南JVM
关于java:面试题-一个单调递增的数组-随机拿出一个数-你怎么找到这个数
关于面试:18年毕业历经3年到现在的快手架构师聊聊我的java后端学习之路