常见排序的Java实现

背景

通过对常见排序的规则了解，按照自己理解实现。其实部分代码可再简化，为了更好的体现自己的实现步骤就没简化，这样有利于之后回顾思路。

常见排序

• 冒泡排序
• 选择排序
• 快速排序
• 归并排序
• 堆排序

import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author XiaoJia
 * @since 2020/5/3 21:21
 */
public class SimpleSortTest {
    int[] numbers;

    @Before
    public void before() {
        numbers = new int[]{0, 8, 7, 6, 5, 3, 4, 9, 2, 1};
    }

    @After
    public void after() {
        Assert.assertEquals(Arrays.toString(numbers), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
    }

    /**
     * 冒泡排序
     * <p>
     * 规则：按照升序（或降序）每次从第一个元素开始选出最大（或最小）的数
     * <p>
     * 时间复杂度：(n-1)+(n-2)+...+1 = n(n-1) / 2 看做 n^2
     */
    @Test
    public void bubbleSort() {
        // 每次获取最大数的填充位置 i
        for (int i = numbers.length - 1; i > 0; i--) {
            // 正在比较的数，通过交换位置保持比较结果
            for (int j = 0; j < i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j + 1];
                    numbers[j + 1] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * <p>
     * 规则：依次为每个位置选择最小的数组（相对冒泡排序无需不必要的数据位置交换）
     * <p>
     * 时间复杂度：(n-1)+(n-2)+...+1 = n(n-1) / 2 看做 n^2
     */
    @Test
    public void selectSort() {
        // 每次存放选择结果的位置 - i
        for (int i = 0; i < numbers.length - 1; i++) {
            // 存放临时比较的最大值与下标
            int temp = numbers[i];
            int tempIndex = i;
            // 比较两个数得较小值
            for (int j = i + 1; j < numbers.length; j++) {
                if (temp > numbers[j]) {
                    temp = numbers[j];
                    tempIndex = j;
                }
            }
            numbers[tempIndex] = numbers[i];
            numbers[i] = temp;
        }
    }

    /**
     * 快速排序
     * <p>
     * 规则：将数据拆分左右两个集合，左边集合所有元素必须都小于右边集合。如果集合元素大于1则按相同规则继续拆分
     * <p>
     * 时间复杂度：
     * 1. 最坏情况：每次拆分左边集合都只有一个元素，则时间复杂度与冒泡一样 n(n-1) / 2
     * 2. 最好情况：每次拆分左右集合元素相仿，则经过 log2(n) 次则拆分完成，每次拆分都会进行 n-1 次比较
     * 故 时间复杂度为 (n-1)log2(n) 看做 nlog2(n)
     */
    @Test
    public void quickSort() {
        // 选择第一个元素作为拆分元素，小于该元素则与其交互位置
        quickSplit(0, numbers.length - 1);
    }

    /**
     * 归并排序
     * <p>
     * 规则：分为两个步骤
     * 步骤一：拆分数据，每次将数据均分两个集合，直到集合元素个数为1
     * 步骤二：合并数据，依次从元素小的集合合并成较大的有序集合，直到所有集合都被合并
     * <p>
     * 时间复杂度：数据拆分次数为log2(n)，最坏情况是每个元素归并时都需要比较一次，
     * 故 时间复杂度为 (n-1)log2(n)
     */
    @Test
    public void mergeSort() {
        int[] result = new int[numbers.length];
        mergeSplitAndMerge(result, 0, numbers.length - 1);
    }

    /**
     * 堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
     * 1、堆中某个节点的值总是不大于或不小于其父节点的值；
     * 2、堆总是一棵完全二叉树。
     * <p>
     * 堆排序
     * <p>
     * 规则：先将无序集合调整为符合堆规范的集合，再将堆顶元素作为已排好序的数填充到指定位置（从最后位置到第一个位置依次填充）
     * 最大堆：父节点总大于或等于左右节点
     * 最小堆：父节点总小于或等于左右节点
     * <p>
     * 时间复杂度：log2(n) + log2(n-1) + ... + log2(1) = log2(n) * n / 2 看做 nlog2(n)
     */
    @Test
    public void headSort() {
        // 从最后一个非叶子节点从下往上、从右往左依次获取最大的父节点（最后一个元素的父节点为最后一个非叶子节点）
        for (int i = numbers.length / 2 - 1; i >= 0; i--) {
            adjustNode(i, numbers[i], numbers.length);
        }

        // 依次将通过堆获取的最大值保存到当次排序值的末尾，然后从上往下、从左往右依次获取最大的父节点
        for (int i = numbers.length - 1; i > 0; i--) {
            int temp = numbers[0];
            numbers[0] = numbers[i];
            numbers[i] = temp;
            adjustNode(0, numbers[0], i);
        }
    }

    private void quickSplit(int begin, int end) {
        if (begin >= end) {
            return;
        }

        // 记录当前拆分标准的位置
        int compare = numbers[begin];
        // 记录开始切分的位置
        int splitIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (compare > numbers[i]) {
                splitIndex++;
                // 判断是否交互位置
                if (splitIndex != i) {
                    int temp = numbers[i];
                    numbers[i] = numbers[splitIndex];
                    numbers[splitIndex] = temp;
                }
            }
        }

        // 拆分标准的位置与最后一个小于拆分标准的调换位置
        if (splitIndex != begin) {
            int temp = numbers[splitIndex];
            numbers[splitIndex] = numbers[begin];
            numbers[begin] = temp;
        }

        quickSplit(begin, splitIndex - 1);
        quickSplit(splitIndex + 1, end);
    }

    private void mergeSplitAndMerge(int[] temp, int begin, int end) {
        if (begin >= end) {
            return;
        }

        // 拆分并合并子数据
        int splitIndex = begin + (end - begin + 1) / 2 - 1;
        mergeSplitAndMerge(temp, begin, splitIndex);
        mergeSplitAndMerge(temp, splitIndex + 1, end);

        // 合并数据
        int firstIndex = begin;
        int secondIndex = splitIndex + 1;
        for (int i = begin; i <= end; i++) {
            if (numbers[firstIndex] < numbers[secondIndex]) {
                temp[i] = numbers[firstIndex];
                firstIndex++;
            } else {
                temp[i] = numbers[secondIndex];
                secondIndex++;
            }

            // 任何一个集合全部已排序则将另一个集合的未排序元素直接拷贝到目标集合中
            if (firstIndex > splitIndex) {
                System.arraycopy(numbers, secondIndex, temp, i + 1, end - i);
                break;
            } else if (secondIndex > end) {
                System.arraycopy(numbers, firstIndex, temp, i + 1, end - i);
                break;
            }
        }

        System.arraycopy(temp, begin, numbers, begin, end - begin + 1);
    }

    private void adjustNode(int index, int value, int length) {
        int temp = index;
        while (true) {
            int leftIndex = 2 * (temp + 1) - 1;
            int rightIndex = 2 * (temp + 1);
            // 左右节点的较大值
            int maxIndex;
            if (leftIndex > length - 1) {
                break;
            } else if (rightIndex > length - 1) {
                maxIndex = leftIndex;
            } else {
                maxIndex = numbers[leftIndex] > numbers[rightIndex] ? leftIndex : rightIndex;
            }
            // 与父节点的比较，如果父节点小于子节点则需要已子节点作为父节点再次更新
            if (numbers[maxIndex] > value) {
                numbers[temp] = numbers[maxIndex];
                numbers[maxIndex] = value;
                temp = maxIndex;
            } else {
                break;
            }
        }
    }
}