一、 递归
一个调用它本身的函数称为递归（Recursive）函数。在编写程序时，也常来处理某些问题，而这些问题通常有相同的规则，下面将举例说明。
n 阶乘
n!=n ×(n-1)!
(n-1)!=(n-1)×(n-2)!
(n-2)!=(n-2)×(n-3)!
…
1!=1
从上述公式可得知其相同的规则为:某一数A的阶乘为本身A乘以(A-1)的阶乘。其程序如下:
public int fun(int n){
int a;
if(n==1)
a=1；
else
a=n * fun (n-1);
return a;
}
在编写递归程序时，记住必须有一个结束点，可以使函数往上追溯直到结束。如上例中，当 n= 1 时，1！= 1 即为其结束点。
程序解说
下图表示n！阶乘，假设n=4，如图
二、 排序
（冒泡排序，选择排序，插入排序，归并排序，快速排序，希尔排序）
1、冒泡排序：
冒泡排序（Bubble Sont）又称为交换排序（Interchange Sont）。相邻两个相比，如果前一个比后一个大时，则互相对调。通常有 n 个数据时需要做n+1次扫描，一次扫描完后，数据量减少 1，当没有数据需要对调时，就表示已好排好序了。
例如，有 5 个数据分别是20，2，25，56，15 冒泡排序的步骤如下；
冒泡排序一样是稳定的，最坏时间与平均时间都是 O(n2)，所需要额外空间也很少。
代码解释：
public class test {
public static void main(String[] args) {
int a[]={20,2,25,56,15};
talk(a);
}
public static void talk(int a[]){
p(a);//打印出原来的数组顺序
int i,j,temp;
//让数据两两作对比，将小的置于前
for( i=0;i<a.length;i++){
int flag=0;//退出冒泡循环的标志
for (j = 0; j < a.length-i-1; j++) {
if (a[j] > a[j+1]){
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
flag=1;
p(a);
}
}
if(flag != 1) {
break;
}
}
}
/*打印数组方法*/
private static void p(int a[]){
for(int i : a){
System.out.print(i+" ");
}
System.out.println();
}
}
结果：
20 2 25 56 15
2 20 25 56 15
2 20 25 15 56
2 20 15 25 56
2 15 20 25 56
2、选择排序
选择排序（Selection Sort）首先在所有的数据中挑选一个最小的放在第一个位置由小到大排序)，再从第二个开始挑选一个最小的放于第二个位置，以此类推。假设有n个记录，则最多需要 n-1 次对调，以及n(n-1)2次比较。
例如，有 5 个记录，为 16,4,20,35,15。利用选择排序，其做法如下：
选择排序跟冒泡排序一样是稳定的，最坏时间与平均时间都是 O(n2)，所需要额外空间也很少。
代码解释：
public class test2 {
public static void main(String[] args) {
int a[]={16,4,20,35,15};
talk(a);
}
public static void talk(int a[]){
int min,temp;
for (int i = 0; i < a.length-1; i++) {
min=i;
for (int j = i+1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min) {
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
p(a);
}
}
private static void p(int a[]){
for (int i : a){
System.out.print(i+" ");
}
System.out.println();
}
}
结果：
4 16 20 35 15
4 15 20 35 16
4 15 16 35 20
4 15 16 20 35
3、插入排序
插入排序（Insertion Sort）是将插入的数据置于原来的文件适当的位置，如下图：
插入排序是稳定的，最坏的时间与平均时间为O(n2)，所需的额外空间少。
代码解释：
4、归并排序
归并排序（Merge Sont）是将两个或两个以上已排序好的文件，合并成一个大的已排序好的文件。
例如，有两个已排序好的文件分别为
甲= {4, 8, 12, 16, 25}
乙= {6, 10, 15，35, 40}
归并排序过程如下：甲文件的第一个数据是4，而乙第一个数据是6，由于4小于6，故将4写入两文件的第一个数据；甲文件的第二个数据是8，8 比6 大，故 6写入丙文件；乙文件的第二个数据为10，12比10大。故10写入丙文件：以此类推，最后丙文件为{4,6,8,10,12,15,16,25,35,40}。
5、快速排序
快速排序（Quick Sont）又称为划分交换排序（Parition Bxchange Sorig），就平的时间而言，快速排序是所有排序中最佳的。假设有 n个 R1, R2,R3，…R，其关键字为K1，K2,以.…,Kn。快速排序法的步骤如下：
- 以第一个记录的关键字 k1 做基准 K。
- 由左至右i=2,3,…,n，一直找到ki > K.
- 由右至左j= n, n-1,n-2,…,2，一直找到kj≤ K。
- 当i<j时 Ri与 Rj 互换，否则 R1 与Rj互换。
由图可以看出39左边都是比39小的，右边是比39大的，所以继续用上述方法即可（形成递归）
6、希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序方法：
(1）先将所有的数据分成Y=（9 Div 2)部分Y=4，Y 为划分数。
(2)每个循环的划分数是 Y，都是上一循环二分数除 2，即 Yi= Yi Div 2，逐渐缩小的增量组成一个序列： [n/2, n/2/2, … 1]，最后一个循环的划分数为1，当增量等于 1 时，排序整个数组后，排序完成。
public class rc {
public static void main(String[] args) {
int a[]= {10, 22, 18, 45, 25, 75, 64, 45, 99};
talk(a);
}
private static void talk(int[] a) {
int step = a.length / 2; //步长，默认取数组长度一半
int temp;
while (step > 0) {
for (int i = step; i <a.length; i++) {
temp = a[i];//当前值
int preIndex = i - step; //步长间隔上一个值的下标
//在步长间隔的的数组中，找到需要插入的位置，挪动右边的数
while (preIndex >= 0 && a[preIndex] > temp) {
a[preIndex + step] = a[preIndex];
preIndex -= step;
}
//把当前值插入到在步长间隔的的数组中找到的位置
a[preIndex + step] = temp;
}
step /= 2;
p(a);
}
}
private static void p(int[] a) {
for(int i : a) {
System.out.print(i + " ");
}
System.out.println();
}
}
结果：
10 22 18 45 25 75 64 45 99
10 22 18 45 25 45 64 75 99
10 18 22 25 45 45 64 75 99