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

分析总结

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

(0)

相关推荐

  • java 算法二分查找和折半查找

     java 算法二分查找与折半查找 折半查找 :首先数组是已经排好序的 实例代码: package com.hao.myrxjava; /** * 折半查找 :首先数组是已经排好序的 * * @author zhanghaohao * @date 2017/5/15 */ public class HalfDivision { /** * 循环实现 * * @param array 排好序的数组 * @param value 查找的值 * @return value在array的位置 */ pu

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • Java经典算法汇总之顺序查找(Sequential Search)

    a)原理:顺序查找就是按顺序从头到尾依次往下查找,找到数据,则提前结束查找,找不到便一直查找下去,直到数据最后一位. b)图例说明: 原始数据:int[]a={4,6,2,8,1,9,0,3}; 要查找数字:8 找到数组中存在数据8,返回位置. 代码演示: import java.util.Scanner; /* * 顺序查找 */ public class SequelSearch { public static void main(String[] arg) { int[] a={4,6,2

  • java 折半查找法(二分查找)实例

    复制代码 代码如下: public class HalfSearch { public static int halfSearch(int a[], int x) {  int mid, left, right;  left = 0;  right = a.length - 1;   mid = (left + right) / 2;  while (a[mid] != x) {   if (x > a[mid]) {    left = mid + 1;   }   else if (x <

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • 使用javascipt---实现二分查找法

    复制代码 代码如下: <html><head><meta http-equiv="Content-Type" content="text/html;charset=utf-8"><script type="text/javascript"> //window.alert(Math.floor(5.7)); //向下取整 输出5 //二分查找法 数组必须是有序的 function binarySeac

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

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

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

  • java二分查找插入法

    复制代码 代码如下: package uv; public class Bean  implements Comparable<Bean>  {String sessionId;Integer num = 1;public String getSessionId() {return sessionId;}public void setSessionId(String sessionId) {this.sessionId = sessionId;}public Integer getNum()

  • Java使用二分法进行查找和排序的示例

    实现二分法查找 二分法查找,需要数组内是一个有序的序列 二分查找比线性查找:数组的元素数越多,效率提高的越明显 二分查找的效率表示:O(log2N) N在2的M次幂范围,那查找的次数最大就是M,  log2N表示2的M次幂等于N, 省略常数,简写成O(logN) 如有一个200个元素的有序数组,那么二分查找的最大次数: 2^7=128, 2^8=256, 可以看出7次幂达不到200,8次幂包括, 所以最大查找次数就等于8 //循环,二分查找 static int binarySearch(int

随机推荐