冒泡 选择 二分

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class App {

    public static final int LENGTH = 6;
    public static Random random = new Random();
    public static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        // 创建一个长度为LENGTH的整型数组
        int[] arr = new int[LENGTH];
        // 初始化数组
        initArray(arr);
        // 打印排序之前的数组
        traverseArray(arr);
        // 使用冒泡排序对数组进行排序
        bubbleSort(arr);
        // 打印冒泡排序之后的数组
        traverseArray(arr);
        // 使用选择排序对数组进行排序
        selectionSort(arr);
        // 打印选择排序之后的数组
        traverseArray(arr);
        // 使用反转排序对数组进行排序
        reverseSort(arr);
        // 打印反转排序之后的数组
        traverseArray(arr);
        // 提示用户输入待查找的元素
        System.out.print("请选择待查找的元素:   ");
        // 读取用户输入的待查找元素
        int targetNum = scanner.nextInt();
        // 使用二分查找算法查找目标元素的索引
        int index = binnarySearch(arr, targetNum);
        // 打印查找结果
        System.out.println(index);
    }

    // private static int binnarySearch(int[] arr, int targetNum) {
    //     for (int low = 0, high = arr.length - 1; low <= high;) {
    //         int mid = (low + high) / 2;
    //         if (targetNum > arr[mid]) {
    //             low = mid + 1;
    //             continue;
    //         } else if (targetNum < arr[mid])
    //             high = mid - 1;
    //         else
    //             return mid;
    //     }
    //     return -1;
    // }

    /**
     * 使用二分查找算法在有序数组中查找指定元素的索引
     * 二分查找通过不断缩小搜索范围来提高查找效率，是一种高效的查找算法
     * 
     * @param arr 一个已按升序排列的整型数组
     * @param targetNum 需要查找的目标数字
     * @return 如果目标数字存在于数组中，则返回其索引；否则返回-1
     */
    private static int binnarySearch(int[] arr, int targetNum) {
        // 初始化搜索范围的左右边界
        int left = 0;
        int right = arr.length - 1;
        // 计算中间位置的索引
        int mid = (left + right) / 2;
        // 当左边界不大于右边界时，表示搜索范围仍然有效
        while (left <= right) {
            // 检查中间位置的元素是否等于目标数字
            if (arr[mid] == targetNum)
                return mid;
            // 如果目标数字大于中间元素，调整左边界
            if (targetNum > arr[mid])
                left = mid + 1;
            // 如果目标数字小于中间元素，调整右边界
            if (targetNum < arr[mid])
                right = mid - 1;
            // 重新计算中间位置的索引
            mid = (left + right) / 2;
        }
        // 如果没有找到目标数字，返回-1
        return -1;
    }


    /**
     * Reverse sorts the given array in place.
     * This method uses the XOR bitwise operation to swap elements, avoiding the need for a temporary variable.
     * 
     * @param arr The array to be reverse sorted.
     */
    private static void reverseSort(int[] arr) {
        // Iterate over the first half of the array elements
        for (int i = 0; i < arr.length / 2; i++) {
            // Use XOR bitwise operation to swap the elements at both ends, no need for a temporary variable
            int t = arr[i] ^ arr[arr.length - 1 - i];
            arr[i] ^= t;
            arr[arr.length - 1 - i] ^= t;
        }
    }

    /**
     * 使用选择排序算法对整数数组进行排序
     * 该方法在每一轮迭代中找到数组中最大的元素，并将其与当前位置的元素交换
     * 从而逐步将最大的元素移动到数组的末尾
     *
     * @param arr 待排序的整数数组
     */
    private static void selectionSort(int[] arr) {
        // 遍历数组，除了最后一个元素，因为最后一步排序会将其放置在正确的位置
        for (int i = 0; i < arr.length - 1; i++) {
            // 假设当前遍历的元素是最大的
            int maxIndex = i;
            // 获取假设的最大值
            int maxValue = arr[maxIndex];
            // 遍历当前元素之后的所有元素，寻找实际的最大值
            for (int j = i + 1; j < arr.length; j++) {
                // 如果找到比当前最大值更大的元素
                if (arr[j] > maxValue) {
                    // 更新最大值及其索引
                    maxValue = arr[j];
                    maxIndex = j;
                }
            }
            // 如果最大值的索引发生变化，则交换最大值和当前位置的元素
            if (maxIndex != i) {
                // 使用位运算进行无变量交换
                int t = arr[maxIndex] ^ arr[i];
                arr[maxIndex] ^= t;
                arr[i] ^= t;
            }
        }
    }

/**
 * 使用冒泡排序算法对整数数组进行排序
 * 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数组，比较相邻的元素并交换它们，直到数组排序完成
 * 
 * @param arr 待排序的整数数组
 */
private static void bubbleSort(int[] arr) {
    // 遍历数组，每次迭代将最大的元素移动到数组的末尾
    for (int i = 0; i < arr.length - 1; i++) {
        // 在每次迭代中，比较并交换相邻的元素
        for (int j = 0; j < arr.length - 1 - i; j++) {
            // 如果当前元素大于下一个元素，则交换它们
            if (arr[j] > arr[j + 1]) {
                // 使用位运算进行无临时变量交换
                int t = arr[j] ^ arr[j + 1];
                arr[j] ^= t;
                arr[j + 1] ^= t;
            }
        }
    }
}

/**
 * 打印整型数组

 * 本方法通过接收一个整型数组作为参数，并将其转换为字符串形式打印出来
 * 这样做可以方便地展示数组中的所有元素，有助于调试和查看数组内容
 *
 * @param arr 需要打印的整型数组
 */
private static void traverseArray(int[] arr) {
    System.out.println(Arrays.toString(arr));
}

/**
 * 初始化整型数组
 * @param arr 需要初始化的整型数组
 * 此方法通过为数组的每个元素赋予一个随机数（范围为0到99），来实现数组的初始化
 * 选择0到99的范围是为了确保随机数的范围既不太小也不太大，以便在各种情境下使用
 */
private static void initArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }
}

}