java常见排序方法

时间:2022-06-29 00:49:57

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)  
 注意事项: 解决问题简练,性能很差。一定给出结束条件。

                                                                    若有不完善的地方请大家多提意见,转发时请注明出处!