基础的排序与搜索算法

import java.util.ArrayList;

class BubbleSort {
    /**
     * 冒泡排序
     * @param list 要排序的数组
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> list) {
        ArrayList<Integer> sorted = new ArrayList<>(list); // 复制一份原数组，不改变原数组

        boolean swapped; // 是否发生过交换
        do {
            swapped = false; // 每次开始排序前，假设没有发生过交换
            for (int i = 0; i < sorted.size() - 1; i++) { // 遍历数组，只遍历到倒数第二个元素（因为最后一个元素后面没有元素与之比较）
                if (sorted.get(i) > sorted.get(i + 1)) { // 如果当前元素比后一个元素大
                    // 交换两个元素
                    int tmp = sorted.get(i);
                    sorted.set(i, sorted.get(i + 1));
                    sorted.set(i + 1, tmp);
                    // 交换过元素后，将swapped设为true
                    swapped = true;
                }
            }
        } while (swapped); // 如果发生过交换，继续排序，否则代表排序已经完成，退出循环

        return sorted;
    }
}

class SelectionSort {
    /**
     * 选择排序
     * @param list 要排序的数组
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> list) {
        ArrayList<Integer> sorted = new ArrayList<>(list); // 复制一份原数组，不改变原数组

        int min, minIndex; // 最小值和最小值的索引

        for (int i = 0; i < sorted.size() - 1; i++) { // 遍历数组，只遍历到倒数第二个元素（因为最后一个元素不需要再比较/交换了）
            // i 同时代表要找到的第 i 小的元素的索引
            min = sorted.get(i); // 假设当前元素是最小值
            minIndex = i; // 假设当前元素的索引是最小值的索引

            for (int j = i + 1; j < sorted.size(); j++) { // 遍历当前元素之后的所有元素，因为当前元素之前的元素已经是有序的而且一定比当前元素小
                if (min > sorted.get(j)) { // 如果有比当前元素更小的元素
                    min = sorted.get(j); // 更新最小值
                    minIndex = j; // 更新最小值的索引
                }
            }

            // 将最小值与当前元素交换
            // （就算最小值是默认的当前元素也不会有问题，因为相当于没有交换）
            int tmp = sorted.get(i);
            sorted.set(i, min);
            sorted.set(minIndex, tmp);
        }

        return sorted;
    }
}

class InsertionSort {
    /**
     * 插入排序
     * @param list 要排序的数组
     */
    public static ArrayList<Integer> sort(ArrayList<Integer> list) {
        ArrayList<Integer> sorted = new ArrayList<>(); // 需要一个新的数组来存放已排序的元素
        
        for (int i = 0; i < list.size(); i++) { // 遍历源数组
            int num = list.get(i); // 取出当前元素（要向已排序数组中插入的元素）
            if (i == 0) {
                // 如果已排序数组为空，直接将当前元素放入已排序数组
                sorted.add(num);
            } else {
                if (num <= sorted.get(0)) { // 如果当前元素小于等于已排序数组中的第一个元素
                    // 那么这个元素就是最小的
                    // 将已排序数组中的所有元素向后移动一个位置
                    sorted.add(sorted.get(sorted.size() - 1));
                    for (int j = sorted.size() - 2; j > 0; j--) {
                        sorted.set(j, sorted.get(j - 1));
                    }
                    // 将当前元素放入已排序数组的第一个位置
                    sorted.set(0, num);
                } else if (num > sorted.get(sorted.size() - 1)) {
                    // 如果当前元素比已排序数组中的最后一个元素大
                    // 直接将当前元素放入已排序数组的最后一个位置
                    sorted.add(num);
                } else {
                    // 否则，将当前元素插入到已排序数组中的合适位置
                    for (int j = 0; j < sorted.size() - 1; j++) { // 遍历已排序数组，找到合适的位置（搜索循环）
                        if (sorted.get(j) < num && num <= sorted.get(j + 1)) {
                            // 如果当前元素大于已排序数组中的第j个元素，且小于/等于第j+1个元素，那么当前元素应该插入到第j+1个位置
                            // 先将第j+1个位置以及之后的所有元素向后移动一个位置
                            sorted.add(sorted.get(sorted.size() - 1));
                            for (int k = sorted.size() - 2; k > j + 1; k--) {
                                sorted.set(k, sorted.get(k - 1));
                            }
                            // 将当前元素插入到第j+1个位置
                            sorted.set(j + 1, num);
                            break; // 不需要继续“搜索”循环了
                        }
                    }
                }
            }
        }

        return sorted;
    }
}

class LinearSearch {
    /**
     * 线性搜索
     * @param list 要搜索的数组
     * @param target 要搜索的目标
     * @return 目标在数组中的索引，如果不存在则返回 -1
     */
    public static int search(ArrayList<Integer> list, int target) {
        for (int i = 0; i < list.size(); i++) { // 遍历数组
            if (list.get(i) == target) { // 如果找到目标
                return i; // 返回目标的索引
            }
        }
        return -1; // 如果循环完整结束了，则代表没有找到目标，返回 -1
    }
}

class JumpSearch {
    /**
     * 跳跃搜索
     * @param list 要搜索的数组
     * @param target 要搜索的目标
     * @return 目标在数组中的索引，如果不存在则返回 -1
     */
    public static int search(ArrayList<Integer> list, int target) {
        int step = (int) Math.sqrt(list.size()); // 获取步长

        int idx; // 索引
        for (idx = 0; idx < list.size(); idx += step) { // 以步长为单位遍历数组
            if (list.get(idx) == target) { // 如果找到目标
                return idx; // 返回目标的索引
            }
            if (list.get(idx) > target) { // 如果当前元素大于目标，则目标在当前元素之前，上次检查的元素之后
                break; // 结束以步长为单位的遍历
            }
        }

        // 回退一个步长，回到上次检查的元素，遍历这个步长内的元素（或者直到数组末尾）
        for (int i = idx - step; i < idx && i < list.size(); i++) {
            if (list.get(i) == target) { // 如果找到目标
                return i; // 返回目标的索引
            }
        }

        return -1; // 如果循环完整结束了，则代表没有找到目标，返回 -1
    }
}

class BinarySearch {
    /**
     * 二分搜索
     * @param list 要搜索的数组
     * @param target 要搜索的目标
     * @return 目标在数组中的索引，如果不存在则返回 -1
     */
    public static int search(ArrayList<Integer> list, int target) {
        int low = 0; // 低位索引
        int high = list.size() - 1; // 高位索引

        while (low <= high) { // 当低位索引小于等于高位索引时，才有元素可以搜索
            int mid = (low + high) / 2; // 计算中间索引
            if (list.get(mid) == target) { // 如果找到目标
                return mid; // 返回目标的索引
            } else if (list.get(mid) < target) { // 如果中间元素小于目标，则目标在中间元素之后
                low = mid + 1; // 低位索引更新为中间索引加一，在中间元素之后的元素中搜索
            } else { // 如果中间元素大于目标，则目标在中间元素之前
                high = mid - 1; // 高位索引更新为中间索引减一，在中间元素之前的元素中搜索
            }
        }

        return -1; // 如果循环完整结束了，则代表没有找到目标，返回 -1
    }
}