当前位置：首页 > news >正文

详解：递归和排序（冒泡排序，选择排序，插入排序，归并排序，快速排序，希尔排序）

news 来源：原创 2024/9/20 9:28:59

一、递归

一个调用它本身的函数称为递归（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(n²)，所需要额外空间也很少。
代码解释：

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(n²)，所需要额外空间也很少。

代码解释：

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(n²)，所需的额外空间少。
代码解释：

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();
    }

}