/**
 * 冒泡排序
 *
 * @param nums 待排序数组
 */
public static void BubbleSort(int[] nums) {
    // 初始化两个指针,slow和fast
    int slow = 0, fast = 1;
    // 外层循环,遍历整个数组
    for (int i = 0; i < nums.length; i++) {
        // 内层循环,遍历未排序的部分
        while (fast < nums.length - i) {
            // 如果slow指向的元素大于fast指向的元素,交换它们
            if (nums[slow] > nums[fast]) {
                int tmp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = tmp;
            }
            // 移动slow和fast指针
            slow++;
            fast++;
            // 打印每次排序后的结果
            print(nums);
        }
        // 重置slow和fast指针
        slow = 0;
        fast = 1;
    }
}

/**
 * 选择排序
 * @param nums 待排序数组
 */
public static void selectionSort(int[] nums) {
    // 遍历整个数组
    for (int i = 0; i < nums.length; i++) {
        // 假设当前索引为最小元素的索引
        int minIndex = i;
        // 从当前索引的下一个元素开始,遍历未排序的部分
        for (int j = i + 1; j < nums.length; j++) {
            // 如果找到比当前最小元素还小的元素,更新最小元素的索引
            if (nums[minIndex] > nums[j]) {
                minIndex = j;
            }
        }
        // 将找到的最小元素与未排序部分的第一个元素交换位置
        int tmp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = tmp;
        // 打印每次排序后的结果
        print(nums);
    }
}

/**
 * 插入排序
 *
 * @param nums 待排序数组
 */
public static void InsertionSort(int[] nums) {
    // 从第二个元素开始遍历数组
    for (int i = 1; i < nums.length; i++) {
        // preIndex是待插入元素的前一个元素的索引
        int preIndex = i - 1;
        // current是待插入的元素
        int current = nums[i];
        // 当preIndex不小于0且待插入元素小于前一个元素时,将前一个元素后移一位
        while (preIndex >= 0 && current < nums[preIndex]) {
            nums[preIndex + 1] = nums[preIndex];
            preIndex--;
        }
        // 找到了待插入元素的位置,插入元素
        nums[preIndex + 1] = current;
    }
}

/**
 * 希尔排序
 *
 * @param nums 待排序数组
 */
public static void ShellSort(int[] nums) {
    // 定义初始间隔为数组长度的一半
    int gap = nums.length / 2;
    // 当间隔大于0时,继续排序
    while (gap > 0) {
        // 从间隔位置开始,遍历数组
        for (int i = gap; i < nums.length; i++) {
            // preIndex是待插入元素的前一个元素的索引
            int preIndex = i - gap;
            // current是待插入的元素
            int current = nums[i];
            // 当preIndex不小于0且待插入元素小于前一个元素时,将前一个元素后移一位
            while (preIndex >= 0 && current < nums[preIndex]) {
                nums[preIndex + gap] = nums[preIndex];
                preIndex -= gap;
            }
            // 找到了待插入元素的位置,插入元素
            nums[preIndex + gap] = current;
        }
        // 更新间隔为原来的一半
        gap /= 2;
    }
}

/**
 * 归并排序
 * @param nums 待排序数组
 * @return 排序后数组
 */
public static int[] MergeSort(int[] nums) {
    // 如果数组长度小于等于1,直接返回
    if (nums.length <= 1) return nums;
    // 计算中间位置
    int middle = nums.length / 2;
    // 将数组分为两部分
    int[] nums1 = Arrays.copyOfRange(nums, 0, middle);
    int[] nums2 = Arrays.copyOfRange(nums, middle, nums.length);
    // 对两部分分别进行归并排序,然后合并结果
    return merge(MergeSort(nums1), MergeSort(nums2));
}

/**
 * 归并排序合并方法
 * @param nums1 合并有序数组1
 * @param nums2 合并有序数组 2
 * @return 合并后有序数组
 */
public static int[] merge(int[] nums1, int[] nums2) {
    // 创建一个新数组,长度为两个输入数组的长度之和
    int[] nums = new int[nums1.length + nums2.length];
    // 初始化三个指针,p指向新数组,p1和p2分别指向两个输入数组
    int p = 0, p1 = 0, p2 = 0;
    // 当两个输入数组都有元素时,比较当前元素,将较小的元素放入新数组
    while (p1 < nums1.length && p2 < nums2.length) {
        if (nums1[p1] < nums2[p2]) {
            nums[p] = nums1[p1];
            p1++;
        } else {
            nums[p] = nums2[p2];
            p2++;
        }
        p++;
    }
    // 如果第一个数组还有剩余元素,将它们复制到新数组
    if (p1 < nums1.length) {
        while (p1 < nums1.length) {
            nums[p] = nums1[p1];
            p1++;
            p++;
        }
    } 
    // 如果第二个数组还有剩余元素,将它们复制到新数组
    else {
        while (p2 < nums2.length) {
            nums[p] = nums2[p2];
            p2++;
            p++;
        }
    }

    // 返回新数组
    return nums;
}