Java教程
算法基础二：渐增型算法---插入排序
本文主要是介绍算法基础二：渐增型算法---插入排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
算法基础二：渐增型算法---插入排序
一、渐增型算法是什么
渐增型算法（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();
}
}
这篇关于算法基础二：渐增型算法---插入排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Java管理系统项目实战入门教程11-02
-
Java监控系统项目实战教程11-02
-
Java就业项目项目实战：从入门到初级工程师的必备技能11-02
-
Java全端项目实战入门教程11-02
-
Java全栈项目实战：从入门到初级应用11-02
-
Java日志系统项目实战：初学者完全指南11-02
-
Java微服务系统项目实战入门教程11-02
-
Java微服务项目实战：新手入门指南11-02
-
Java项目实战：新手入门教程11-02
-
Java小程序项目实战：从入门到简单应用11-02
-
Java支付系统项目实战入门教程11-02
-
SpringCloud Alibaba项目实战：新手入门教程11-02
-
Swagger项目实战：新手入门教程11-02
-
UNI-APP项目实战：新手入门与初级教程11-02
-
编译部署资料入门教程：一步步学会编译和部署11-02
栏目导航
