Home>

This article details the implementation of java bubble sort and binary search,Although these two algorithms are relatively simple,But indeed we must master.Let ’s take a look.

Bubble Sort

Bubble sort, see this algorithm,I thought of the phrase "Decimal floating up,"Small number sinking", through the comparison of layers to make small numbers surface,And make the large numbers "stone sinking into the water." So as to achieve the effect of sorting.Bubble sort is a simple sorting algorithm.It repeatedly visits the sequence to be sorted,Compare two elements at a time,Swap them if they are out of order.Visiting the sequence is repeated until there is no longer a need for exchange,In other words, the sequence has been sorted.The name of the algorithm comes from the fact that the smaller elements will slowly "float" to the top of the sequence through swapping.

The operation of the bubble sort algorithm is as follows:

1. Compare adjacent elements.If the first is larger than the second,Just swap them both.

2. Do the same for each pair of adjacent elements,The first pair from the beginning to the end.At this point,The last element should be the largest number.

3. Repeat the above steps for all elements,Except the last one.

4. Repeat the above steps every time for fewer and fewer elements,Until no pair of numbers need to be compared.

Process diagram of bubble sorting:

Example code

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 ("Article" + (i + 1) + "Sort Sort");
      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);
  }
}

Print results:

Sort 1
3 7 5 6 8 1 9
Sort 2
3 5 6 7 1 8 9
Sort 3
3 5 6 1 7 8 9
Sort 4
3 5 1 6 7 8 9
Sort 5
3 1 5 6 7 8 9
Sort 6
1 3 5 6 7 8 9
Sort 7
1 3 5 6 7 8 9

Binary search

Ordered,We also need to find the data we want,The dichotomy search is commonly used among them.Time-saving, a basic algorithm.Binary search is to search and compare from the middle position of sorted data.Similar to the middle cut of a stick,So it's called half search,It is a more efficient search method.

[Binary search requirements]:1. Must use sequential storage structure 2. Must be arranged in order by keyword size.

[Pros and cons]The advantage of half-finding is that it has fewer comparisons.Find fastAverage performance is good;The disadvantage is that the table to be checked is an ordered list.And insertion and deletion are difficult.Therefore, the half search method is suitable for an ordered list that is not frequently changed and is frequently searched.

[Algorithm]First, compare the keywords recorded in the middle of the table with the lookup keywordsIf they are equal,The search is successful;Otherwise use the middle position record to split the table into the first and last two child tablesIf the keyword recorded in the middle position is greater than the search keyword,Then look up the previous subtable further,Otherwise, the latter sub-table is further searched.

Repeat the above process,Until you find a record that meets the conditions,Make the lookup successful,Or until the child table does not exist,The lookup was unsuccessful at this time.

[Algorithm complexity]Assuming its array length is n and its algorithm complexity iso (log (n)),Worst case time complexity iso (n).

Example code

package com.somnus.array;
/**
 * Binary Search
 * @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 Immediately after the middle point, print the separator
        {
          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 ("Location:" + index);
  }
}

Print results:

Sort 1
3 7 5 6 8 1 9
Sort 2
3 5 6 7 1 8 9
Sort 3
3 5 6 1 7 8 9
Sort 4
3 5 1 6 7 8 9
Sort 5
3 1 5 6 7 8 9
Sort 6
1 3 5 6 7 8 9
Sort 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
Location:0

analysis Summary

In the search algorithm,Dichotomy is the fastest,But it must be an ordered sequence.These are the foundations of the foundation of the algorithm,We still need to work hard to experiment,Summarize, absorb, and persist in algorithm learning.

  • Previous Reverse Ajax in 30 minutes
  • Next Jquery method to implement click to change navigation style