常见排序算法, 学习for循环if语句, 数组操作

         选择排序

         冒泡排序

         插入排序

Java API 提供的排序算法使用

简单递归调用

1. 3.

练习使用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}  

  i= 0 ~ < ary.length - 1;

    j=i+1 ~

           if(ary[i]>ary[j]){

                int t=ary[i];       ary[i]=ary[j];     ary[j]=t;

           }

 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}

  i = 0~ < ary.length-1

    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} 5

 

 i= 1 ~

          t = [i];

                    j= i-1 ~ >=0 && [j]>t, j--

                      [j]->[j+1] //移动

          t->[j+1]//插入

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

3. 方法的递归调用

1) java 的栈: 是Java进程启动时候在内存中开辟的存储空间栈内存的利用方式LIFO(后进先出). Java所有局部变量都在栈中分配(压入), 方法的参数也是局部变量, 局部变量在离开作用域时候回收 就是从栈中弹出(删除).

 2) Java方法调用使用栈实现, 递归调用就是栈实现的

 3) 递归时候要按照递归深度分配全部临时变量, 栈开销很大, 性能不好, 要注意不要超过栈的大小, 并且一定要给出结束条件, 否则会造成栈溢出错误.

  案例：1+2+3+...+n=f(n)=n+f(n-1) && (n>0, f(1)=1) 

 注意事项: 解决问题简练，性能很差。一定给出结束条件。