1. 查找

1.1 顺序查找

public class test {
    public static void main(String[] args){
        // 定义数组
        int [] array1  = {1,2,4,5,6,8,234,64,32,565,62,54};
        // 确定查找数值
        int targetNum = 8;
        // 调用函数
        int index = findtarget(array1,targetNum);

        if (index==-1){
            System.out.println("没查到");
        }else{
            System.out.println(targetNum+" 查到了索引是："+index);
        }
    }

    private static int findtarget(int[] array,int targetNum){
        int index=-1;
        for (int i=0;i<array.length;i++){
            if(array[i]==targetNum){
                index = i;
                break;
            }
        }
        return index;
    }
}

1.2 二分查找（使用条件：查找序列是顺序结构，有序。）

• 优点
  • 比较次数少，查找速度快，平均性能好；
• 缺点
  • 要求待查表为有序表，且插入删除困难。

所以，折半查找方法适用于不经常变动而查找频繁的有序列表。

• 二分查找（不使用递归）： ```java /**
• 循环二分查找，返回第一次出现该值位置，前提是有序，

• 二分查找必须使用顺序存储结构 */ public class BinarySearch { public static void main(String[] args) { // 定义数组 int[] array1 = {1,2,3,4,5,6,7,8,9,10,11,12}; // 确定查找数值 int targetNum = 8; // 调用函数 int index = findtarget(array1, targetNum);

   if (index == -1) {
       System.out.println("没有找到");
   } else {
       System.out.println(targetNum + " 找到了索引是：" + index);
   }  }
  

  private static int findtarget(int[] array1, int targetNum) { int low = 0; int high = array1.length - 1; int middle = 0;

   if(targetNum < array1[low] || targetNum > array1[high]){
       return -1;
   }
  
   while (low <= high) {
       middle = (low + high) / 2;
       if (array1[middle] > targetNum) {
           //比关键字大则关键字在左区域
           high = middle - 1;
       } else if (array1[middle] < targetNum) {
           //比关键字小则关键字在右区域
           low = middle + 1;
       } else {
           return middle;
       }
   }
   return -1;  } } ```
  

• 二分查找（使用递归）： ```java /**
• 循环二分查找，返回第一次出现该值位置，前提是有序，

• 二分查找必须使用顺序存储结构 */ public class BinarySearch1 { public static void main(String[] args) { // 定义数组 int[] array1 = {1,2,3,4,5,6,7,8,9,10,11,12};

   // 确定查找数值
   int targetNum = 8;
      
   // 调用函数
   int low = 0;
   int high = array1.length - 1;
      
   int index = findtarget(array1, targetNum,low, high);
      
   if (index == -1) {
       System.out.println("没有找到");
   } else {
       System.out.println(targetNum + " 找到了索引是：" + index);
   }  }
  

  private static int findtarget(int[] array1, int targetNum,int low,int high) { if(targetNum < array1[low] || targetNum > array1[high]){ return -1; }

   int middle = (low + high) / 2;
      
   if (array1[middle] > targetNum) {
       //比关键字大则关键字在左区域
       return findtarget(array1, targetNum, low, middle - 1);
   } else if (array1[middle] < targetNum) {
       //比关键字小则关键字在右区域
       return findtarget(array1, targetNum, middle + 1, high);
   } else {
       return middle;
   }  } } ``` # 2. 排序 ## 2.1 选择排序
  

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

public class test {
    public static void main(String[] args) {
        int[] array1 = {1, 2, 4, 9, 6, 4, 2, 4, 6, 8, 2};
        selectionSort(array1);
        System.out.println("从小到大排序后的结果是:");
        for (int j : array1) System.out.print(j + " ");
    }

    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {//交换次数
            //先假设每次循环时，最小数的索引为i
            int minIndex = i;
            //每一个元素都和剩下的未排序的元素比较
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {//寻找最小数
                    minIndex = j;//将最小数的索引保存
                }
            }
            //经过一轮循环，就可以找出第一个最小值的索引，然后把最小值放到i的位置
            swap(arr, i, minIndex);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

我们对比一下C语言

#include<iostream>
using namespace std;
#define N 6
int main()
{
	int x[N],i,j,min,temp;
	printf("请输入%d数据:",N);
	for(i=0;i<N;i++)
		scanf("%d",&x[i]);
	for(i=0;i<N-1;i++)
	{  
		min=i;
		for(j=i+1;j<N;j++)
			if(x[min]>x[j])
				min=j;
			if(i!=min)
			{
				temp=x[i];
				x[i]=x[min];
				x[min]=temp;
			}
	}
	printf("排序的顺序为：");
	for(i=0;i<N;i++)
		printf("%2d",x[i]);
}

2.2 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

public class test {
    public static void main(String[] args) {
        int[] array1 = {1, 2, 4, 9, 6, 4, 2, 4, 6, 8, 2};
        //需进行length-1次
        for (int i = 0; i < array1.length - 1; i++) {
            for (int j = 0; j < array1.length - 1 - i; j++) {
                if (array1[j] > array1[j + 1]) {
                    int temp = array1[j];
                    array1[j] = array1[j + 1];
                    array1[j + 1] = temp;
                }
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for (int j : array1) System.out.print(j + " ");
    }
}

我们对比一下C语言

#include<iostream>
using namespace std;
#define N 6
int main()
{
	int x[N],i,j,temp;
	printf("请输入%d数据:",N);
	for(i=0;i<N;i++)
		scanf("%d",&x[i]);
	for(i=0;i<N-1;i++)
		for(j=0;j<N-1-i;j++)
			if(x[j]>x[j+1])
			{
				temp=x[j];
				x[j]=x[j+1];
				x[j+1]=temp;
			}
	printf("排序的顺序为：");
	for(i=0;i<N;i++)
		printf("%2d",x[i]);
}