JAVA冒泡排序和二分查找的实现_java

冒泡排序 

冒泡排序(Bubble Sort),看到这种算法,我就想起一句话“小数上浮,大数下沉”,通过层层的比较使小数浮出水面,而使大数“石沉水底”。从而达到排序的效果。冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

3. 针对所有的元素重复以上的步骤,除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序的过程图:

实例代码

public class BubbleSort{

  public static int[] bubbleSort(int[] array){
    for(int i = 0;i < array.length;i++){
      for(int j = 0; j < array.length-i-1;j++){
        if(array[j] > array[j+1]){
          int temp = array[j];
          array[j] = array[j+1];
          array[j+1] = temp;
        }
      }
      System.out.println("第"+(i+1)+"趟排序");
      for(int k = 0;k < array.length;k++){
        System.out.print(array[k]+" ");
      }
      System.out.println();
    }
    return array;
  }

  /**
   * @param args
   */
  public static void main(String[] args){
    int[] array = {7,3,9,5,6,8,1};
    bubbleSort(array);
  }

}

打印结果:

第1趟排序

3 7 5 6 8 1 9

第2趟排序

3 5 6 7 1 8 9

第3趟排序

3 5 6 1 7 8 9

第4趟排序

3 5 1 6 7 8 9

第5趟排序

3 1 5 6 7 8 9

第6趟排序

1 3 5 6 7 8 9

第7趟排序

1 3 5 6 7 8 9

二分查找

排好顺序了,也需要我们查找我们想要的数据了,而二分法查找就是其中常用的,节时的,基础的一种算法。二分查找就是从排序好数据的中间位置进行查找比较,类似于木棒的中间对砍,所以又叫折半查找,它是一种效率较高的查找方法。

【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。

【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。

重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

【算法复杂度】假设其数组长度为n,其算法复杂度为o(log(n)),最坏情况下的时间复杂度是O(n)。

实例代码

package com.somnus.array;
/**
 * 二分查找法
 * @author Compaq
 *
 */
public class BinarySearch{
  public static int binarySearch(int[] array, int value){
    int low = 0;
    int high = array.length-1;
    int middle = 0;
    while(low <= high){
      middle = (low+high)/2;//0 6  4 6  6 6
      for(int i = 0;i < array.length;i++){
        System.out.print(array[i]+" ");
        if(i == middle)//3 5 6 紧随最中间的指向 后面 打印分隔符
        {
          System.out.print("## ");
        }
      }
      System.out.println();
      if(array[middle] == value){
        return middle;
      }
      if(value < array[middle]){
        high = middle - 1;
      }
      if(value > array[middle]){
        low = middle + 1;
      }

    }
    return -1;
  }

  /**
   * @param args
   */
  public static void main(String[] args){
    int[] array = {7,3,9,5,6,8,1};
    int[] array1 = BubbleSort.bubbleSort(array);

    int index = binarySearch(array1,1);
    System.out.println("所在的位置:"+index);

  }

}

打印结果:

第1趟排序

3 7 5 6 8 1 9

第2趟排序

3 5 6 7 1 8 9

第3趟排序

3 5 6 1 7 8 9

第4趟排序

3 5 1 6 7 8 9

第5趟排序

3 1 5 6 7 8 9

第6趟排序

1 3 5 6 7 8 9

第7趟排序

1 3 5 6 7 8 9

1 3 5 6 ## 7 8 9

1 3 ## 5 6 7 8 9

1 ## 3 5 6 7 8 9

所在的位置:0

分析总结

查找算法中,二分法是速度最快的,但是必须是有序的序列。这些都是算法的基础中的基础,还需要我们下大功夫来试验,来总结,来吸收,坚持算法学习中.

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索java冒泡排序
, java冒泡排序代码
java二分查找算法
java实现冒泡排序、java实现冒泡排序算法、用java实现冒泡排序、java代码实现冒泡排序、java实现二分查找,以便于您获取更多的相关知识。

时间: 2024-12-08 17:48:59

JAVA冒泡排序和二分查找的实现_java的相关文章

冒泡排序和二分查找

js的排序 我们这里只介绍一下冒泡排序法:[其它方法可以参考 php 的排序章节]     代码: <html> <head> <meta http-equiv="content-type" content="text/html;charset=utf-8"/>   <script type="text/javascript">   var arr=[0,-1,90,-18,900,90,78];

Java实现二分查找算法实例分析_java

本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解

数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组 复制代码 代码如下: //冒泡排序(数组排序)function bubble_sort($array) { $count = count($array); if ($count <= 0) return false; for($i=0; $i<$count; $i++){ for($j=$count-1; $j>$i; $j–){ if ($array[$j] < $array[$j-1]){

冒泡排序、插入排序、选择排序、快速排序、二分查找(Objective-C实现)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 8

动态数组,数组初始化,数组内存释放,向数组中添加一个元素,向数组中添加多个元素,数组打印,顺序查找,二分查找,查找数组并返回地址,冒泡排序,改变数组中某个元素的值,删除一个数值,删除所有,查找含有

 1定义接口: Num.h #ifndef_NUM_H_ #define_NUM_H_   #include<stdio.h> #include<stdlib.h>   /************************************************************************/ /*数组的结构体类型                                                    */ /***************

Java实现二分查找算法

Java程序员总该玩点基本的算法. 1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实

java自定义类的数组的二分查找时,应该实现什么接口?

问题描述 java自定义类的数组的二分查找时,应该实现什么接口? 我在做POJ 1054时,希望对自己定义的一个类Plant进行二分查找,但是查找的结果一直不成功(未找到).我认为是没有实现判断类相等的接口中对应的方法,请问诸位该怎么实现,或者还是别的原因,烦请各位不吝赐教,谢谢! 以下是源代码,出问题的地方在searchPath方法中"当下一步在稻田内时,查找下一步的坐标是否在Plant[]中",既: if(Arrays.binarySearch(plants tmp) != -1)

二分查找-新手请教,自学java,请大家多多指教

问题描述 新手请教,自学java,请大家多多指教 java.lang.NoSuchMethodError: main Exception in thread "main" 这是学习一维数组时出现的问题,代码如下: //逐步实现二分查找法,出错 public class Study2{ // public static void main(String[] args){ public static int binarySearch(int[] list,int key){ int low

js基本算法:冒泡排序,二分查找的简单实例_基础知识

知识扩充: 时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间.时间复杂度越低,效率越高. 自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n). 1.冒泡排序 解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置. 2.第一轮的时候最后一个元素应该是最大的一个. 3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较. function sort(elements){ for(var i