用折半查找法在一组排好序(递增有序或递减有序)的值中查找某个数据+ 冒泡排序+选择排序+数组排序(例子)

时间:2022-06-05 11:40:08

用折半查找法在一组排好序(递增有序或递减有序)的值中查找某个数据+ 冒泡排序+选择排序+数组排序(例子)

用折半查找法在一组排好序(递增有序或递减有序)的值中查找某个数据+ 冒泡排序+选择排序+数组排序(例子)

/**

 * 二分法 :用折半查找法在一组排好序(递增有序或递减有序)的值中查找某个数据。

 *

 * 基本思想:

 *

 * 首先将待查数据k与排好序(递增有序)的一组数据的中间位置上的数据进行比较, 若相等,则查找成功;

 * 若k>a[mid],则待查数据k只可能出现在右半部a[mid+1…n]中,则应在这个右半部中再进行折半查找;

 * 若k<a[mid],则待查数据k只可能出现在左半部a[1…mid-1]中,则应在这个左半部中再进行折半查找;

 * 这样通过逐步缩小查找范围,直到找到或找不到该数据k为止。

 *

 * @author Administrator

 *

 */

package com.my.test;

import java.util.Arrays;

public class CTest {

    public static void main(String[] ss) 
    {
        int[] a = { 3, 4, 2, 8, 6, 0, 7, 5, 9, 1 };

        System.out.println("原  数   组: " + Arrays.toString(a));

        Arrays.sort(a);
        System.out.println("集合排序: " + Arrays.toString(a));

        // 冒泡排序
for (int i = 0; i < a.length; i++) 
        {
            for (int j = i + 1; j < a.length - i; j++) 
            {
                int tmp = 0;
                if (a[i] > a[j]) 
                {
                    tmp = a[j];
                    a[i] = a[j];
                    a[j] = tmp;
                }
            }
        }
        System.out.println("冒泡排序: " + Arrays.toString(a));
        
        
        //选择排序
        int[] c = { 3, 4, 2, 8, 6, 0, 7, 5, 9, 1 };
        int tmp = 0;
        for (int i=0;i<c.length-1;i++)
        {
            int lowIndex = 0; //找出最小的一个索引
            for (int j=i+1;j<c.length-1;j++)
            {
                if (c[i]>c[j])
                {
                    lowIndex = j;
                }
            }
            //交换
            tmp = c[i];
            c[i] = c[lowIndex];
            c[lowIndex] = tmp;
        }
        System.out.println("选择排序: " + Arrays.toString(a));
        
        // 测试二分法查找
        int[] b = { 1, 3, 5, 7, 9, 12, 13, 15 };

        System.out.println(BinarySearch(b, 9));

    }

    /**
     * 
     * @Title: 二分法查找
     * @Description: TODO
     * @param a
     * @param key
     * @return int
     */
    public static boolean BinarySearch(int[] Data, int KeyValue) 
    {
        int Left = 0; // 左边界变量
        int Right = 0; // 右边界变量
        int Middle; // 中位数变量

        while (Left <= Right) 
        {
            Middle = (Left + Right) / 2;
            if (KeyValue < Data[Middle]) // 查找值比中间值小
            {
                Right = Middle - 1; // 查找前半段
            } 
            else if (KeyValue > Data[Middle])// 查找值比中间值大
            {
                Left = Middle + 1; // 查找后半段
            }
            else if (KeyValue == Data[Middle]) // 查找到数据
            {
                System.out.println("Data[" + Middle + "] = " + Data[Middle]);
                return true;
            }
        }
        return false;
    }

}