冒泡, 选择, 插入, 快速排序

SortMethodsImpl.java

package utils;

/**
 * @author Tiam
 * @date 2023/3/27 20:59
 * @description
 */
public class SortMethodsImpl implements SortMethods {

    public void swap(int[] arr, int i, int j) {
        if (i == j) return;
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    @Override
    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
            }
        }
    }

    @Override
    public void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) swap(arr, i, j);
            }
        }
    }

    @Override
    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1; j--) {
                if (arr[j] >= arr[j - 1]) break;
                swap(arr, j, j - 1);
            }
        }
    }
    @Override
    public void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int low, int high) {
        if (low >= high) return;
        // 将第一位做基准数, 使base左边都比base小, base右边都比base大
        int base = arr[low], i = low, j = high;
        while (i < j) {
            while (arr[j] >= base && i < j) j--;
            while (arr[i] <= base && i < j) i++;
            if (i < j) swap(arr, i, j);
        }
        // 交换基准数到中间
        swap(arr, low, i);
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}