教科书的5道最常见算法题

未分类

一、二分查找

    public int binarySearch(int[] a, int key) {
        if (a == null) {
            return -1;
        }
        int low = 0, high = a.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (a[mid] == key) {
                return mid;
            } else if (a[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

二、冒泡算法

public void bubbleSort(int[] a) {
    int temp;
    for (int i = 1; i < a.length; i++) {
        for (int j = 0; j < a.length - i; j++) {
            if (a[j + 1] < a[j]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

三、快速排序

    public void quickSort(int[] a) {
        // 使用qSort函数封装排序细节
        qSort(a, 0, a.length - 1);
    }
    public void qSort(int[] a, int low, int high) {
        if (low < high) {
            int qivot = Partition(a, low, high);
            qSort(a, low, qivot - 1);
            qSort(a, qivot + 1, high);          
        }
    }
    public int Partition(int[] a, int i, int j) {
        // 1.取第一记录为支点
        int pivot = a[i];
        // 2.将小于支点的记录放支点左边，将大于支点的记录放右边
        while (i<j) {
            while(i<j && pivot <= a[j]){
                j--;
            }
            if (i<j) {
                a[i] = a[j];
                i++;
            }
            while(i<j && pivot > a[i]){
                i++;
            }
            if (i<j) {
                a[j] = a[i];
                j--;
            }
        }
        // 3.将支点放到中间位置,这时 i == j
        a[i] = pivot;
        // 4.返回支点位置
        return i;
    }

四、堆排序

五、归并排序