算法(01)排序

//工具类
//断言类

public class Asserts {
    public static void test(boolean value) {
        try {
            if (!value) throw new Exception("测试未通过");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

//数组生成类

public class Integers {
    public static Integer[] random(int count, int min, int max) {
        if (count <= 0 || min > max) return null;
        Integer[] array = new Integer[count];
        int delta = max - min + 1;
        for (int i = 0; i < count; i++) {
            array[i] = min + (int)(Math.random() * delta);
        }
        return array;
    }
    
    public static Integer[] combine(Integer[] array1, Integer[] array2) {
        if (array1 == null || array2 == null) return null;
        Integer[] array = new Integer[array1.length + array2.length];
        for (int i = 0; i < array1.length; i++) {
            array[i] = array1[i];
        }
        for (int i = 0; i < array2.length; i++) {
            array[i + array1.length] = array2[i];
        }
        return array;
        
    }
    
    public static Integer[] same(int count, int unsameCount) {
        if (count <= 0 || unsameCount > count) return null;
        Integer[] array = new Integer[count];
        for (int i = 0; i < unsameCount; i++) {
            array[i] = unsameCount - i;
        }
        for (int i = unsameCount; i < count; i++) {
            array[i] = unsameCount + 1;
        }
        return array;
    }
    
    public static Integer[] headTailAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        
        int begin = (array.length - disorderCount) >> 1;
        reverse(array, begin, begin + disorderCount);
        return array;
    }
    
    public static Integer[] centerAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        int left = disorderCount >> 1;
        reverse(array, 0, left);
        
        int right = disorderCount - left;
        reverse(array, array.length - right, array.length);
        return array;
    }
    
    public static Integer[] headAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        reverse(array, array.length - disorderCount, array.length);
        return array;
    }
    
    public static Integer[] tailAscOrder(int min, int max, int disorderCount) {
        Integer[] array = ascOrder(min, max);
        if (disorderCount > array.length) return array;
        reverse(array, 0, disorderCount);
        return array;
    }
    
    public static Integer[] ascOrder(int min, int max) {
        if (min > max) return null;
        Integer[] array = new Integer[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            array[i] = min++;
        }
        return array;
    }
    
    public static Integer[] descOrder(int min, int max) {
        if (min > max) return null;
        Integer[] array = new Integer[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            array[i] = max--;
        }
        return array;
    }
    
    /**
     * 反转一个数组，索引范围是[begin, end)
     */
    private static void reverse(Integer[] array, int begin, int end) {
        int count = (end - begin) >> 1;
        int sum = begin + end - 1;
        for (int i = begin; i < begin + count; i++) {
            int j = sum - i;
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
    
    public static Integer[] copy(Integer[] array) {
        return Arrays.copyOf(array, array.length);
    }
    
    public static boolean isAscOrder(Integer[] array) {
        if (array == null || array.length == 0) return false;
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] > array[i]) return false;
        }
        return true;
    }
    
    public static void println(Integer[] array) {
        if (array == null) return;
        StringBuilder string = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            if (i != 0) string.append("_");
            string.append(array[i]);
        }
        System.out.println(string);
    }
}

//时间测试类

public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
    
    public interface Task {
        void execute();
    }
    
    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始：" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束：" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时：" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}

//排序

@SuppressWarnings("unchecked")
public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {
    protected T[] array;
    private int cmpCount;
    private int swapCount;
    private long time;
    private DecimalFormat fmt = new DecimalFormat("#.00");
    
    public void sort(T[] array) {
        if (array == null || array.length < 2) return;
        
        this.array = array;
        
        long begin = System.currentTimeMillis();
        sort();
        time = System.currentTimeMillis() - begin;
    }
    
    @Override
    public int compareTo(Sort<T> o) {
        int result = (int)(time - o.time);
        if (result != 0) return result;
        
        result = cmpCount - o.cmpCount;
        if (result != 0) return result;
        
        return swapCount - o.swapCount;
    }
    
    protected abstract void sort();
    
    /*
     * 返回值等于0，代表 array[i1] == array[i2]
     * 返回值小于0，代表 array[i1] < array[i2]
     * 返回值大于0，代表 array[i1] > array[i2]
     */
    protected int cmp(int i1, int i2) {
        cmpCount++;
        return array[i1].compareTo(array[i2]);
    }
    
    protected int cmp(T v1, T v2) {
        cmpCount++;
        return v1.compareTo(v2);
    }
    
    protected void swap(int i1, int i2) {
        swapCount++;
        T tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }
    
    @Override
    public String toString() { 
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
        String stableStr = "稳定性：" + isStable();
        return "【" + getClass().getSimpleName() + "】\n" 
                + stableStr + " \t"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";

    }
    
    private String numberString(int number) {
        if (number < 10000) return "" + number;
        
        if (number < 100000000) return fmt.format(number / 10000.0) + "万";
        return fmt.format(number / 100000000.0) + "亿";
    }
    
    private boolean isStable() {
        if (this instanceof RadixSort) return true;
        if (this instanceof CountingSort) return true;
        if (this instanceof ShellSort) return false;
        if (this instanceof SelectionSort) return false;
        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((T[]) students);
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != prevScore + 10) return false;
        }
        return true;
    }
}

冒泡

• 冒泡排序也叫做起泡排序
• 执行流程(本课程统一以升序为例子)
  1、 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置 ✓ 执行完一轮后，最末尾那个元素就是最大的元素
  2 、忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序

public class BubbleSort1<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                }
            }
        }
    }

}

public class BubbleSort2<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            boolean sorted = true;
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }

}

public class BubbleSort3<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }

}

选择

• 执行流程
  1 从序列中找出最大的那个元素，然后与最末尾的元素交换位置 ✓ 执行完一轮后，最末尾的那个元素就是最大的元素
  2 忽略 1 中曾经找到的最大元素，重复执行步骤 1

• 思考
  选择排序是否还有优化的空间? ✓ 使用堆来选择最大值

• 选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序

• 最好、最坏、平均时间复杂度:O(n2)，空间复杂度:O(1)，属于不稳定排序

public class SelectionSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        
//      for (int end = array.length - 1; end > 0; end--) {
//          int max = 0;
//          for (int begin = 1; begin <= end; begin++) {
//              if (cmp(max, begin) <= 0) {
//                  max = begin;
//              }
//          }
//          swap(max, end);
//      }
        
        for (int end = array.length - 1; end > 0; end--) {
            int max = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(max, begin) < 0) {
                    max = begin;
                }
            }
            swap(max, end);
        }
        
        // 7 5 10 1 4 2 10 
    }

}

堆排序

• 堆排序可以认为是对选择排序的一种优化
• 执行流程
  1 对序列进行原地建堆(heapify)
  2 重复执行以下操作，直到堆的元素数量为 1
  ✓ 交换堆顶元素与尾元素
  ✓堆的元素数量减 1
  ✓对 0 位置进行 1 次 siftDown 操作

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        
        while (heapSize > 1) {
            // 交换堆顶元素和尾部元素
            swap(0, --heapSize);

            // 对0位置进行siftDown（恢复堆的性质）
            siftDown(0);
        }
    }
    
    private void siftDown(int index) {
        T element = array[index];
        
        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];
            
            int rightIndex = childIndex + 1;
            // 右子节点比左子节点大
            if (rightIndex < heapSize && 
                    cmp(array[rightIndex], child) > 0) { 
                child = array[childIndex = rightIndex];
            }
            
            // 大于等于子节点
            if (cmp(element, child) >= 0) break;
            
            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
}

插入排序

• 插入排序非常类似于扑克牌的排序
• 执行流程
  1 在执行过程中，插入排序会将序列分为2部分
  ✓ 头部是已经排好序的，尾部是待排序的
  2 从头开始扫描每一个元素
  ✓ 每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序

public class InsertionSort1<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                swap(cur, cur - 1);
                cur--;
            }
        }
    }

}

public class InsertionSort2<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            T v = array[cur];
            while (cur > 0 && cmp(v, array[cur - 1]) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = v;
        }
    }

}

public class InsertionSort3<T extends Comparable<T>> extends Sort<T> {

    
//  protected void sort() {
//      for (int begin = 1; begin < array.length; begin++) {
//          T v = array[begin];
//          int insertIndex = search(begin);
//          // 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位
////            for (int i = begin - 1; i >= insertIndex; i--) {
////                
////            }
//          for (int i = begin; i > insertIndex; i--) {
//              array[i] = array[i - 1];
//          }
//          array[insertIndex] = v;
//      }
//  }
    
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            insert(begin, search(begin));
        }
    }
    
    /**
     * 将source位置的元素插入到dest位置
     * @param source
     * @param dest
     */
    private void insert(int source, int dest) {
        T v = array[source];
        for (int i = source; i > dest; i--) {
            array[i] = array[i - 1];
        }
        array[dest] = v;
    }
    
    /**
     * 利用二分搜索找到 index 位置元素的待插入位置
     * 已经排好序数组的区间范围是 [0, index)
     * @param index
     * @return
     */
    private int search(int index) {
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (cmp(array[index], array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}

归并排序

• 1945年由约翰·冯·诺伊曼(John von Neumann)首次提出

• 执行流程
  1 不断地将当前序列平均分割成2个子序列
  ✓ 直到不能再分割(序列中只剩1个元素)
  2 不断地将2个子序列合并成一个有序序列
  ✓ 直到最终只剩下1个有序序列

• 归并排序花费的时间
  T(n) =2∗T(n/2) +O(n)
  T1 =O(1)
  T(n) /n=T(n/2) /(n/2)+O(1)

• 令S(n) =T(n)/n
  S(1) =O(1)
  S(n) =S(n/2) +O(1)=S(n/4) +O(2)=S(n/8) +O(3)=S(n/2k) +O(k) =S(1)+O(logn)=O(logn)
  T(n) =n∗S(n) =O(nlogn)

• 由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是 O(nlogn) ，属于稳定排序

• 从代码中不难看出:归并排序的空间复杂度是On/2+logn =O(n)
  n/2 用于临时存放左侧数组，logn 是因为递归调用

@SuppressWarnings("unchecked")
public class MergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }
    
    // T(n) = T(n/2) + T(n/2) + O(n)
    
    /**
     * 对 [begin, end) 范围的数据进行归并排序
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }
    
    /**
     * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
     */
    private void merge(int begin, int mid, int end) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;
        
        // 备份左边数组
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }
        
        // 如果左边还没有结束
        while (li < le) { 
            if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
                array[ai++] = array[ri++];
            } else {
                array[ai++] = leftArray[li++];
            }
        }
    }
}

常见的递推式与复杂度

递推式 ---------------------> 复杂度
T(n) = T(n/2) + O(1) -------> O(logn)
T(n) =T(n−1) +O(1) --------> O(n)
T(n) = T(n/2) + O(n)-------->O(n)
T(n )=2∗T(n/2) +O(1)------->O(n)
T(n )=2∗T(n/2) +O(n)------->O(nlogn)
T(n)=T(n−1) +O(n)---------->O(n^2)
T(n) =2∗T(n−1) +O(1)------->O(2^n)
T(n) =2∗T(n−1) +O(n)------->O(2^n)

快速排序

• 1960年由查尔斯·安东尼·理查德·霍尔(Charles Antony Richard Hoare，缩写为C. A. R. Hoare)提出
  昵称为东尼·霍尔(Tony Hoare)

• 执行流程
  1 从序列中选择一个轴点元素(pivot)
  ✓假设每次选择 0 位置的元素为轴点元素
  2 利用 pivot 将序列分割成 2 个子序列
  ✓将小于 pivot 的元素放在pivot前面(左侧)
  ✓将大于 pivot 的元素放在pivot后面(右侧)
  ✓ 等于pivot的元素放哪边都可以
  3 对子序列进行 1 2 操作
  ✓ 直到不能再分割(子序列中只剩下1个元素)

• 快速排序的本质
  逐渐将每一个元素都转换成轴点元素

– 时间复杂度
◼ 在轴点左右元素数量比较均匀的情况下，同时也是最好的情况
T(n) =2∗T(n/2) +O n =O(nlogn)
◼ 如果轴点左右元素数量极度不均匀，最坏情况 T(n) =T(n−1) +O(n) =O(n^2)
◼ 为了降低最坏情况的出现概率，一般采取的做法是 随机选择轴点元素
◼ 最好、平均时间复杂度:O(nlogn)
◼ 最坏时间复杂度:O(n^2)
◼ 由于递归调用的缘故，空间复杂度:O(logn)
◼ 属于不稳定排序

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) { 
        if (end - begin < 2) return;
        
        // 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);
        // 对子序列进行快速排序
        sort(begin, mid); 
        sort(mid + 1, end); 
    } 
    
    /**
     * 构造出 [begin, end) 范围的轴点元素
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        // 随机选择一个元素跟begin位置进行交换
        swap(begin, begin + (int)(Math.random() * (end - begin)));
        
        // 备份begin位置的元素
        T pivot = array[begin];
        // end指向最后一个元素
        end--;
        
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) { // 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }
        
        // 将轴点元素放入最终的位置
        array[begin] = pivot;
        // 返回轴点元素的位置
        return begin;
    }
}

希尔排序

• 1959年由唐纳德·希尔(Donald Shell)提出
• 希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序
  𝑚 从某个整数逐渐减为1
  当 𝑚 为1时，整个序列将完全有序
• 因此，希尔排序也被称为递减增量排序(Diminishing Increment Sort)
• 矩阵的列数取决于步长序列(step sequence)
  ✓ 比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序
  ✓ 不同的步长序列，执行效率也不同

@SuppressWarnings("unused")
public class ShellSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        List<Integer> stepSequence = sedgewickStepSequence();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }
    
    /**
     * 分成step列进行排序
     */
    private void sort(int step) {
        // col : 第几列，column的简称
        for (int col = 0; col < step; col++) { // 对第col列进行排序
            // col、col+step、col+2*step、col+3*step
            for (int begin = col + step; begin < array.length; begin += step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur -= step;
                }
            }
        }
    }
    
    private List<Integer> shellStepSequence() {
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step >>= 1) > 0) {
            stepSequence.add(step);
        }
        return stepSequence;
    }
    
    private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }
}

计数

• 之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序
  平均时间复杂度目前最低是 O(nlogn)
• 计数排序、桶排序、基数排序，都不是基于比较的排序
  它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn)更低
• 计数排序于1954年由Harold H. Seward提出，适合对一定范围内的整数进行排序
• 计数排序的核心思想
  统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引

public class CountingSort extends Sort<Integer> {

    @Override
    protected void sort() {
        // 找出最值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        
        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] - min]] = array[i];
        }
        
        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
    
    protected void sort0() {
        // 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        } // O(n)
        
        // 开辟内存空间，存储每个整数出现的次数
        int[] counts = new int[1 + max];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i]]++;
        } // O(n)
        
        // 根据整数的出现次数，对整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; i++) {
            while (counts[i]-- > 0) {
                array[index++] = i;
            }
        } // O(n)
    }   
    
    public static void main(String[] args) {
        Person[] persons = new Person[] {
                new Person(20, "A"),
                new Person(-13, "B"),
                new Person(17, "C"),
                new Person(12, "D"),
                new Person(-13, "E"),
                new Person(20, "F")
        };
        
        // 找出最值
        int max = persons[0].age;
        int min = persons[0].age;
        for (int i = 1; i < persons.length; i++) {
            if (persons[i].age > max) {
                max = persons[i].age;
            }
            if (persons[i].age < min) {
                min = persons[i].age;
            }
        }
        
        // 开辟内存空间，存储次数
        int[] counts = new int[max - min + 1];
        // 统计每个整数出现的次数
        for (int i = 0; i < persons.length; i++) {
            counts[persons[i].age - min]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        Person[] newArray = new Person[persons.length];
        for (int i = persons.length - 1; i >= 0; i--) {
            newArray[--counts[persons[i].age - min]] = persons[i];
        }
        
        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            persons[i] = newArray[i];
        }
        
        for (int i = 0; i < persons.length; i++) {
            System.out.println(persons[i]);
        }
    }
    
    private static class Person {
        int age;
        String name;
        Person(int age, String name) {
            this.age = age;
            this.name = name;
        }
        @Override
        public String toString() {
            return "Person [age=" + age 
                    + ", name=" + name + "]";
        }
    }
}

基数

• 基数排序非常适合用于整数排序(尤其是非负整数)，因此本课程只演示对非负整数进行基数排序
• 执行流程:依次对个位数、十位数、百位数、千位数、万位数...进行排序(从低位到高位)
• 个位数、十位数、百位数的取值范围都是固定的0~9，可以使用计数排序对它们进行排序

public class RadixSort extends Sort<Integer> {

    @Override
    protected void sort() {
        // 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        
        // 个位数: array[i] / 1 % 10 = 3
        // 十位数：array[i] / 10 % 10 = 9
        // 百位数：array[i] / 100 % 10 = 5
        // 千位数：array[i] / 1000 % 10 = ...

        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider);
        }
    }
    
    protected void countingSort(int divider) {
        // 开辟内存空间，存储次数
        int[] counts = new int[10];
        // 统计每个整数出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] / divider % 10]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        
        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] / divider % 10]] = array[i];
        }
        
        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}

桶排序

• 执行流程
  1 创建一定数量的桶(比如用数组、链表作为桶)
  2 按照一定的规则(不同类型的数据，规则不同)，将序列中的元素均匀分配到对应的桶
  3 分别对每个桶进行单独排序
  4 将所有非空桶的元素合并成有序序列

• 元素在桶中的索引
  元素值 * 元素数量