算法基础二：渐增型算法---插入排序

2022-12-07 11:43:55

算法基础二：渐增型算法---插入排序

一、渐增型算法是什么

渐增型算法（incremental algorithms)指的是算法使得标识问题的解从较小的部分渐渐扩张，最终成长为完整解。渐增型算法有一个共同的特征：构成算法的主体是一个循环结构，它逐步将部分解扩张成一个完整解。该循环将遵循一个始终不变的原则：每次重复之初，总维持着问题的一个部分解。我们将此特征称为算法的循环不变量（loop invariant）。下面将介绍几种典型的渐增型算法。

二、插入排序算法

1、算法描述与分析

①问题的理解与描述

输入：一组数<a1,a2,...,an>

输出：输入的一个排列（重排）：<a1',a2',...,an'>，满足a1'<a2'<...<an'

从小到大的顺序称为升序，反之从大到小为降序。

②插入排序的例子

摸扑克牌，我们左手拿着扑克牌，右手去摸牌，每次获得新的扑克牌后，放入左手，自动为其排序，找到这张扑克牌应在的位置。左手中的扑克牌始终是排好序的，等最后一张摸完之后，也就都排完了序。

③算法的伪代码描述

2、程序实现的注意点

①参数与返回值

参数：一个参数，等待排序的序列A。

返回值：由于排序的结果维持在A中，所以无需返回值。

注意的点：要转换成程序的时候，需要向程序过程传递等待排序的序列A，但是需要考虑A中的元素是什么类型，A按怎样的结构加以存储（数组还是链表）

②数据设置

INSERTION-SORT中所访问的变量包括两重循环嵌套的控制变量，i和j，j控制外层的for循环，i控制内层while循环。初次之外，还需要序列元素A[j]的值暂存变量key。

3、Java语言实现----整型数组版本

①算法代码

public class InsertSort_01 {

    public static void insertionSort(int[] a){
        int i,j,key,n=a.length;
        for (j=1;j<n;j++){
            key = a[j];//key<-a[j]
            i=j-1;//第一次：key为第二个，i为第一个，两个作比较。
            while (i>=0 && a[i]>key){//注意此处的大于等于
                a[i+1] = a[i];//前后互换
                i--;//i<-i-1,i一直到不大于key或者为-1，空出来一个位置
            }
            a[i+1] = key;//a[i+1] <- key，填补空缺的那个位置
        }
    }

}

由于a是一个数组，数组是一个对象，它具有自己的长度属性length，所有不需要传递长度的信息。
数组下表从0开始，这点需要注意。
方法被定义为静态的static，这样这个方法是从属于这个类的，而不从属于该类的任何一个实例对象。因此，可以在需要的时候用“类名.方法名”的形式调用。

②测试类

public class Test_InsertSort_01 {

    public static void main(String[] args) {
        int A[] = {5,1,9,4,6,2,0,3,8,7};
        int i ;
        InsertSort_01.insertionSort(A);
        for (i = 0; i < 10; i++) {
            System.out.println(A[i]);
        }
        System.out.println();
    }

}

4、Java语言实现---可比较类型数组版本

①Comparable接口

我们在字符串中见到过CompareTo方法,知道这个方法是用于比较字符串顺序的,根据字典顺序进行排序。Java中很多类也都有CompareTo方法，甚至于排序算法的底层组成也是依赖于比较的，而这个比较就是依赖于各种数据类型的CompareTo或者Compare方法。Java中所有的compareTo方法都源于一个共同的接口，那就是Comparable。这个接口只有一个方法，那就是CompareTo。所有想要具有比较功能的类，都建议实现这个接口，而非是自己定义这个功能，这是面向对象的概念（将具有相同功能的事物抽象到一个共同的类或接口），并且为了多态也建议通过实现接口来进行向上转型，通过接口来操作具体实现，这也是面向接口编程要求我们做的。下面我们来具体了解一下Comparable接口。

详细学习参考：

https://www.cnblogs.com/lin-jing/p/8278271.html

理解：所有实现了Comparable接口的类必须覆盖此抽象方法，使之能比较这种类的对象x和另一个对象y之间的大小：

x>y返回1，x<y返回-1，x=y返回0

在Java中，只有基本的数值类型（整型、字符型、浮点型）才有比较运算符<、>、<=、>=并且没有运算符重载功能。
int char double float等基本类型的包装类，Integer Character Double Float等以及字符串类String都已经实现了Comparable的类。系统以及为其实现了compareTo方法，可以直接使用。

②算法代码

public class InsertSort_02 {

    public static void insertionSort(Comparable[] a){
        int i,j,n=a.length;
        Comparable key;
        for (j=1;j<n;j++){
            key = a[j];
            i = j-1;
            while (i>=0 && a[i].compareTo(key)>0){//a[i]>key
                a[i+1] = a[i];
                i--;
            }
            a[i+1]=key;
        }
    }

}

参数a由基本整型数组改变为Comparable型的数组。这样，所有实现了Comparable接口的类的对象，就可以作为数组元素都能用此方法进行排序了。
临时变量key应当与输入的数组元素类型一致，所以它是Comparable型的。
a[i].comparaTo(key)>0，可以看出上面我们提到的包装类比较大小的方式。

③测试代码

public class Test_InsertSort_02 {

    public static void main(String[] args) {
        Integer[] a = {5,1,9,4,6,2,0,3,8,7};
        String[] b = {"ChongQing","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
        Double[] c = {8.5,6.3,1.7,9.2,0.5,2.3,4.1,7.4,5.9,3.7};

        int i;
        InsertSort_02.insertionSort(a);
        for (i=0; i<10; i++){
            System.out.print(a[i]+"");
        }
        System.out.println();

        InsertSort_02.insertionSort(b);
        for (i=0;i<b.length;i++){
            System.out.print(b[i]+"");
        }
        System.out.println();

        InsertSort_02.insertionSort(c);
        for (i=0;i<c.length;i++){
            System.out.print(c[i]+"");
        }
        System.out.println();
    }

}

5、Java语言实现---任意可比较类型线性表容器版本

Java的集合类Collection Framework的标准程序库中，提供了表示集合的类，包括存储线性表的List容器。List类有数组表ArrayList、链表LinkedList和向量Vector等子类。利用Java中的类的继承关系，我们用下面程序解决所有存储Comparable数据的线性表容器的插入排序问题。

①算法代码

import java.util.List;

public class InsertSort_03 {

    public static void insertionSort(List<Comparable> a){

        int i,j,n=a.size();
        Comparable key;
        for (j=1;j<n;j++){
            key = a.get(j); //key<-a[j]
            i=j-1;
            while (i>=0 && (a.get(i).compareTo(key)>0)){//i>=0且a[i]>key
                a.set(i+1,a.get(i));//a[i+1]<-a[i]
                i--;
            }
            a.set(i+1,key);//a[i+1]<-key
        }

    }

}

程序解析：

a的类型是List<Comparable>，说明凡是数据类型实现了Comparable接口的任何继承List的线性表都可用此函数对其进行插入排序。
元素的下标访问方式：a.get(i)
改写值：a.set(i)

②测试代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public class Test_InsertSort_03 {

    public static void main(String[] args) {
        Integer[] a = {5,1,9,4,6,2,0,3,8,7};
        String[] b = {"ChongQing","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
        Double[] c = {8.5,6.3,1.7,9.2,0.5,2.3,4.1,7.4,5.9,3.7};

        int i;
        ArrayList<Integer> A = new ArrayList<Integer>();
        for (Integer integer : a) {
            A.add(integer);
        }
        Vector<String> B = new Vector<>();
        for (String s : b) {
            B.add(s);
        }
        LinkedList<Double> C = new LinkedList<>();
        for (Double aDouble : c) {
            C.add(aDouble);
        }

        InsertSort_03.insertionSort((List)A);
        System.out.println(A);
        InsertSort_03.insertionSort((List)B);
        System.out.println(B);
        InsertSort_03.insertionSort((List)C);
        System.out.println(C);
    }

}

6、Java语言实现---双向排序版本

我们可以对线性表进行任何方向的排序。先设计两个实现了Comparator的类：

import java.util.Comparator;

public class Greater implements Comparator<Comparable> {
    public int compare(Comparable x, Comparable y){
        return x.compareTo(y);
    }
}

import java.util.Comparator;

public class Less implements Comparator<Comparable> {
    @Override
    public int compare(Comparable o1, Comparable o2) {
        return o2.compareTo(o1);
    }
}

解释说明：

与Comparable接口类似，Comparator接口也只有一个抽象方法compare。与Comparable不同的是，Comparator的compare方法有两个参数x和y，而Comparable的compareTo方法只有一个参数。
Comparable往往依附于某个类，compareTo作为该类的对象的方法完成与另一个同类对象的比较。
Comparator<T>往往自成一个类，compare方法比较的是类T的两个对象的大小。
这里意思就是说，comparator比较的是两个实现了Comparable类的大小。

①算法代码

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class InsertSort_04 {
    
    public static void insertionSort(List<Comparable> a, Comparator comp){
        int i,j,n=a.size();
        Comparable key;
        for (j=1;j<n;j++){
            key = a.get(j);
            i = j-1;
            while (i>=0 && comp.compare(a.get(i),key)>0){
                i--;
            }
            Collections.rotate(a.subList(i+1,j+1),1);
        }
    }
    
}

②测试类

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public class Test_InsertSort_04 {

    public static void main(String[] args) {
        Integer[] a = {5,1,9,4,6,2,0,3,8,7};
        String[] b = {"ChongQing","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
        Double[] c = {8.5,6.3,1.7,9.2,0.5,2.3,4.1,7.4,5.9,3.7};

        int i;
        ArrayList<Integer> A = new ArrayList<Integer>();
        for (Integer integer : a) {
            A.add(integer);
        }
        Vector<String> B = new Vector<>();
        for (String s : b) {
            B.add(s);
        }
        LinkedList<Double> C = new LinkedList<>();
        for (Double aDouble : c) {
            C.add(aDouble);
        }

        InsertSort_04.insertionSort((List)A,new Greater());
        System.out.println(A);
        InsertSort_04.insertionSort((List)B,new Less());
        System.out.println(B);
        InsertSort_04.insertionSort((List)C,new Less());
        System.out.println(C);
    }

}

三、冒泡排序——练习

1、从小到大排列

public class BubbleSort {

    public static void bubbleSort(int[] a){

        int i,j;

        for (i=0;i<a.length-1;i++){//需要进行length-1次冒泡
            for (j=0;j<a.length-1;j++){
                if (a[j]>a[j+1]){
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }

    }

}

2、从大到小排列

public static void bubbleSort2(int[] a){

    int i,j;

    for (i=0;i<a.length-1;i++){
        for (j=0;j<a.length-1;j++){
            if (a[j+1]>a[j]){
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }

}

3、测试

import org.junit.Test;

public class Test_Bubble {

    public static void main(String[] args) {
        int A[] = {5,1,9,4,6,2,0,3,8,7};
        int i ;
        BubbleSort.bubbleSort(A);
        for (i = 0; i < 10; i++) {
            System.out.println(A[i]);
        }
        System.out.println();

    }

    @Test
    public void bubble2(){
        int A[] = {5,1,9,4,6,2,0,3,8,7};
        int i ;
        BubbleSort.bubbleSort2(A);
        for (i = 0; i < 10; i++) {
            System.out.println(A[i]);
        }
        System.out.println();
    }

}

码农公寓

算法基础二：渐增型算法---插入排序

一、渐增型算法是什么

二、插入排序算法

1、算法描述与分析

①问题的理解与描述

②插入排序的例子

③算法的伪代码描述

2、程序实现的注意点

①参数与返回值

②数据设置

3、Java语言实现----整型数组版本

①算法代码

②测试类

4、Java语言实现---可比较类型数组版本

①Comparable接口

②算法代码

③测试代码

5、Java语言实现---任意可比较类型线性表容器版本

①算法代码

②测试代码

6、Java语言实现---双向排序版本

①算法代码

②测试类

三、冒泡排序——练习

1、从小到大排列

2、从大到小排列

3、测试

相关文章