2019年java中高级java面试题（八）数据结构与算法

秒速五厘米 2022-01-20 00:19 212阅读 0赞

### 1、快速排序 ###

快速排序是一种分治的排序算法。将一个数组分成两个子数组，将两部分独立的进行排序。快速排序时，当两个子数组都有序时，整个数组自然有序了。其伪代码如下所示

public static void quickSort(int[] arr, int left, int right) {
        //左边索引不能大于右边索引
        if (left > right) {
            return;
        }
        //切分元素，找到新的基准
        int i = partition(arr, left, right);
        //基准数左边比基准数小，右边比基准数大
        //排左边
        quickSort(arr, left, i - 1);
        //排右边
        quickSort(arr, i + 1, right);
    }

快速排序关键在于切分，整个过程满足三个条件

1.  对于某个基准i  arr\[i\]已排定。
2.  arr\[left\]到arr\[i-1\]都小于或等于arr\[i\] 
3.  arr\[i+1\]到arr\[right\]都大于或等于arr\[i\]

切分语言描述如下：

> 会把数组中的一个数当做基准数，一般把数组中最左边得数当做基准数。然后从两边开始检索。先从右边检索比基准数小的，再从左边检索比基准数大的。如果检索到了，就停下，然后交换这两个元素。然后再继续检索。
> 
> 一旦相遇停止检索，交换基准数和相遇位置的元素。

代码如下：

public static int partition(int[] arr, int low, int high) {
        //定义左右扫描指针
        int left = low;
        int right = high;
        //基准
        int base = arr[low];
        while (left != right) {
    
            //找右边比基准小
            while (base <= arr[right] && left < right) {
                right--;
            }
            //找左边比基准大
            while (arr[left] <= base && left < right) {
    
                left++;
            }
            //交换left和right
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
    
        }
        //将bse放到 right位置上
        arr[low] = arr[right];
        arr[right]=base;
    
    
        return right;
    }

public static void main(String[] args) {
        int[] arr = {6, 3, 8, 10, 9, 85, 2, 1, 120, 654654};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    
    }
    
    public static void quickSort(int[] arr, int left, int right) {
        //左边索引不能大于右边索引
        if (left > right) {
            return;
        }
        //切分元素，找到新的基准
        int i = partition(arr, left, right);
        //基准数左边比基准数小，右边比基准数大
        //排左边
        quickSort(arr, left, i - 1);
        //排右边
        quickSort(arr, i + 1, right);
    }
    
    public static int partition(int[] arr, int low, int high) {
        //定义左右扫描指针
        int left = low;
        int right = high;
        //基准
        int base = arr[low];
        while (left != right) {
    
            //找右边比基准小
            while (base <= arr[right] && left < right) {
                right--;
            }
            //找左边比基准大
            while (arr[left] <= base && left < right) {
    
                left++;
            }
            //交换left和right
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
    
        }
        //将bse放到 right位置上
        arr[low] = arr[right];
        arr[right] = base;
    
    
        return right;
    }

### 2、LRU算法 ###

有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。下面说一下LRU算法的核心思想，LRU算法的设计原则是：**如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小**。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。