【常用排序算法】

写在最前面

只想用其中的某个算法？

如果你只是想要对应的排序算法，可删除每个排序类的以下三处

• extends SortTest
• main方法
• @Override

比如，对于冒泡排序，删除下图中框选出来的即可单独使用

类关系图

所有排序算法皆继承SortTest，SortTest主要用于测试算法排序的效果（正确率如何）

工具类NumberArrayUtil

准备一个工具类，用于产生无序的数组

• createNumberArray(int count):产生一个长度为count的数组
• createNumberArrays()：产生一定量的无序数组

public class NumberArrayUtil {
    private static final Random RANDOM = new Random();
    /**
     * 数组的长度包含0 ~ MAX_VAL
     */
    private static final int MAX_VAL = 10;

    /**
     * 除了长度为0 ~ MAX_VAL长度的数组之外，再产生多少个数组
     */
    private static final int RANDOM_ARRAY_COUNT = 20;
    /**
     * 除了长度为0 ~ MAX_VAL长度的数组之外，再产生的数组最大长度
     */
    private static final int RANDOM_ARRAY_MAX_LENGTH = 100;

    /**
     * 产生指定长度的数组
     * @param count
     * @return
     */
    public static int[] createNumberArray(int count){
        int[] res = new int[count];
        for (int i = 0; i < res.length; i++) {
            res[i] =  RANDOM.nextInt();
        }

        return res;
    }

    /**
     * 产生一定量的随机长度的数组
     * @return
     */
    public static List<int[]> createNumberArrays(){
        List<int[]> res = new ArrayList<>();

        for (int i = 0; i < MAX_VAL; i++) {
            res.add(createNumberArray(i));
        }

        for (int i = 0; i < RANDOM_ARRAY_COUNT; i++) {
            res.add(createNumberArray(RANDOM.nextInt(RANDOM_ARRAY_MAX_LENGTH)));
        }

        return res;
    }

    /**
     * 判断两个数组的值是否相同
     * @param arr1
     * @param arr2
     * @return
     */
    public static boolean isSameArray(int[] arr1, int[] arr2){
        if (arr1.length != arr2.length){
            return false;
        }

        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]){
                return false;
            }
        }

        return true;
    }
}

用于测试排序的父类 SortTest

准备一个抽象类，用于快速测试我们写的算法，是否能完成排序

• test():子类调用，对我们实现的sort进行结果进行检验
• sort方法是抽象方法，子类需要重写，然后调用test方法，即可完成测试
• swap是交换两个索引处的值的方法，排序多会用到

public abstract class SortTest {
    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    public abstract int[] sort(int[] nums);

    /**
     * 用于检验排序结果
     */
    public void test() {
        List<int[]> numberArrays = NumberArrayUtil.createNumberArrays();
        int[] sort;
        int errorCount = 0;
        for (int[] numberArray : numberArrays) {
            int[] copy = Arrays.copyOf(numberArray, numberArray.length);
            sort = sort(Arrays.copyOf(numberArray, numberArray.length));
            Arrays.sort(copy);
            if (!NumberArrayUtil.isSameArray(sort, copy)) {
                System.out.println(Arrays.toString(numberArray) + "排序出错,排序后的结果：\n" + Arrays.toString(sort));
                System.out.println();
                errorCount++;
            }
        }
        
        System.out.println("测试完成！共计：" + numberArrays.size() + "个，出错个数：" + errorCount);
    }

    /**
     * 交换
     *
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

冒泡排序

public class BubbleSort extends SortTest{
    public static void main(String[] args) {
        new BubbleSort().test();
    }

    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        //排序次数
        boolean isSwap;
        for (int i = 0; i < nums.length - 1; i++) {
            //选出第i大的
            isSwap = false;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]){
                    swap(nums, j, j + 1);
                    isSwap = true;
                }
            }
            if (!isSwap){
                break;
            }
        }

        return nums;
    }
}

堆排序

public class HeapSort extends SortTest {
    public static void main(String[] args) {
        new HeapSort().test();
    }
    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        //初始化一个大顶堆
        buildMaxHeap(nums);

        //堆的大小，每次减少一个
        for (int i = nums.length - 1; i > 0; i--) {
            //和最后面交换
            swap(nums, 0, i);
            //构建堆,长度-1，最后一个放最大的
            heapify(nums, 0, i);
        }

        return nums;
    }

    private void buildMaxHeap(int[] nums) {
        //从倒数第二层最后一个往前，依次构建堆
        int len = nums.length;
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(nums, i, len);
        }
    }

    /**
     * 构建堆
     *
     * @param nums
     * @param index 起始索引
     * @param len   有效长度
     */
    private void heapify(int[] nums, int index, int len) {
        if (index >= nums.length){
            return;
        }

        int left = 2 * index + 1;
        int right = 2 * index + 2;

        //当前节点和其两个子节点，最大值处对应的索引
        int maxIndx = index;

        //是否子节点比当前节点大
        if (left < len && nums[left] > nums[maxIndx]) {
            maxIndx = left;
        }
        if (right < len && nums[right] > nums[maxIndx]) {
            maxIndx = right;
        }

        //和子节点交换，并对子节进行重新构建堆
        if (maxIndx != index) {
            swap(nums, index, maxIndx);
            heapify(nums, maxIndx, len);
        }
    }
}

插入排序

public class InsertSort extends SortTest{
    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        //遍历
        for (int i = 1; i < nums.length; i++) {
            int tmp = nums[i];
            //如果比当前值大，都应该往后移动
            int j = i - 1;
            while (j >= 0 && nums[j] > tmp){
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = tmp;
        }

        return nums;
    }

    public static void main(String[] args) {
        new InsertSort().test();
    }
}

归并排序

public class MergeSort extends SortTest {
    public static void main(String[] args) {
        new MergeSort().test();
    }

    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private void sort(int[] nums, int left, int right) {
        //结束：
        if (right <= left) {
            return;
        }

        int mid = left + (right - left) / 2;
        //分成两个部分，分别排序
        sort(nums, left, mid);
        sort(nums, mid + 1, right);

        //归并
        int[] marge = marge(Arrays.copyOfRange(nums, left, mid + 1), Arrays.copyOfRange(nums, mid + 1, right + 1));
        System.arraycopy(marge, 0, nums, left, marge.length);
    }

    private int[] marge(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length + nums2.length];
        //已经添加的个数
        int index = 0;
        //两个指针
        int i = 0, j = 0;

        while (i < nums1.length && j < nums2.length) {
            //谁小，谁加入;//i或j增加
            if (nums1[i] > nums2[j]) {
                res[index++] = nums2[j++];
            } else {
                res[index++] = nums1[i++];
            }
        }
        //如果添加完了就结束
        if (index == res.length) {
            return res;
        }
        //没添加完，把某个数组剩余的部分拷贝进去
        if (i < nums1.length) {
            for (; i < nums1.length; i++) {
                res[index++] = nums1[i];
            }
        } else {
            for (; j < nums2.length; j++) {
                res[index++] = nums2[j];
            }
        }

        return res;
    }
}

快速排序

public class QuickSort extends SortTest{
    public static void main(String[] args) {
        new QuickSort().test();
    }

    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    private void sort(int[] nums, int left, int right) {
        //结束：
        if (left >= right){
            return;
        }

        //排序
        //基准
        int val = nums[left];
        int i = left, j = right;
        while (i < j){
            //右边先移动
            while (j > i && nums[j] >= val){
                j--;
            }
            //换到左边
            nums[i] = nums[j];
            //左边移动
            while (i < j && nums[i] <= val){
                i++;
            }
            //换到右边
            nums[j] = nums[i];
        }
        nums[i] = val;

        //排左边
        sort(nums, left, i - 1);
        //排右边
        sort(nums, i + 1, right);
    }
}

选择排序

public class SelectionSort extends SortTest{

    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        //要选n-1次
        for (int i = 0; i < nums.length - 1; i++) {
            //每次找最小的放前面
            int min = nums[i];
            int index = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (min > nums[j]){
                    min = nums[j];
                    index = j;
                }
            }
            //交换
            swap(nums, i, index);
        }

        return nums;
    }

    public static void main(String[] args) {
        new SelectionSort().test();
    }
}

希尔排序

public class ShellSort extends SortTest {
    public static void main(String[] args) {
        new ShellSort().test();
    }

    /**
     * 排序方法
     *
     * @param nums
     * @return
     */
    @Override
    public int[] sort(int[] nums) {
        //步长
        int step = nums.length;

        for (int i = step; i > 0; i /= 2) {
            //以步长为i进行快速排序
            for (int j = 0; j < step; j++) {
                //对第j组进行排序，步长是i
                sort(nums, j, i);
            }
        }

        return nums;
    }

    /**
     * 希尔排序，对第startIndex组进行排序
     *
     * @param nums
     * @param startIndex 起始索引
     * @param step       步长
     */
    private void sort(int[] nums, int startIndex, int step) {
        for (int i = startIndex + step; i < nums.length; i += step) {
            int tmp = nums[i];
            //一直向前找，找到一个比当前值小的值
            int j = i - step;
            while (j >= 0 && nums[j] > tmp) {
                nums[j + step] = nums[j];
                j -= step;
            }

            //插入在其后面
            nums[j + step] = tmp;
        }
    }
}