字符串二分查找、快速排序

Dear 丶 2022-03-18 06:24 204阅读 0赞

public class Main {
        /**
         * 字符串的二分查找
         * @param str
         * @param strs
         * @return
         */
        public static int binarySearch(String str, String[] strs) {
            int low = 0, high = strs.length - 1;
            while (low <= high) {
                int middle = (low + high) >>> 1;
                int temp = strs[middle].compareTo(str);
                if (temp < 0)
                    low = middle + 1;
                else if (temp > 0)
                    high = middle - 1;
                else
                    return middle;
            }
            return -1;
        }
    
        /**
         * 快速排序
         * @param arr
         * @param low
         * @param high
         */
        public static void quickSort(int[] arr, int low, int high) {
            if (low >= high) {
                return;
            }
            int i = low;
            int j = high;
            int index = arr[i];
            while (i < j) {
                while (i < j && arr[j] >= index)
                    j--;
                if (i < j)
                    arr[i++] = arr[j];
                while (i < j && arr[i] < index)
                    i++;
                if (i < j)
                    arr[j--] = arr[i];
            }
            arr[i] = index;
            quickSort(arr, low, i - 1);
            quickSort(arr, i + 1, high);
        }
    
        public static void main(String[] args) {
            String[] strs = {"asd", "eqw", "asddsf", "qwe", "fdv", "gdf", "re", "opm"};
            Arrays.sort(strs);
            System.out.println(Arrays.toString(strs));
            System.out.println(binarySearch("opm", strs));
    
            int[] arr = {72, 6, 57, 88, 60, 42};
            Arrays.sort(args);
            System.out.println(Arrays.toString(arr));
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    }

打印结果：

[asd, asddsf, eqw, fdv, gdf, opm, qwe, re]
    5
    [72, 6, 57, 88, 60, 42]
    [6, 42, 57, 60, 72, 88]