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

1. 时间复杂度的定义

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

1
x=T(n)=O(f(n))
  • n表示输入规模。

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

  • x表示代码执行次数。

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

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

2. 常见的时间复杂度

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

  • 常数阶O(1)

    1
    2
    //无论i增加到多大,得到结果都只需要执行一行代码
    int n = n + 1
  • 对数阶O(logN)

  • 线性阶O(n)

    1
    2
    3
    4
    5
    6
    //需要n次循环执行代码才能得到结果
    for(i=1; i<=n; ++i)
    {
    j = i;
    j++;
    }
  • 线性对数阶O(nlogN)

  • 平方阶O(n²)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //需要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,则去除与这个项相乘的常数。

    常见大O阶推导

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

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

考虑上面这个程序,由于每次count乘以2之后,就距离n更近了一分。也就是说,有x2相乘后大于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) 稳定
  • 冒泡排序
    比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。针对所有的元素(除开已经排过放到队列尾部的元素)重复以上的步骤。
  • 选择排序
    首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。重复第二步,直到所有元素均排序完毕。
  • 插入排序
    将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)把小于基准值元素的子数列和大于基准值元素的子数列排序;

      快速排序

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
75
76
77
78
79
80
81
/**
* 参考资料: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));
}
}
  • 归并排序
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
/**
* 归并排序
* 参考资料: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) 无序或有序队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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²)。