JAVA数据结构和算法（第三章）学习笔记

-------------------------------
一、冒泡排序

1、前提：
2、关键算法：

　int out, in;
      for(out=nElems-1; out>1; out--){   // outer loop (backward)
         for(in=0; in<out; in++)        // inner loop (forward)
            if( a[in] > a[in+1] )       // out of order?
               swap(in, in+1);          // swap them
   }
  
3、优缺点：优点是简单，缺点是慢
　　４、效率： Ｏ(N*N）
  
--------------------------------------
二、选择排序

1、前提：
2、关键算法：
　
　　 int out, in, min;
　　for(out=0; out<nElems-1; out++)   // outer loop
     {
   min = out;                     // minimum
    for(in=out+1; in<nElems; in++) // inner loop
        if(a[in] < a[min] ) {        // if min greater,
            min = in;                  // we have a new min
        }                         
         swap(out, min);                // swap them
     }  // end for(out)
　
  
3、优缺点：优化了冒泡的交换操作
　　４、效率： 比较操作Ｏ(N*N），交换操作约Ｎ
--------------------------------------  
三、插入排序

1、前提：在数据局部是有序的情况下，使用效果好
2、关键算法：
　
　　 　int in, out;
      for(out=1; out<nElems; out++)     // out is dividing line
       {
         long temp = a[out];            // remove marked item　　　取出临时变量
         in = out;                      // start shifts at out
         while(in>0 && a[in-1] >= temp) // until one is smaller,　与Ｎ－１变量比较，如果Ｎ－１大于ＴＥＭＰ，则Ｎ－１向后移动一步　
          {
            a[in] = a[in-1];            // shift item to right
            --in;                       // go left one position　　改变指针，继续向前比较
          }
         a[in] = temp;                  // insert marked item　　　临时变量新的位置
       }  // end for
　
  
3、优缺点：相对于冒泡优化了比较与交换
　　４、效率： 最差Ｏ(N*N），最好Ｏ(N)
--------------------------------------