Java 语言基础 Day05

QQ账号登录	立即注册>>

汪星人

326 主题	72 听众	999 金钱

实习版主

该用户从未签到

电梯直达

楼主

发表于 2014-03-03 17:27:32 |只看该作者 |倒序浏览

练习使用for循环和
  数组, 有些面试题中会出现.在实际工程项目中有现成的优化的排序API
1) 选择排序
原理:a 将数组中的每个元素,与第一个元素比较
      如果这个元素小于第一个元素, 就将这个
      两个元素交换.
   b 每轮使用a的规则, 可以选择出一个最小元素
      放到第一个位置.
   c 经过n-1轮比较完成排序
简单说: 每轮选择最小的放到前面.
原理说明:
ary={8,2,3,7,1}
ary={1|8,3,7,2}
ary={1,2|8,7,3}
ary={1,2,3|8,7}
ary={1,2,3,7|8}
代码分析:
i 代表第一个数据的位置
j 代码后部每一个数据的位置
ary    i j ary[i] ary[j] ary[i]>ary[j] [i]<->[j]
{8|2,3,7,1} 0 1 8    2       true       8<->2
{2|8,3,7,1} 0 2 2    3       false
{2|8,3,7,1} 0 3 2    7       false
{2|8,3,7,1} 0 4 2    1       true       2<->1
{1,8|3,7,2} 1 2 8    3       true       8<->3
{1,3|8,7,2} 1 3 3    7       false
{1,3|8,7,2} 1 4 3    2       true       3<->2
{1,2,8|7,3} 2 3 8    7       true       8<->7
{1,2,7|8,3} 2 4 7    3       true       7<->3
{1,2,3,8|7} 3 4 8    7       true       8<->7
{1,2,3,7,8}
  for: i= 0 ~ < ary.length - 1;
for: j=i+1 ~ <ary.length
   if(ary[i]>ary[j]){
   ary[i]<->ary[j]
   }

2) 冒泡排序
  原理: a 逐一比较数组中相邻的两个元素, 如果后面
      的数字小于前面的数字, 就交换先后元素.
   b 经过一个轮次的比较, 一定有一个最大的排
      在最后的位置.
   c 每次比较剩下的元素, 经过n-1次比较, 可以
      实现排序
  简单说: 比较相邻元素,大的向后交换
原理说明:
ary={8,2,3,7,1}
ary={2,8,3,7,1}
ary={2,3,8,7,1}
ary={2,3,7,8,1}
ary={2,3,7,1|8}
ary={2,3,7,1|8}
ary={2,3,7,1|8}
ary={2,3,1|7,8}
ary={2,3,1|7,8}
ary={2,1|3,7,8}
ary={1,2,3,7,8}
i代表次数
j代表比较位置
ary    i j j+1 ary[j] ary[j+1] [j]>[j+1] [j]<->[j+1]
{8,2,3,7,1} 0 0  1 8    2    true    8<->2
{2,8,3,7,1} 0 1  2 8    3    true    8<->3
{2,3,8,7,1} 0 2  3 8    7    true    8<->7
{2,3,7,8,1} 0 3  4 8    1    true    8<->1
{2,3,7,1|8} 1 0  1 2    3    false
{2,3,7,1|8} 1 1  2 3    7    false
{2,3,7,1|8} 1 2  3 7    1    true    7<->1
{2,3,1|7,8} 2 0  1 2    3    false
{2,3,1|7,8} 2 1  2 3    1    true    3<->1
{2,1|3,7,8} 3 0  1 2    1    true    2<->1
{1,2,3,7,8}
  for: i = 0~ < ary.length-1
for: j = 0~ < ary.length - i -1;
   if([j]>[j+1]){
          [j]<->[j+1]
   }

3) 插入排序
  原理: a 将数组分为两部分, 将后部分的第一张逐一
      与前部分每一张比较, 如果当前元素小, 就
      一点被比较元素.
      b 找到合理位置插入.
  原理说明:
temp = 1
  {8|2,3,7,1}
  {2,8|8,7,1}
  {2,3,8|7,1}
  {2,3,8|8,1}
  {2,3,7,8|8}
  {2,3,7,7|8}
  {2,3,3,7|8}
  {2,2,3,7|8}
  {1,2,3,7|8}

temp 代表取出的待插入元素
i 代表后组待插入元素位置
j 代表前组每个元素的位置
                                 (移动)    插入
ary    i  t  j  ary[j]  t<[j] [j]->[j+1] t->[j+1]
{8|2,3,7,5} 1  2  0 8    true 8->[j+1]
{8|8,3,7,5} 1  2 -1                         2->[j+1]
{2,8|3,7,5} 2  3  1 8    true 8->[j+1]
{2,8|8,7,5} 2  3  0 2    false          3->[j+1]
{2,3,8|7,5} 3  7  2 8    true 8->[j+1]
{2,3,8|8,5} 3  7  1 3    false          7->[j+1]
{2,3,7,8|5} 4  5  3 8    true 8->[j+1]
{2,3,7,8|8} 4  5  2 7    true 7->[j+1]
{2,3,7,7|8} 4  5  1 3    false          5->[j+1]
{2,3,5,7|8}
i= 1 ~ <ary.length, i++
   t = [i];
   j= i-1 ~ >=0, j--
   if(t<[j]){
     [j]->[j+1] //移动 ary[j+1]=ary[j]
   }else{
      break j;
   }
   t->[j+1]//插入

2. java 系统排序 Arrays.sort(), 排序算法性能很好

3. 方法的递归调用
1) java 的栈: 是Java进程启动时候在内存中开辟的存储空间
栈内存的利用方式LIFO(后进先出).
A Java所有局部变量都在栈中分配(压入)方法的参数也是局部变量
B 局部变量在离开作用域时候回收就是从栈中弹出(删除).
2) Java方法调用使用栈实现, 递归调用就是栈实现的
3) 递归时候要按照递归深度分配全部临时变量, 栈开销很大, 性能
不好, 要注意不要超过栈的大小, 并且一定要给出结束条件, 否则
会造成栈溢出错误.

  案例：1+2+3+...+n=f(n)=n+f(n-1) && (n>0, f(1)=1)
注意事项: 解决问题简练，性能很差。一定给出结束条件。

作业：
  1 复习并且实现全部案例，找出全部的疑问，并解决。
  2 实现递归代码：
  //案例：n!=1*2*3*...*n=f(n)
  //    =n*f(n-1) && f(1)=1;

  //案例：1+3+5+...+n=f(n)
  //    =n+f(n-2) && f(1)=1;

  //案例：1/1+1/2+1/3+...+1/n=f(n)
  //    =1/n+f(n-1) && f(1)=1;

3 案例

实现随机生成双色球号码: [02 22 13 16 18 12] [12]
  红球 33 个球 (01~33) 取六
  蓝球 16 个球 (01~16) 取一

提示:
  蓝球池  {"01", "02", "03", "04", ... "16"}
  红球池  {"01", "02", "03", "04", ... "33"}
  使用标记{ f, f, f, f, ... f}

  结果采用一个数组存储, 数组可以利用数组扩容追加新的"球号"
  处理逻辑参考如下过程:

  1 随机生成红球序号
  2 检查"红球序号"是否使用过(取出过)
如果使用过返回 1
  3 取出一个红球, 设置使用标记为true
  4 是否取出了6个红球
如果没有到6个, 返回 1
  5 对红球结果排序
  6 取出一个篮球到结果中

4 案例: 生成4位网站验证码,
  1 不能重复
  2 数字和大小写字符, 但是不能包含1,0,o,O,l,L,Z,2,9,g等

案例4: (选做) 将一个整数数位翻转
   如: 整数 56123
   返回结果为整数:  32165
   提示: 使用 %10 获取最后一位
         使用 /10 去除处理完的最后一位

num sum  n=num%10 sum*10+n -> sum  num/10 -> num
  56123 0    3          3             5612
  5612 3    2          32          561
  561    32 1          321          56
  56    321 6          3216          5
  5    3216  5          32165       0
  0    32165

科帮网 1、本主题所有言论和图片纯属会员个人意见，与本社区立场无关
2、本站所有主题由该帖子作者发表，该帖子作者与科帮网享有帖子相关版权
3、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和科帮网的同意
4、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任
5、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
6、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除并致以最深的歉意
7、科帮网管理员和版主有权不事先通知发贴者而删除本文