快速排序

以下是Java中的快速排序算法实现：

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);  // 获取基准值的位置
            quickSort(arr, left, pivotIndex-1);  // 递归排序左边的子数组
            quickSort(arr, pivotIndex+1, right); // 递归排序右边的子数组
        }
    }
    
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left]; // 选择第一个元素作为基准值
        int i = left, j = right;
        while (i < j) {
            // 从右往左找到第一个小于基准值的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            
            // 从左往右找到第一个大于基准值的元素
            while (i < j && arr[i] < pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot; // 将基准值放到最终位置
        return i;
    }
}

快速排序的基本思路是在数组中选择一个元素作为基准值，然后将小于基准值的元素放在其左侧，大于基准值的元素放在其右侧，然后递归对左右两个子数组进行排序。在上面的实现中，我们选择数组的第一个元素作为基准值，然后使用双指针的方式来进行元素的交换。时间复杂度为O(nlogn)，空间复杂度为O(logn)。

以下是带注释的Java插入排序算法实现：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        insertionSort(arr); // 调用插入排序方法
        System.out.println(Arrays.toString(arr)); // 输出排序后的数组
    }
    
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) { // 从第二个元素开始遍历
            int temp = arr[i]; // 当前要插入的元素
            int j = i - 1; // 已排序部分的最后一个元素的下标
            while (j >= 0 && arr[j] > temp) { // 在已排序部分中寻找插入位置
                arr[j+1] = arr[j]; // 将元素向后移动
                j--; // 继续向前寻找插入位置
            }
            arr[j+1] = temp; // 插入元素到正确位置
        }
    }
}

在插入排序算法中，我们使用两个循环来实现。外层循环从第二个元素开始遍历整个数组，内层循环在已排序部分中寻找当前要插入元素的正确位置。在内层循环中，我们使用while循环来找到要插入元素的正确位置，然后将其余元素向后移动，并将当前元素插入到正确位置。

时间复杂度为O(n^2)，空间复杂度为O(1)。插入排序在排序小数组时具有很好的性能，但对于大数组来说，效率较低。

插入排序

以下是Java中的插入排序算法实现：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
    }
}

插入排序的基本思路是将数组分为已排序和未排序两部分，每次从未排序部分中选择一个元素插入到已排序部分的适当位置，使得插入后仍保持有序。在上面的实现中，我们从第二个元素开始，将其与已排序部分中的元素比较，找到插入位置后插入，并将其余元素后移。时间复杂度为O(n^2)，空间复杂度为O(1)。虽然插入排序时间复杂度较高，但是在实际使用中，由于其空间复杂度较低，当数据规模较小时，插入排序可能会比其他排序算法更快。

冒泡排序

以下是Java中的冒泡排序算法实现：

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

冒泡排序的基本思路是将相邻的元素两两比较，如果前一个元素比后一个元素大，则交换这两个元素的位置，一轮比较后，最大的元素将会被移动到最后一个位置，接着对未排序部分进行下一轮比较。在上面的实现中，我们使用两个嵌套的循环来实现冒泡排序。时间复杂度为O(n^2)，空间复杂度为O(1)。尽管冒泡排序在时间和空间复杂度方面不如其他排序算法，但由于其简单易懂的实现方式，仍被广泛地使用在各种场景中。

以下是带注释的Java冒泡排序算法实现：

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        bubbleSort(arr); // 调用冒泡排序方法
        System.out.println(Arrays.toString(arr)); // 输出排序后的数组
    }
    
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { // 外层循环控制比较轮数
            for (int j = 0; j < arr.length - i - 1; j++) { // 内层循环控制每轮比较次数
                if (arr[j] > arr[j+1]) { // 如果前一个元素比后一个元素大，交换它们的位置
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

冒泡排序的基本思路是将相邻的元素两两比较，如果前一个元素比后一个元素大，则交换这两个元素的位置，一轮比较后，最大的元素将会被移动到最后一个位置，接着对未排序部分进行下一轮比较。在上面的实现中，我们使用两个嵌套的循环来实现冒泡排序。时间复杂度为O(n^2)，空间复杂度为O(1)。尽管冒泡排序在时间和空间复杂度方面不如其他排序算法，但由于其简单易懂的实现方式，仍被广泛地使用在各种场景中。