a[mid] > a[low]，即数组前半部分为严格递增数组，后半部分为循环递增数组时，若
key 小于 a[mid]并且不小于 a[low]时，则 key 落在数组前半部分；否则，key 落在数组
后半部分。
a[mid] < a[high]，即数组前半部分为循环递增数组，后半部分为严格递增数组时，
若 key 大于 a[mid]并且不大于 a[high]时，则 key 落在数组后半部分；否则，key 落在
数组前半部分。
这种方式的时间复杂度为：O(log(n))，空间复杂度为 O(1)。
public class TestBinarySearch {
public static void main(String[] args) {
// 定义数组
int[] a = { 17, 19, 20, 21, 25, 1, 4, 7 };
// 调用改进后的二分查找法求索引
int pos = search(a, 7);
System.out.println("要查找的元素的索引为：" + pos);
}
/** 改进后的二分查找法：e 为要查找的元素 */
public static int search(int[] a, int e) {
int low = 0;
int high = a.length - 1;
int mid = 0;
int pos = -1; // 返回-1，表示查找失败
// 如果 low < high，说明循环查找结束，直接返回-1;否则循环查
找
while (low <= high) {
// mid 为中间值索引
mid = (low + high) / 2;
// 如果中间值刚好是 e，则查找成功，终止查找，e 的索引为 mid
if (a[mid] == e) {
pos = mid;
break;
}
// 如果 a[low] <= a[mid]，说明原数组的前半部分是严格递增
的，后半部分是一个更小的循环递增数组
if (a[low] <= a[mid]) {
// 如果要查找的元素 e 小于 a[mid]并且不小于 a[low]时，
则说明 e 落在数组前半部分
if (a[low] <= e && e < a[mid]) {
high = mid - 1;
} else {// 否则的话，需要在数组的后半部分继续查找
low = mid + 1;
}
} else {// 否则，后半部分是严格递增的，前半部分是一个更
小的循环递增数组
// 如果要查找的元素 e 大于 a[mid]并且不大于 a[high]时，
则说明 e 落在数组后半部分
if (a[mid] < e && e <= a[high]) {
low = mid + 1;
} else {// 否则的话，需要在数组的前半部分继续查找
high = mid - 1;
} } }
return pos; } }
请编写一个完整的程序，实现如下功能：从键盘输入数字 n，程序自动
计算 n!并输出。（注 1：n！=123...n, 注 2：请使用递归实现）
思路说明：因为 n! = (n-1)! * n，所以要求 n!首先要求出(n-1)!，而(n-1)! = (n-1-1)! *
(n-1)，以此类推，直到 n = 1 为止。
import java.util.Scanner;
public class TestFactorial {
public static void main(String[] args) {
System.out.print("请输入一个整数：");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(n + "的阶乘是：" + factorial(n));
}
/**求阶乘的方法/
public static int factorial(int n) {
if(n == 1){
return 1;
}
return factorial(n - 1) * n; } }
请用递归的方法计算斐波那契数列的同项 F（n），已知
F0=0,F1=1,F(n)=F(n-1)+F(n-2)(n>=2,n∈N*).
思路说明：斐波那契数列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，
144……，特别指出的是 0 不是第一项而是第 0 项；因为 F(n)=F(n-1)+F(n-2)，所以要
求 F(n)首先要求出 F(n-1)和 F(n-2)，而 F(n-1)=F(n-1-1)+F(n-1-2)，以此类推，直
到,F(2)=F(1)+F(0)为止，已知 F(1) = 1，F(0) = 0。
import java.util.Scanner;
public class TestFibo {
public static void main(String[] args) {
System.out.print("请输要求斐波那契数列的第几项：");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println("斐波那契数列的第"+ n + "是：" +
fibo(n));
}
public static int fibo(int n) {
if(n == 0){
return 0;
} else if(n == 1){
return 1;
}
return fibo(n -1) + fibo(n - 2);
} }
现在有整数数组{11,66,22,0,55,32}，请任意选择一种排序算法，用
Java 程序实现
冒泡思路说明：
(1) 最开始将数组看做一个无序数列(个数是数组的长度)与一个有序数列(0 个)的组合；
(2) 每一趟比较完后, 找到了无序数列的最大值, 将其放到有序数列中(有序数列个数+1)；
(3) N 个数, 比较 N-1 趟；
(4) 每一趟挨个进行比较：从数组的第一个元素开始, 到无序数列的最后一个为止；
(5) 如果前边一个大于后边一个, 那么交换位置；
(6) 每趟比较的次数与趟数有关；
(7) 根据每趟比较是否发生了交换判断数据是否已经有序，从而进行优化。
public class TestSort {
public static void main(String[] args) {
int[] arr = {11, 66, 22, 0, 55, 32};
// 调用排序方法
sort(arr);
// 输出排除后的数组
for (int num : arr) {
System.out.print(num + "\t");
} }
public static void sort(int[] arr) {
// 定义标记
boolean flag = false;
int temp;
// 排序
// 外层循环控制的是比较的趟数
for (int i = 0; i < arr.length - 1; i++) {
// 每一趟比较之前初始化, 否则会保留上一堂比较的结果
flag = false;
// 内层循环控制的是每趟比较的次数
for (int j = 0; j < arr.length - 1 - i; j++) {
// 挨个进行比较: 从数组的第一个元素开始, 到无序数列的
最后一个
if (arr[j] > arr[j + 1]) {
// 交换
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//如果发生交换，改变 flag 的值
flag = true; } }
if (!flag) {
break; } } } }