几种常见的算法

一、冒泡排序法

冒泡排序法

  原始数据：3 2 7 6 8

  第1次循环：（最大的跑到最右边）

  2 3 7 6 8（3和2比较，2<3 所以2和3交换位置）

  2 3 7 6 8（3和7比较，3<7 所以不需要交换位置）

  2 3 6 7 8（6和7比较，6<7 所以6和7交换位置）

  2 3 6 7 8（7和8比较，7<8 所以不需要交换位置）

  经过第1次循环，此时剩下参与比较的数据：2 3 6 7

  第2次循环：

  2 3 6 7（2和3比较，2<3，所以不需要交换位置）

  2 3 6 7（3和6比较，3<6，所以不需要交换位置）

  2 3 6 7  (6和7比较，6<7，所以不需要交换位置）

  经过第2次循环，此时剩下参与比较的数据是：2 3 6

  第3次循环：

  2 3 6（2和3比较，2<3，所以不需要交换位置）

  2 3 6（3和6比较，3<6，所以不需要交换位置）

  经过第3次循环，此时剩下参与比较的数据是：2 3

  第4次循环

   2 3（2和3比较，2<3，所以不需要交换位置）

  

  public class BubbleSort{

     public static void main(String[] args){

       //这是int类型的数组对象

       int[] arr = {3,2,6,7,8};

       //经过冒泡排序算法对以上数组中元素进行排序

       //冒泡排序算法的核心是什么？

      

       //7条数据，循环6次。以下的代码可以循环6次（冒泡排序法采用外层循环）

       int count = 0;

       for(int i=arr.length-1;i>0;i–){

          //不管是否需要交换，总之是要比较一次的

          count++;

         //9 8 10  7 6 0 11

         for(int j=0;j<i；j++){

           if(arr[i]>arr[j+1]){

              //交换位置

             //arr[j]和arr[j+1]交换

            int temp;

            temp = arr[j];

            arr[j] = arr[j+1];

            arr[j+1] = temp;

           }

         }

        }

        System.out.println(“比较次数:”+count);

       //输出结果

       for(int i=0;i<arr.length;i++){

           System.out.println(arr[i]);

       }

      }

 }

二、选择排序法

 

选择排序法比冒泡排序法的效率高

 高在交换位置上

 选择排序的交换位置是有意义的

 每一次从这“堆”参与比较的数据当中“找出最小值”

拿这个最小值和“参与比较的这堆最前面的元素”交换位置

 循环一次，然后找出参加比较的这堆数据中最小的。拿这个最小的值和

最前面的数据交换位置。

参与比较的数据：3 1 6 2 5

第1次循环之后的结果是： 1 3 6 2 5

下次参与比较的数据：3 6 2 5

第2次循环之后的结果是：2 6 3 5

下次参与比较的数据是：6 3 5

第3次循环之后的结果是：3 6 5

 下次参与比较的数据是： 6 5

第4次循环之后的结果是： 5 6

注意：5条数据，循环4次

冒泡排序和选择排序实际上比较的次数没变

交换位置的次数减少了

3 2 6 1 5

  假设：

     第1个3是最小的

     3和2比较，发现2更小，所以此时最小的是2

     继续拿着2往下比对，2和6比较，2仍然是最小的

     继续拿着2往下比对，2和1比对，发现1更小，所以此时最小的是1

     继续拿着1往下比对，1和5比对，发现1还是小的，所以1就是最小的

     拿着1和最左边的3交换位置

 

  2 6 3 5

   假设：

      第1个2是最小的

      ……

  

  6 3 5

  假设6是最小的，6和3比对，发现3更小，所以此时最小的是3

  ……

 public class SelectSort{

    public static void main(String[] args){

         int[] arr = {3,1,6,2,5};

         int count = 0;

         //选择排序

      //5个数据循环4次（外层循环4次）

     for(int i=0;i<arr.length-1;i++){

       //i的值是0 1 2 3

      //i正好是“参加比较的这堆数据中”最左边那个元素的下标

     //i是一个参与比较的这堆数据中的起点下标

    //假设起点i下标位置上的元素是最小的

         int min = I;

         for(int j=i+1;j<arr.length;j++){

          count++;

           if(arr[j]<arr[min]){

              min = j;   //最小值的元素下标是j 

         }

   }

  //当i和min相等时，表示最初猜测是对的

 //当i和min不相等时，表示最初猜测是错的，有比这个元素更小的元素

//需要拿着这个更小的元素和最左边的元素交换位置

 if(min!=i){

   //表示存在更小的数据

  //arr[min]最小的数据

 //arr[i]最前面的数据

    int temp;

    temp = arr[min];

    arr[min = arr[i];

    arr[i] = temp;

    }

  }

  System.out.println(“比较次数”+count);

  //排序之后遍历

  for(int i=0;i<arr.length;i++){

      System.out.println(arr[i]);

   }

 }

}

三、二分法查找

 数组的元素查找

   数组元素查找两种方式：

      第一种方式：一个一个挨着找，直到找到为止

      第二种方式：二分法查找（算法），这个效率较高

 public class ArraySearch{

   public static void main(String[] args){

      //这个例子演示第一种方式

      int[] arr = {4,5,6,87,8};

     //需求：找出87的下标。一个一个挨着找

     for(int i=0;i<arr.length;i++){

       if(arr[i]==87){

          System.out.println(“87元素的下标是：”+i);

          return;

       }

     }

    //程序执行到此处，表示没有87

   System.out.println(“87不存在该元素！”);

  

  //最好以上的程序封装到一个方法，思考：传什么参数？返回什么值？

 //传什么：第一个参数是数组，第二个参数是被查找的元素

 //返回值：返回被查找的这个元素的下标，如果找不到返回-1

 int index = arraySearch(arr,87);

 System.out.println(index == -1?”该元素不存在1″:”该元素下标是：”+index):

  }

  //从数组中检索某个元素的下标（返回的是第一个元素的下标）

 //arr 被检索的数组

//ele 被检索的元素

//大于等于0的数表示元素的下标，-1表示该元素不存在

  public static void arraySearch(int[] arr,int ele){

      for(int i=0;i<arr.length;i++){

          if(ele == arr[i]){

              return I;

          }

       }

   return -1;

  }

}

关于查找算法中的：二分法查找

10（下标0）11 12 13 14 15 16 17 18 19 20（下标10） arr数组

通过二分法查找，找出18这个元素的下标：

 （0+10）/2–>中间元素的下标：5

拿着中间这个元素和目标要查找的元素进行对比：

  中间元素是：arr[5]–>15

  15<18(被查找的元素）

  被查找的元素18在目前中间元素15的右边

再重新计算一个中间元素的下标：

  开始下标是：5+1

  结束下标是：10

  （6+10）/2–>8

 8下标对应的元素arr[8]是18

   找到的中间元素正好和被查找的元素18相等，表示找到了：下标为8

 二分法查找的终止条件：一直折半，直到中间的那个元素恰好是被查找的元素

 

二分法查找算法是基于排序的基础之上。（没有排序的数据是无法查找的）

 publc class ArrayUtil{

   public static void main(String[] args){

      int[] arr = {100,200,230,235,600,1000,2000,9999);

      //找出arr这个数据中200所在的下标

     //调用方法

     int index = binarySearch(arr,200);

     System.out.println(index==-1?”该元素不存在!”:”该元素下标”+index);

    }

   // dest 目标元素

  //-1表示该元素不存在，其他表示返回该元素的下标

   public static void binarySearch(int[] arr,int dest){

     //开始下标

     int begin = 0;

    //结束下标

     int end = arr.length-1;

    

     //开始元素的下标只要在结束元素下标的左边，就有机会继续循环

     while(begin<=end){

     //中间元素下标

     int mid = (begin+end)/2;

     if(arr[mid]==dest){

       return mid;

     }else if(arr[mid]<dest){

       //目标在“中间”的右边

      //开始元素下标需要发生变化（开始元素的下标需要重新赋值）

      begin = mid +1;  //一直加

     }else{

      //arr[mid]>dest

      //目标在“中间”的左边

     //修改结束元素的下标

       end = mid -1;  //一直减

     }

    }

   return -1;

 }

二分法查找原理

  10（下标是0） 23 56 89 100 111 222 235 500 600（下标9）arr数组

 目标：找出600的下标

 （0+9）/2–>4(中间元素的下标）

 arr[4]这个元素就是中间元素：arr[4]是100

 100<600

  说明被查找的元素在100的右边

  那么此时开始下标变成：4+1

 

 （5+9）/2–>7（中间元素的下标）

   arr[7]对应的值是：235

   235<600

   说明被查找的元素在235的右边

  

   开始下标有进行了转变：7+1

   （8+9）/2–>8

     arr[8]–>500

     500<600

     开始元素的下标又发生了变化：8+1

     (9+9)/2–>9

     arr[9]是600，正好和600相等，此时找到了