java排序方法

1.java常用排序方法

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

　　部分重要代码：
 　　 i= 0 ~ < ary.length - 1;
 　　 j=i+1 ~ <ary.length
 　　 if(ary[i]>ary[j]){
    　　  //ary[i]<->ary[j]
    　　  int temp = ary[i];
      　　ary[i]=ary[j];
      　　ary[j]=temp;
  　　}
      
 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 ~ <ary.length, i++
     　t = [i];
        j= i-1 ~ >=0, j--
        if(t<[j]){
            [j]->[j+1] //移动
        }else{
             break j;
        }
     　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)  
 注意事项: 解决问题简练，性能很差。一定给出结束条件。