第2次实验——算法基本功与综合思考

灰太狼 2024-02-17 14:44 6阅读 0赞

（1）算法基本功——快速排序

对文件[ ][Link 1][largeW.txt][Link 1]（[下载链接][Link 1]）中的数据，应用快速排序算法进行排序，并与[冒泡排序、归并排序][Link 2]进行时间比较。体验算法复杂度对设计算法的影响。

下面是快速排序的代码和运行效果，[冒泡排序、归并排序][Link 2]的代码和结果请参照我的另一篇博文：[http://blog.csdn.net/wanghaiping1993/article/details/22232293][http_blog.csdn.net_wanghaiping1993_article_details_22232293]

package test;

import java.io.BufferedReader;
 import java.io.File;
 import java.io.FileOutputStream;
 import java.io.FileReader;
 import java.io.IOException;
 import java.util.ArrayList;//快速排序
 public class QuickSort {  
  
  public static void main(String[] args){  
         
   double start_all = System.currentTimeMillis();
   String path = "txt/largeW.txt";
   ArrayList<Integer> list=read(path); 
   double start = System.currentTimeMillis();
   QuickSort quickSort = new QuickSort();  
         quickSort.quickSort(list,0,list.size()-1); 
         
         double end = System.currentTimeMillis();
         System.out.println("快速排序时间为: " + (end - start)+"毫秒");
         
         // 写入txt文件
         double end_all = System.currentTimeMillis();
         write(list);
         System.out.println("写入完成");
   System.out.println("总运行时间为: " + (end_all - start_all)+"毫秒");
     }  
  
  //创建并写入largeW_quick.txt文件
  public static void write(ArrayList<Integer> list) {
   File f = new File("txt/largeW_quick.txt");
   FileOutputStream fou = null;
   try {
    fou = new FileOutputStream(f, false);// true,设置可追加   for (int i = 0; i < list.size(); i++) {
     String s = String.valueOf(list.get(i));
     String a = "" + s + "\t\n";
     // byte []bytes=new byte[1024];
     // 如何把string转换byte数组
     fou.write(a.getBytes());   }
   } catch (Exception e) {
    // TODO: handle exception
    e.printStackTrace();
   } finally {
    try {
     fou.close();
    } catch (Exception e) {
     // TODO Auto-generated catch block
     e.printStackTrace();
    }
   }
  }
   public void quickSort(ArrayList<Integer> list,int first, int end){  
          if(first<end){  
              int pivot = partition(list,first,end);  
              quickSort(list,first,pivot-1);  
              quickSort(list,pivot+1,end);  
          }  
      }      
     public  int partition(ArrayList<Integer> a, int first , int end){  
         int i = first; int j = end;  
         while(i<j){  
             while(i<j&&a.get(i)<=a.get(j))j--;  
             if(i<j){  
                 int temp;  
                 temp = a.get(i);  
                 a.set(i, a.get(j));  
                 a.set(j, temp);  
                 i++;  
             }  
             while(i<j&&a.get(i)<=a.get(j))i++;  
             if(i<j){  
                 int temp;  
                 temp = a.get(j);  
                 a.set(j, a.get(i));  
                 a.set(i, temp); 
                 j--;  
             }  
         }  
             return i ;  
     }  
      
   //读取文件到int数组
  public static ArrayList read(String path) {
   ArrayList<Integer> list = new ArrayList<Integer>();
   BufferedReader input = null;
   try {
    FileReader in = new FileReader(path);
    input = new BufferedReader(in);
    String ss;
    try {
     while ((ss = input.readLine()) != null) {
      String[] s = ss.split("\r\n");
      for (int i = 0; i < s.length; i++) {
       list.add(Integer.parseInt(s[i].trim())); // 将String s中的内容添加到动态数组中
      }
     }
    } catch (IOException e) {
     // TODO 自动生成的 catch 块
     e.printStackTrace();
    }
    in.close();
    input.close();
   } catch (Exception e) {
    // TODO 自动生成的 catch 块
    e.printStackTrace();
   }  return list;
  }
    
 }

结果：

![SouthEast][]

排序后的结果：

![Center][]

**（2）经典算法面试题**（至少选择其中**1道题**并作答，有自己的思考与理解）

1.  有A、B、C、D四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17分钟内这四个人都过桥？

解答： 方法是：思路就是一定要让1，2分钟的人来送电筒。

方案一：

过河去： 1，2分钟的人 总耗时2

回来送手电筒： 1分钟的人 总耗时3

过河去： 5，10分钟的人 总耗时13

回来送手电筒： 2分钟的人 总耗时15

过河去： 1，2分钟的人 总耗时17

方案二：

过河去： 1，2分钟的人 总耗时2

回来送手电筒： 2分钟的人 总耗时4

过河去： 5，10分钟的人 总耗时14

回来送手电筒： 1分钟的人 总耗时15

过河去： 1，2分钟的人 总耗时17

**（4）实习与工作**

上招聘网站（如 51job、智联招聘）上查看自己感兴趣的职位与要求。**作业要求**：写下自己感兴趣工作的至少2个岗位名称（如Java程序员、搜索引擎工程师）、工作岗位具体要求、自身目前具备哪些条件、有哪些不足的地方并如何弥补。

感兴趣的岗位1：JAVA软件工程师

具体要求：

公司一：

计算机相关专业本科以上学历  
熟练掌握Linux或Windows操作系统  
熟悉Internet/Intranet相关技术、数据库技术  
对JAVA/JSP的应用环境有较好的了解,有实践经验者优先  
具有HTML,Javascript的开发基础,熟悉网页制作  
具有较好的服务意识、沟通能力、责任心强、学习能力强

公司二：

1、本科或以上学历，计算机相关专业毕业，2年以上Java编程经验，有B/S软件开发经验；  
2、熟悉Struts、Spring、Hiberate 等主流开源框架；  
3、熟悉Dwr、ExtJS等JavaScript、Ajax框架；  
4、熟悉Weblogic、Tomcat等应用服务器的部署与配置；  
5、掌握Sqlserver、Mysql等关系类型数据库；  
6、熟练使用开发工具Eclipse，SVN等。  
7、优先考虑熟悉JBPM和EXTJS者。

公司三：

熟练掌握Linux或Windows操作系统  
熟悉Internet/Intranet相关技术、数据库技术  
对JAVA/JSP的应用环境有较好的了解,有实践经验者优先  
具有HTML,Javascript的开发基础,熟悉网页制作  
具有较好的服务意识、沟通能力、责任心强、学习能力强

感兴趣的岗位2：WEB前端开发工程师

具体要求：

公司一：

1、根据项目需求，高效和高质的完成代码编写；  
2、配合开发工程师，以确保代码有效对接；  
3、与设计师密切配合，实现符合用户体验的交互效果；  
任职要求：  
1、 精通W3C标准及规范，熟练掌握Html,Css,Javascript；  
2、 熟练掌握 jquery；  
3、 能够轻松解决各浏览器兼容问题；  
4、 了解使用过 angularjs 或 backbonejs 或 durandaljs 等MV\*框架 (一种或以上) ；  
5、 对Web技术专研有强烈兴趣，有较强的学习能力，良好的沟通能力和团队合作精神；

优先录取项：  
1、 了解或实践过响应式页面，具备一定的移动web开发经验；  
2、 熟悉使用bootstrap 或 foundation 等前端框架(一种或以上).  
3、 熟悉使用 Sass 或Less 等CSS预处理器(一种或以上)。

公司二：

1，两年以上网站及终端制作工作经验。

2，了解业界前端制作的新技术，新思路。

3，熟练掌握PHOTOSHOP，FLASH，Dreamweaver等相关软件，精通HTML+CSS,独立完成制作建站全过程。

4，熟练运用HTML5搭建页面，能流畅实现主流交互及特效以及各浏览器兼容。

6，善于沟通，工作主动，积极向上，良好的团队合作精神和高度的责任感，能承受压力，有创新精神，保证工作质量。

7，有过大型门户网站搭建，响应式布局，JS动态效果实现等经验优先。

8，应聘时请带个人作品。

公司三：

1.负责公司网站的编程、设计、改版、更新内容；

2.负责公司产品的界面进行设计、编辑、美化等工作；

3.配合推广优化做好网站建设；

职位要求：

1.熟悉企业网站程序，具有一年或以上网站开发经验；

2.精通ASP网站程序开发，掌握ACCESS与MSSQL开发使用；熟悉asp.net ；了解PHP+MYSQL；

3.熟练使用Web开发相关的HTML、CSS+DIV、JavaScript、AJAX、DHTML等技术；

4.熟练使用网页设计软件；

5.具有良好的且规范的编码风格，有较强的学习能力、对新技术的追求精神和能够独立完成工作，优秀的团队沟通协作能力和责任心。

目前我具备的条件

1,对学习了jsp,对spring,hibernate,struct有所了解但不精通。

2.会基本html,javascript,css+div,jquery技术

3.会简单使用photoshop,dreamweaver,eclipse等工具的使用。

不足：对这些专业知识学的不精通，了解皮毛，对于真正就业的要求还是有差距的。

补充自己的不足：趁现在还有半年在学校的机会，根据公司的要求一一的去强化自己的知识技能，尽可能的达到公司就业的要求。另外，利用尽力在暑假找一个实习的机会，然后更加近距离的接触社会，从而发现自己的不足来改进自己。

[Link 1]: http://pan.baidu.com/s/1ntoHMmH
[Link 2]: http://blog.csdn.net/dyz1982/article/details/21827047
[http_blog.csdn.net_wanghaiping1993_article_details_22232293]: http://blog.csdn.net/wanghaiping1993/article/details/22232293
[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/91085e8231a24ca9bbf8984f5887db9b.png
[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/03e8672f728349f4828e3eaea01fe452.png