java 二分查找和排序

二分法查找

public static int binarySearch(int[] a, int key) {
        if (a.length == 0) {
            return -1;
        }
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            int midValue = a[mid];
            if (key == midValue) {
                return mid;
            } else if (key < midValue) {
                // 左边
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

冒泡排序

    public static void bubbleSort(int[] a) {
        if (a.length <= 1) {
            return;
        }

        // 一共循环 a.length -1 趟
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                int left = a[j];
                int right = a[j + 1];
                if (left > right) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

选择排序

    public static void selectSort(int[] a) {
        if (a.length <= 1) {
            return;
        }
        // 循环 a.length - 1 趟
        // 每趟选出最小的值
        for (int i = 0; i < a.length - 1; i++) {
            int lowestIndex = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[lowestIndex] > a[j]) {
                    lowestIndex = j;
                }
            }
            if (lowestIndex != i) {
                int temp = a[i];
                a[i] = a[lowestIndex];
                a[lowestIndex] = temp;
            }

        }
    }

插入排序

public static void insertionSort(int[] a) {
        if (a.length <= 1) {
            return;
        }

        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > temp) {
                // 右移动
                a[j + 1] = a[j];
                j--;
            }

            a[j + 1] = temp;
        }
    }

快速排序

  public static void quickSort(int[] a, int left, int right) {
        if (a.length <= 1) {
            return;
        }

        if (left > right) {
            return;
        }

        int pivot = a[left];
        int i = left;
        int j = right;

        while (i != j) {
            // 先从右边开始比对
            while (a[j] >= pivot && i < j) {
                // 右边左移
                j--;
            }

            // 再比对左边
            while (a[i] <= pivot && i < j) {
                // 左边右移
                i++;
            }

            // 交换i 和 j的位置
            if (i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }

        }

        // 当i == j 的时候， 说明找到了中轴的正确位置, 将中轴值赋予在中轴位置
        a[left] = a[i];
        a[i] = pivot;

        // 再次分两边 递归排序 其中i的位置已经是真正的中轴位置，是已经排好了的
        // 左边
        quickSort(a, left, i - 1);
        // 右边
        quickSort(a, i + 1, right);
    }