面试常用算法整理

绝地灬酷狼 2021-12-21 23:51 287阅读 0赞

知识点：基本算法 algorithms

**1.线性查找**

**2.二分查找**

描述：在数组中查找指定数值

首先要求该组元素必须是有序的，假设默认是从小到大排列，使用该组元素的中间元素与目标元素进行比较，如果相等则查找成功，如果中间元素比目标元素小，则去中间元素的右侧查找（递归），如果中间元素比目标元素大，则去中间元素的左侧查找（递归），直到找到目标元素 或者比较完毕，表示查找失败。

int a=\{3,6,7,9,16,28,32\}

伪代码：

// 注意: 使用二分查找算法的前提是数组元素必须有序

public static void main(String\[\] args) \{

int a=\{3,6,7,9,16,28,32\}

int n=a.length;  
SearchBinary(a,16,0,n);  
\}

public static int SearchBinary(int a\[ \],int value,int left,int right)\{

if(left<=right)\{

int mid=(left+right)/2;

tempValue=a\[mid\];

// 和中间元素比较，如果相等，查找成功

if(tempValue==value)\{

return mid;

// 如果小于中间元素，去左边找

else if(tempValue>value)\{

return SearchBinary(a,value,left,mid-1);

// 如果大于中间元素，去右边找

else if(tempValue<value)\{

return SearchBinary(a,value,mid+1,right);

//比较完毕

return -1;

**3.冒泡排序**

int \[\] a = \{10,4,7,3,9\}; n=a.length;

<!--

数据举例demo

第一趟:： 4 7 3 9 10 交换 4次(5-1)

第二趟 ：4 3 7 9 10 交换 3 次(5-2)

。。。

第i趟： 交换 n-i 次 (n-i)

\-->

伪代码：

//n-1趟

for（int i=1;i<=n-1;i++）\{

//n-i次（i趟对应的次数）

for(int j=0;j<n-i;j++)\{

if(a\[j\]>a\[j+1\])\{

//两瓶水交换，借助第三个瓶子为媒介

int tempcontainer=a\[j\];

a\[j\]=a\[j+1\];

a\[j+1\]=tempcontainer;

**4.插入排序  (**把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有n-1个元素；排序过程即每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。)

int \[\] a=\{3,1,5,23,2,4\};n=a.length;

<!--

数据举例demo

第一趟： 1,3,5,23,2,4

第二趟： 1,3,5,23,2,4

。。。

第 i 趟 ：

\-->

伪代码：（详细思路代码，可参考https://www.cnblogs.com/snowcan/p/6244128.html）

//n-1趟循环

for (int i=1;i<n;i++)\{

//tempcontainer存放本轮插入有序列表中的数

int tempcontainer=a\[i\];

//判断tempcontainer要插入的位置

for（int j=i-1;j>=0&&a\[j\]>tempcontainer;j--）\{

//将第j上的元素，朝后移动

a\[j+1\]=a\[j\];

//将tempcontainer,插入到空出来的位置上

a\[j+1\]=tempcontainer; //到这里，之前for循环，j位置的元素已经移到j+1的位置上了，j--位置的元素如果不满足条件，跳出循环，此时要想在j的空位置上赋值，

//必须a\[j+1\],因为在跳出循环之前j--了

**5.简单选择排序（基本思想：**给定数组 int\[\] arr=\{ 里面n个数据\}；第1趟排序，在待排序数据arr\[0\]~arr\[n-1\]中选出最小的数据，将它与arrr\[0\]交换；第2趟，在待排序数据arr\[1\]~arr\[n-1\]中选出最小的数据，将它与r\[1\]交换；以此类推，第i趟在待排序数据arr\[i-1\]~arr\[n-1中选出最小的数据，将它与r\[i-1\]交换，直到全部排序完成。**）**

int \[\] a=\{3,1,5,23,2,4\};n=a.length;

<!--

数据举例demo

第一趟： 1,3,5,23,2,4

第二趟： 1,2,5,23,3,4

。。。

第 i 趟 ：

\-->

伪代码：（详细思路代码，可参考https://www.cnblogs.com/shen-hua/p/5424059.html）

//n-1趟循环

for(int i=0;i<n-1;i++)\{

int min=i; //第i趟最小值，下标用min来记录

for(int j=min+1;j<n;j++)\{  //选择最小记录

if(a\[j\]<a\[min\])\{

min=j;//记下当前找到的最小值所在的位置

//内层循环结束后，已经找到了本轮循环的最小数，再进行交换

if（i !=min）\{ //如果i下标的位置，不是最小值的话(min=i的情况)，则交换a\[i\]和a\[min\]

int temp=a\[i\];

a\[i\]=a\[min\];

a\[min\]=temp;

**6.n层汉诺塔问题**

（知识点参考知乎：https://www.zhihu.com/question/24385418）

(伪代码参考https://www.cnblogs.com/gw811/archive/2012/10/10/2719181.html)

**描述：**

**![1132642-20190211145816712-1726654451.png][]**

**图片动画演示**：

![1132642-20190211153030031-2140611838.gif][]

三维动画演示可查看：https://hightopo.com/demo/hanoi\_20151106/index.html

伪代码：

public class Hanoi {
        
    
        public static void move(int n,String from,String temp,String to){
        
            if(n>0){
        
                move(n-1,from,to,temp);
                System.out.println("盘"+n+"由"+from+"移到"+to);
                move(n-1,temp,from,to);
            }
        }
    
        public static void main(String[] args) {
        
          move(3,"A","B","C");
        }
    
    }
    
    输出结果：

以上是伪代码，详细代码参考

博客：https://www.cnblogs.com/Ray1024/p/10337144.html

补充：关于其他经典排序算法（希尔排序、快速排序、归并排序、堆排序、基数排序等） 可以参考 https://www.cnblogs.com/fivestudy/p/10212306.html

转载于:https://www.cnblogs.com/shuaifing/p/10338927.html

[1132642-20190211145816712-1726654451.png]: /images/20211220/7aae437c1cae4663ad5039459c04106b.png
[1132642-20190211153030031-2140611838.gif]: /images/20211220/974cb0995a83429dab5957b04e890979.png