面试常见排序算法和查找算法

1. 时间复杂度的定义

算法的时间复杂度可以用一个函数来定性的表示程序运行时间。时间运行短的效率高，时间运行长的效率低。

x=T(n)=O(f(n))

• n表示输入规模。

  假设现在有一个累加求和的算法，目前有两个输入规模：1100和11000。毫无疑问，后者的输入规模比前者要大。

• x表示代码执行次数。

  核心代码执行次数，执行次数越多，表示需要花费的时间越长。

总体来说，我们所追求的理想目标是随着输入规模（n）的增大，核心代码执行次数(x)不会上升得太快，最好是不要上升。

2. 常见的时间复杂度

按照时间复杂度由小到大排序，常见的时间复杂度如下：

• 常数阶O(1)

  //无论i增加到多大，得到结果都只需要执行一行代码
  int n = n + 1

• 对数阶O(logN)

• 线性阶O(n)

  //需要n次循环执行代码才能得到结果
  for(i=1; i<=n; ++i)
  {
     j = i;
     j++;
  }

• 线性对数阶O(nlogN)

• 平方阶O(n²)

  //需要n²次循环执行代码才能得到结果
  for(x=1; i<=n; x++)
  {
     for(i=1; i<=n; i++)
      {
         j = i;
         j++;
      }
  }

• 立方阶O(n³)

• K次方阶O(n^k)

• 指数阶(2^n)

  

3.如何计算时间复杂度？

3.1 推导大O阶的方法

1. 用常数1取代运行时间中的所有加法常数。

2. 在修改后的运行函数中，只保留最高阶项。

3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

   

3.2 时间复杂度log(n)是怎么算的？

let count = 1;
while (count < n) {
    count = count * 2;
}

考虑上面这个程序，由于每次count乘以2之后，就距离n更近了一分。也就是说，有x个2相乘后大于n， 则会退出循环。 所以我们可以得到2^x =n。最终我们需要得到x也就是f(n)，因此式子必须要进行转换。根据对数运算，得到x=log 2n。再把底数给省略（影响较小，不重要），这个循环的时间复杂度为O(logn)。

另外一个由二分查找算法推算出log(n)的例子可以看这里。

3.3 什么是算法的排序稳定性

通俗地讲就是，两个数相等，排序前和排序后位置不变就是稳定的。如果要下一个定义的话，可以这么说：一列数中，如果Ai = Aj，Ai位于Aj的前置位，那么经过升降序排序后Ai仍然位于Aj的前置位。

稳定性对于原始数据排序本来就无意义的数据来说，稳定性不重要。但是原始数据排序有意义的情况下，可能就重要了。比如商品先按照价格排序，再按照销量排序。则第二次排序中，如果排序算法是稳定的，那么可以保证销量相同的情况下，按照价格排序。

4. 常见排序和查找算法的时间复杂度

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定
直接选择排序	O(n²)	O(n²)	O(n)	O(1)	不稳定
直接插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(nlogn)	O(nlogn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
希尔排序	O(nlogn)	O(ns)	O(n)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
基数排序	O(N*M)	O(N*M)	O(N*M)	O(M)	稳定

• 冒泡排序
  比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素（除开已经排过放到队列尾部的元素）重复以上的步骤。
• 选择排序
  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
• 插入排序
  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

public int[] sort(int[] a) {
    //初始化化第一个元素认为是有序的,所以i是1
    for (int i = 1; i < a.length; i++) {
        //拿未排序部分的第一个元素作为比较元素和已排序的部分比较
        for (int j = i; j > 0; j--) {
            //如果比较元素小于已排序部分的元素，就交换
            if (a[j] < a[j-1]) {
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
    return a;
}

• 快速排序

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

     

/**
 * 参考资料：https://segmentfault.com/a/1190000040022056
 * @author JerryYin
 * @since 2022-03-02 10:49
 */
public class QuickSort {

    /**
     * 首先选取数组中最大位置作为基准元素。
     * 根据基准元素，对数组进行排序。让数组中比基准元素小的元素在基准元素的左边（不要要求顺序），比基准元素大的元素则在右边（不要要求顺序）。
     * 3个指针
     * 1、基准指针：最后一个元素为基准元素
     * 2、第二指针：保存距离交换位置最近的，比基准元素大的元素的位置
     * 3、比较指针：用于在数组（有效范围）内遍历，比较与基准元素的大小。它的index一定大于或等于第二指针的index
     * @param array 待排序的数组。
     * @param lowIndex 本次操作数组的范围，最小索引。
     * @param highIndex 本次操作数组的范围，最大索引。
     * @return 返回最终基准元素的位置
     */
    public static int partition(int[] array, int lowIndex, int highIndex) {
        //选取队列中最后的元素作为基准元素
        int basePointerValue = array[highIndex];
        //保存距离交换位置最近的，比基准元素大的元素的位置,初始默认最低位
        int secondPointerIndex = lowIndex;
        for (int i = lowIndex; i < highIndex; i++) {
            //指针固定在基准元素上，将基准元素与从第一个索引开始的元素进行比较。
            if (array[i] < basePointerValue) {
                //如果该元素小于基准元素，则将较小的元素和上次找到的较大元素交换位置
                swap(array,secondPointerIndex,i);
                //只有交换，才会自增第二指针的位置
                secondPointerIndex++;
            }
            else{
                //如果该元素大于基准元素，不做任何处理。
            }
        }
        //最后将基准元素与第二个指针指向的元素交换位置。
        swap(array,highIndex,secondPointerIndex);

        System.out.println("中心点："+secondPointerIndex+" 中心值："+array[secondPointerIndex]+" "+Arrays.toString(array));

        return secondPointerIndex;
    }

    /**
     * 在数组中交换两个索引中的值
     * @param array
     * @param indexA
     * @param indexB
     */
    public static void swap(int[] array, int indexA, int indexB){
        int temp = array[indexA];
        array[indexA] = array[indexB];
        array[indexB] = temp;
    }

    /**
     * 不断递归
     * @param array 待排序的数组。
     * @param lowIndex 本次操作数组的范围，最小索引。
     * @param highIndex 本次操作数组的范围，最大索引。
     * @return 返回最终基准元素的位置
     */
    public static void quickSort(int[] array, int lowIndex, int highIndex){
        //如果最高和最低指针相等，就不用再排了。
        if(lowIndex < highIndex){
            //获取基准元素的位置
            int centerIndex = partition(array,lowIndex,highIndex);
            //对基准位置的左边（比基准小）进行排序
            quickSort(array,lowIndex,centerIndex-1);
            //对基准位置的右边（比基准大）进行排序
            quickSort(array,centerIndex+1,highIndex);
        }
    }
    
    public static void main(String[] args) {
        int[] a = new int[]{2,0,3,3,5,3,6,8,2,4,5,8,4,2,2,5,7,0};
        QuickSort.quickSort(a,0,a.length-1);
        System.out.println("result:"+Arrays.toString(a));
    }
}

• 归并排序

/**
 * 归并排序
 * 参考资料：https://www.cnblogs.com/chengxiao/p/6194356.html   https://www.bilibili.com/video/BV1XL411g7qF?p=31
 * @author JerryYin
 * @since 2022-03-21 11:19
 */
public class MergeSort {
    /**
     * 假设有一个数组，分为两段，分别有序，现在要求将两个有序的部分，合并成一个大的有序数组。
     * [1,3,4,6,2,5,6,7]，索引为3的地方分隔两个有序的部分。
     * 解题思路，创建两个指针，分别指向两个有序部分的开头。
     * 然后指针相互比较大小，把较小的值放到新数组中，并且这部分指针要自增。
     *
     * @param list
     * @param low
     * @param mid
     * @param high
     * @param tempList 临时数组，用来存放本轮处理的临时结果
     * @return
     */
    public int[] merge(int[] list, int low, int mid, int high,  int[] tempList) {
        int tempListIndex = 0;
        int firstIndex = low;
        int secondIndex = mid + 1;

        //一旦某个部分的指针遍历到头了，就不再遍历。
        while (firstIndex <= mid && secondIndex <= high) {
            //把结果较小的存放到临时数组。
            if (list[firstIndex] < list[secondIndex]) {
                tempList[tempListIndex++] = list[firstIndex++];
            } else {
                tempList[tempListIndex++] = list[secondIndex++];
            }
        }
        //假设左边部分还未遍历完成，就把剩余的数据写入临时数组。
        while (firstIndex <= mid) {
            tempList[tempListIndex++] = list[firstIndex++];
        }
        //假设右边部分还未遍历完成，就把剩余的数据写入临时数组。
        while (secondIndex <= high) {
            tempList[tempListIndex++] = list[secondIndex++];
        }
        //将本次处理好的合并结果写回到原数组，让新一轮的合并基于本次结果进行。
        tempListIndex = 0;
        while (low <= high) {
            list[low++] = tempList[tempListIndex++];
        }
        return tempList;
    }

    public void sort(int[] list, int low, int high, int[] tempList) {
        //当范围大于1个元素，就需要继续分割
        if (low < high) {
            //**最终（递归最底层）**,这里只有两个元素了，就可以二分一，左边1个元素，右边1个元素。分到最细，不可再分。
            int mid = (low + high) / 2;
            //分割左边部分
            sort(list, low, mid, tempList);
            //分隔右边部分
            sort(list, mid + 1, high, tempList);
            //将左右部分进行合并排序
            merge(list, low, mid, high, tempList);
        }
    }


}

查找算法	平均时间复杂度	查找条件
顺序查找	O(n)	无序或有序队列
二分查找（折半查找）	O(logn)	有序数组
二叉排序树查找	O(logn)	二叉排序树
哈希表法（散列表）	O(1)	先创建哈希表（散列表）
分块查找	O(logn)	无序或有序队列

public static int search(int[] array, int lowIndex, int highIndex, int searchValue) {
    //确定中间点
    int middleIndex = (lowIndex + highIndex) / 2;

    if(lowIndex > highIndex){
        //比较结束
        return  -1;
    }

    if (array[middleIndex] > searchValue) {
        //如果中间值比要查找值大，那么就认为待查找的值在左边
        highIndex = middleIndex - 1;
        return search(array, lowIndex, highIndex, searchValue);
    } else if (array[middleIndex] < searchValue) {
        //如果中间值比要查找值小，那么就认为待查找的值在右边
        lowIndex = middleIndex + 1;
        return search(array, lowIndex, highIndex, searchValue);
    }else {
        //相等，直接返回
        return middleIndex;
    }
}

5、空间复杂度

空间复杂度就是用来衡量空间使用量的。空间复杂度比较常用的有：O(1)、O(n)、O(n²)。