Java面试题冲刺第二十天–算法(1)

Java面试题冲刺第二十天--算法(1)攻略

前言

在面试Java开发岗位时，算法是面试官必问的一个方面。在Java面试题冲刺系列的第二十天，我们探讨的是算法相关的问题。本篇攻略主要讲解与算法相关的顶级问题、常用排序算法与查找算法。

算法相关顶级问题

1. 什么是排序算法？

判断一个排序算法的效率主要有两个指标：时间复杂度和空间复杂度。时间复杂度通常作为衡量排序算法优劣的主要标准，而空间复杂度也至关重要。

1. 常用排序算法分类？

常用排序算法包括插入排序、选择排序、冒泡排序、快速排序、归并排序、堆排序、计数排序、基数排序等。根据时间复杂度，排序算法可分为两类，一类是平均时间复杂度 O(nlogn) 的排序算法，如快速排序、堆排序等；另一类是平均时间复杂度 O(n^2) 的排序算法，如冒泡排序、插入排序等。

1. 什么是查找算法？

查找算法是一类在数据集合中寻找特定数据元素的算法，也称为搜索算法。常见的查找算法包括顺序查找、二分查找、哈希查找等。

1. 常用查找算法的时间复杂度？

常见查找算法的时间复杂度如下：

• 顺序查找：O(n)
• 二分查找：O(logn)
• 哈希查找：O(1)

常用排序算法

插入排序

插入排序的基本思想是，在无序数列中逐一将每一个数插入到有序数列中的正确位置，直到排序完成。插入排序的时间复杂度为 O(n^2)。

示例代码：

public static void insertionSort(int[] array) {
    int len = array.length;
    for (int i = 1; i < len; i++) {
        int temp = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > temp) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
}

快速排序

快速排序的基本思想是，选择一个基准数，然后将比基准数小的数放到基准数的左边，比基准数大的数放到基准数的右边。然后递归的对左右两部分进行快排。快速排序的时间复杂度为 O(nlogn)。

示例代码：

public static void quickSort(int[] array, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(array, left, right);
        quickSort(array, left, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, right);
    }
}

private static int partition(int[] array, int left, int right) {
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (array[i] < array[pivot]) {
            swap(array, i, index);
            index++;
        }
    }
    swap(array, pivot, index - 1);
    return index - 1;
}

private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

归并排序

归并排序的基本思想是，将待排序数列拆分为两部分，分别对两部分进行排序，然后将两部分有序的合并成一个有序的数列。归并排序的时间复杂度为 O(nlogn)。

示例代码：

public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

private static void merge(int[] array, int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    int[] temp = new int[right - left + 1];
    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = array[i++];
    }
    while (j <= right) {
        temp[k++] = array[j++];
    }
    for (int l = 0; l < k; l++) {
        array[left + l] = temp[l];
    }
}

常用查找算法

二分查找

二分查找的前提是有序数列，将待查找元素与有序数列的中间元素进行比较，根据比较结果折半范围，直到找到待查找元素。二分查找的时间复杂度为 O(logn)。

示例代码：

public static int binarySearch(int[] array, int target) {
    int left = 0, right = array.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

总结

在Java面试中，算法是一个非常重要的话题。本篇攻略详细讲解了算法相关的顶级问题、常用排序算法与查找算法，并带有示例代码说明。希望能帮助大家在面试中更好地掌握算法知识。