java中的几种排序方法

admin

  数组, 有些面试题中会出现.在实际工程项目中有现成的优化的排序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) 递归时候要按照递归深度分配全部临时变量, 栈开销很大, 性能
   不好, 要注意不要超过栈的大小, 并且一定要给出结束条件, 否则
   会造成栈溢出错误.

发光的影子

看了看  学习学习  哈哈哈哈

java宫城大师

学习一下。谢谢

woniu

这个项目太棒勒！下下来学习下！

lymlj1314

真心不错，推荐自己的好友去学习。

myou525

过来学习了，果然是好的学习资料，不错

wudizxt

不错不错不错不错

xjm

不错，学习学习

劉様

学习学习，谢谢分享