提高效率的本质：少做事情（效率＝产出／所做的事情）

public class Recursion{
    public static void main(String[] args){
        recursion(100);
    }    
    public int recursion(int n){
        if(n=1){
            return ;
        }
        return n*recursion(n-1);
    }
}

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {//控制已排序部分的长度
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {//找到未排序部分中的最小值，
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //将最小值和已排序部分的最后一个位置进行交换。
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {//控制排序轮数
            for (int j = 0; j < n - i - 1; j++) {//比较相邻元素并交换位置。
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

//该方法接受一个整型数组作为参数，对其进行插入排序。
//在方法中，变量 n 存储数组的长度。
//接着使用一个循环，从数组的第二个元素开始遍历，将其插入到已排序部分中。
//变量 key 存储当前要插入的元素，变量 j 存储已排序部分中最后一个元素的下标。使用一个 while 循环，将已排序部分中大于 key 的元素后移一位，直到找到 key 的插入位置。最后将 key 插入到数组中。

public static void insertionSort(int[] arr) {
    int n = arr.length;//存储数组的长度
    for (int i = 1; i < n; i++) {//从数组的第二个元素开始遍历，将其插入到已排序部分中
        int key = arr[i];// 存储当前要插入的元素
        int j = i - 1;//存储已排序部分中最后一个元素的下标
        while (j >= 0 && arr[j] > key) {//将已排序部分中大于 key 的元素后移一位，直到找到 key 的插入位置
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;//将 key 插入到数组中
    }
}

//mergeSort 方法对序列进行分割，merge 方法对分割后的序列进行合并。其中，temp 数组用于存储合并后的序列，i 和 j 分别表示左右子序列的起始位置，k 表示 temp 数组的当前位置。



public class MergeSort {
//对序列进行分割
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 分割序列
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            // 合并序列
            merge(arr, left, mid, right);
        }
    }
//对分割后的序列进行合并
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];//temp 数组用于存储合并后的序列
        int i = left, j = mid + 1, k = 0;//i 和 j 分别表示左右子序列的起始位置，k 表示 temp 数组的当前位置。
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 4};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

public class QuickSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = arr[(left + right) / 2];//用了 `pivot` 元素来将数组分为两个子数组，并递归对它们进行排序
        int i = left;
        int j = right;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

//定义了一个 heapSort 方法，它接受一个整数数组作为参数，然后对数组进行堆排序。
//在排序过程中，首先通过 heapify 方法建立一个最大堆。
//然后，从数组末尾开始，将最大值（根节点）与当前位置的元素交换，接着调整堆，使得交换后的剩余元素仍满足堆的性质。
//最终，通过不断重复这个过程，得到一个有序的数组。

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 建堆（构造最大堆）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 排序
        for (int i = n - 1; i > 0; i--) {
            // 将当前最大值（根节点）与最后一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整堆，使剩余元素仍满足最大堆性质
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i;  // 初始化最大值为当前节点
        int left = 2 * i + 1;  // 左子节点索引
        int right = 2 * i + 2;  // 右子节点索引

        // 如果左子节点大于最大值节点，更新最大值节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 如果右子节点大于最大值节点，更新最大值节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值节点不是当前节点，交换节点并递归调整堆
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}