java-笔试-算法题，关联 面试

查找算法

二分查找

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class BinarySearchRecursive {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 4, 6, 8, 9 };
        int key = 4;
        int result = recursionBinarySearch(arr, key, 0, arr.length-1);
        
        System.out.println("searching " + key + " index is :" + result);
    }
    
    public static int recursionBinarySearch(int[] data, int key, int low, int high) {
        if( key < data[low] || key > data[high] || low > high) {
            return -1;
        }
        
        int middle = (low + high) / 2;
        if( key < data[middle] ) {
            return recursionBinarySearch(data, key, low, middle - 1);
        }
        if( key > data[middle] ) {
            return recursionBinarySearch(data, key, middle + 1, high);
        }
        return middle;
    }

}

不使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class BinarySearchNoRecursion {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    
    public static int commonBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;
        
        if( key < arr[low] || key > arr[high] || low > high ) {
            return -1;
        }
        
        while(low <= high) {
            middle = (low + high) / 2;
            if( arr[middle] > key ) {
                high = middle - 1;
            } else if ( arr[middle] < key ) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        
        return -1;
    }
}

插值查找算法

插值查找（Insert Value Search）是二分查找的一种改良，主要是改良了mid的值，mid的值由原来的mid = (left + right) / 2而变成了自适应获取mid的值mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left)，上述公式是前辈们推导出来的，其余和二分查找一样。

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。而关键字分布不均匀的情况下，该方法不一定比二分查找要好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int insertValueSearch(int[] arr, int num) {
    return insertValueSearch(arr, 0, arr.length - 1, num);
}
 
public static int insertValueSearch(int[] arr, int left, int right, int num) {
    //如果没有找到
    if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
        return -1;
    }
    //获取中间索引
    int mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left);
    //往左边递归找
    if (num < arr[mid]) {
        return insertValueSearch(arr, left, mid - 1, num);
    }
    //往右边递归找
    else if (num > arr[mid]) {
        return insertValueSearch(arr, mid + 1, right, num);
    }
    //数据位置找到
    else {
        return mid;
    }
}

斐波那契查找

黄金分割点查找：

黄金分割点查找要运用到斐波那契数列，要在该数列中从小到大找到一个数减一刚好大于等于待查找数组的长度，既顺序表长度n <= F[k] - 1
但顺序表长度 n 不一定刚好等于 F[k]-1，所以需要将原来的顺序表长度 n 增加至 F[k]-1（将最后一个字依次向后填充）。
这样一来带查找的顺序表就可以表示成：
由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到F[k]-1=（F[k-1]-1）+（F[k-2]-1）+1

黄金分割点的位置：mid = left + F(k - 1) - 1
注： 为什么是F[k] - 1,而不是F[k]?
因为斐波那契数列只有从第二个数开始与后一个数的比值才越来越接近黄金比率。
斐波那契数列的大小： 数组长度不同，那么对应所需要的斐波那契数列长度就不一样。若是写死，则很浪费空间。故斐波那契数列的大小可根据数组的大小进行选择。

当数组长度小于等于5时，数组的长度大于等于数组长度对应的斐波那契数，这时后面进行查找一个k使得fib[k]-1刚好大于等于数组长度就会越界，故写死，给一个6。产生的最大斐波那契数是8，大于数组长度，就不会越界
当数组长度大于5时，数组的长度小于数组长度对应的斐波那契数，斐波那契数组长度为待顺序表长度，不会产生越界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = {1,5,90,500,1000};
        FibonacciSearch fibonacciSearch = new FibonacciSearch();
        int i = fibonacciSearch.fibonacciSearch(arr, 1000);
        System.out.println("i = " + i);
    }

    /**
     * @Description: fibonacciSearch 斐波那契查找
     * @param: [arr, searchValue]
     * @return: int
     * @auther: zqq
     * @date: 20/6/18 10:18
     */
    public int fibonacciSearch(int[] arr, int searchValue){
        int left = 0;
        int right = arr.length - 1;
        int[] fib = fib(arr.length);
        int mid = 0;// 存储
        int k = 0;
        while (arr.length > fib[k] - 1){ // 找到一个k使得这个斐波那契数刚好大于等于right
            k++;
        }
        if (arr.length < fib[k]){
            arr = Arrays.copyOf(arr, fib[k]);// 因为right可能小于找到的斐波那契数，所以需要对数组扩容进行向后填充
            for (int i = right+1; i < arr.length; i++) {
                arr[i] = arr[right];
            }
        }
        while (left <= right){
            mid = left + fib[k - 1] - 1; // 分割点
            if (searchValue < arr[mid]){ // 在黄金分割点左边
                right = mid - 1;
                k--;// 向fib[k-1]的范围查找
            }else if (searchValue > arr[mid]){
                left = mid + 1;
                k -= 2;//向fib[k-2]的范围查找
            }else {
                if (mid <= right){
                    return mid;
                }else {
                    return right;
                }
            }
        }
        return -1;// 没有找到
    }

    /**
     * @Description: fib 构造斐波那契数列
     * @param: [right, left]
     * @return: int[]
     * @auther: zqq
     * @date: 20/6/18 9:50
     */
    public int[] fib( int right){
        int[] fibonacii;
        // 当数组长度小于等于5时，数组的长度大于等于数组长度对应的斐波那契数，
        // 这时后面进行查找一个k使得fib[k]-1刚好大于等于数组长度就会越界，故写死给一个6。产生的最大斐波那契数是8，大于数组长度，就不会越界
        if (right <= 5){
            fibonacii = new int[6];
        }else {//当数组长度大于5时，数组的长度小于数组长度对应的斐波那契数，不会产生越界
            fibonacii = new int[right];
        }

        fibonacii[0] = 1;
        fibonacii[1] = 1;
        for (int i = 2; i < fibonacii.length; i++) {
            fibonacii[i] = fibonacii[i -1] + fibonacii[i - 2];
        }
        return fibonacii;
    }
}

排序

冒泡排序

冒泡排序是一种简单的交换排序算法，以升序排序为例，其核心思想是：

从第一个元素开始，比较相邻的两个元素。如果第一个比第二个大，则进行交换。
轮到下一组相邻元素，执行同样的比较操作，再找下一组，直到没有相邻元素可比较为止，此时最后的元素应是最大的数。
除了每次排序得到的最后一个元素，对剩余元素重复以上步骤，直到没有任何一对元素需要比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void bubbleSortOpt(int[] arr) {

    if(arr == null) {
        throw new NullPoniterException();
    }
    if(arr.length < 2) {
        return;
    }
    int temp = 0;
    for(int i = 0; i < arr.length - 1; i++) {
        for(int j = 0; j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

快速排序

快速排序的思想很简单，就是先把待排序的数组拆成左右两个区间，左边都比中间的基准数小，右边都比基准数大。接着左右两边各自再做同样的操作，完成后再拆分再继续，一直到各区间只有一个数为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void quickSort(int[] arr, int start, int end) {
    if(start < end) {
        // 把数组中的首位数字作为基准数
        int stard = arr[start];
        // 记录需要排序的下标
        int low = start;
        int high = end;
        // 循环找到比基准数大的数和比基准数小的数
        while(low < high) {
            // 右边的数字比基准数大
            while(low < high && arr[high] >= stard) {
                high--;
            }
            // 使用右边的数替换左边的数
            arr[low] = arr[high];
            // 左边的数字比基准数小
            while(low < high && arr[low] <= stard) {
                low++;
            }
            // 使用左边的数替换右边的数
            arr[high] = arr[low];
        }
        // 把标准值赋给下标重合的位置
        arr[low] = stard;
        // 处理所有小的数字
        quickSort(arr, start, low);
        // 处理所有大的数字
        quickSort(arr, low + 1, end);
    }
}

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void insertSort(int[] arr) {
    // 遍历所有数字
    for(int i = 1; i < arr.length - 1; i++) {
        // 当前数字比前一个数字小
        if(arr[i] < arr[i - 1]) {
            int j;
            // 把当前遍历的数字保存起来
            int temp = arr[i];
            for(j = i - 1; j >= 0 && arr[j] > temp; j--) {
                // 前一个数字赋给后一个数字
                arr[j + 1] = arr[j];
            }
            // 把临时变量赋给不满足条件的后一个元素
            arr[j + 1] = temp;
        }
    }
}

希尔排序

希尔排序把序列按下标的一定增量（步长）分组，对每组分别使用插入排序。随着增量（步长）减少，一直到一，算法结束，整个序列变为有序。因此希尔排序又称缩小增量排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void shellSort(int[] arr) {
    // gap 为步长，每次减为原来的一半。
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 对每一组都执行直接插入排序
        for (int i = 0 ;i < gap; i++) {
            // 对本组数据执行直接插入排序
            for (int j = i + gap; j < arr.length; j += gap) {
                // 如果 a[j] < a[j-gap]，则寻找 a[j] 位置，并将后面数据的位置都后移
                if (arr[j] < arr[j - gap]) {
                    int k;
                    int temp = arr[j];
                    for (k = j - gap; k >= 0 && arr[k] > temp; k -= gap) {
                        arr[k + gap] = arr[k];
                    }
                    arr[k + gap] = temp;
                }
            }
        }
    }
}

简单选择排序

选择排序思想的暴力实现，每一趟从未排序的区间找到一个最小元素，并放到第一位，直到全部区间有序为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void selectSort(int[] arr) {
    // 遍历所有的数
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        // 把当前遍历的数和后面所有的数进行比较，并记录下最小的数的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                // 记录最小的数的下标
                minIndex = j;
            }
        }
        // 如果最小的数和当前遍历的下标不一致，则交换
        if (i != minIndex) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 转化为大顶堆
 * @param arr 待转化的数组
 * @param size 待调整的区间长度
 * @param index 结点下标
 */
public void maxHeap(int[] arr, int size, int index) {
    // 左子结点
    int leftNode = 2 * index + 1;
    // 右子结点
    int rightNode = 2 * index + 2;
    int max = index;
    // 和两个子结点分别对比，找出最大的结点
    if (leftNode < size && arr[leftNode] > arr[max]) {
        max = leftNode;
    }
    if (rightNode < size && arr[rightNode] > arr[max]) {
        max = rightNode;
    }
    // 交换位置
    if (max != index) {
        int temp = arr[index];
        arr[index] = arr[max];
        arr[max] = temp;
        // 因为交换位置后有可能使子树不满足大顶堆条件，所以要对子树进行调整
        maxHeap(arr, size, max);
    }
}

/**
 * 堆排序
 * @param arr 待排序的整型数组
 */
public static void heapSort(int[] arr) {
    // 开始位置是最后一个非叶子结点，即最后一个结点的父结点
    int start = (arr.length - 1) / 2;
    // 调整为大顶堆
    for (int i = start; i >= 0; i--) {
        SortTools.maxHeap(arr, arr.length, i);
    }
    // 先把数组中第 0 个位置的数和堆中最后一个数交换位置，再把前面的处理为大顶堆
    for (int i = arr.length - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        maxHeap(arr, i, 0);
    }
}

归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法。

  1. 将 n 个元素分成两个各含 n/2 个元素的子序列
  2. 借助递归，两个子序列分别继续进行第一步操作，直到不可再分为止
  3. 此时每一层递归都有两个子序列，再将其合并，作为一个有序的子序列返回上一层，再继续合并，全部完成之后得到的就是一个有序的序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 合并数组
 */
public static void merge(int[] arr, int low, int middle, int high) {
    // 用于存储归并后的临时数组
    int[] temp = new int[high - low + 1];
    // 记录第一个数组中需要遍历的下标
    int i = low;
    // 记录第二个数组中需要遍历的下标
    int j = middle + 1;
    // 记录在临时数组中存放的下标
    int index = 0;
    // 遍历两个数组，取出小的数字，放入临时数组中
    while (i <= middle && j <= high) {
        // 第一个数组的数据更小
        if (arr[i] <= arr[j]) {
            // 把更小的数据放入临时数组中
            temp[index] = arr[i];
            // 下标向后移动一位
            i++;
        } else {
            temp[index] = arr[j];
            j++;
        }
        index++;
    }
    // 处理剩余未比较的数据
    while (i <= middle) {
        temp[index] = arr[i];
        i++;
        index++;
    }
    while (j <= high) {
        temp[index] = arr[j];
        j++;
        index++;
    }
    // 把临时数组中的数据重新放入原数组
    for (int k = 0; k < temp.length; k++) {
        arr[k + low] = temp[k];
    }
}

/**
 * 归并排序
 */
public static void mergeSort(int[] arr, int low, int high) {
    int middle = (high + low) / 2;
    if (low < high) {
        // 处理左边数组
        mergeSort(arr, low, middle);
        // 处理右边数组
        mergeSort(arr, middle + 1, high);
        // 归并
        merge(arr, low, middle, high);
    }
}

基数排序

基数排序的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。为此需要将所有待比较的数值统一为同样的数位长度，数位不足的数在高位补零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 基数排序
 */
public static void radixSort(int[] arr) {
    // 存放数组中的最大数字
    int max = Integer.MIN_VALUE;
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    // 计算最大数字是几位数
    int maxLength = (max + "").length();
    // 用于临时存储数据
    int[][] temp = new int[10][arr.length];
    // 用于记录在 temp 中相应的下标存放数字的数量
    int[] counts = new int[10];
    // 根据最大长度的数决定比较次数
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        // 每一个数字分别计算余数
        for (int j = 0; j < arr.length; j++) {
            // 计算余数
            int remainder = arr[j] / n % 10;
            // 把当前遍历的数据放到指定的数组中
            temp[remainder][counts[remainder]] = arr[j];
            // 记录数量
            counts[remainder]++;
        }
        // 记录取的元素需要放的位置
        int index = 0;
        // 把数字取出来
        for (int k = 0; k < counts.length; k++) {
            // 记录数量的数组中当前余数记录的数量不为 0
            if (counts[k] != 0) {
                // 循环取出元素
                for (int l = 0; l < counts[k]; l++) {
                    arr[index] = temp[k][l];
                    // 记录下一个位置
                    index++;
                }
                // 把数量置空
                counts[k] = 0;
            }
        }
    }
}