《疯狂 Java 突破程序员基本功的 16 课》 读书笔记

/ JAVA / 0 条评论 / 460浏览

第 1 课 —— 数组与内存控制

数组初始化

数组初始化之后,该数组的长度是不可变的(可通过数组的 length 属性访问数组的长度)。Java 中的数组必须经过初始化(为数组对象的元素分配内存空间,并为每个数组元素指定初始值)才可使用。

数组初始化的形式:

使用数组

数组元素就是变量:例如 int[] 数组元素相当于 int 类型的变量

当通过索引来使用数组元素时(访问数组元素的值、为数组元素赋值),将该数组元素当成普通变量使用即可。

第 2 课 —— 对象与内存的控制

Java 内存管理分为:内存分配和内存回收。

  • 内存分配:创建 Java 对象时 JVM 为该对象在堆内存中所分配的内存空间。
  • 内存回收:当 Java 对象失去引用,变成垃圾,JVM 的垃圾回收机制自动清理该对象,并回收内存

实例变量 和 类变量

局部变量

特点:作用时间短,存储在方法的栈内存中

种类:

成员变量

类体内定义的变量,如果该成员变量没有使用 static 修饰,那该成员变量又被称为非静态变量或实例变量,如果使用 static 修饰,则该成员变量又可被称为静态变量或类变量。

实例变量和类变量的属性

使用 static 修饰的成员变量是类变量,属于该类本身,没有使用 static 修饰的成员变量是实例变量,属于该类的实例,在同一个类中,每一个类只对应一个 Class 对象,但每个类可以创建多个对象。

由于同一个 JVM 内的每个类只对应一个 CLass 对象,因此同一个 JVM 内的一个类的类变量只需要一块内存空间;但对于实例变量而言,该类每创建一次实例,就需要为该实例变量分配一块内存空间。也就是说,程序中创建了几个实例,实例变量就需要几块内存空间。

这里我想到一道面试题目:

public class A{
  {
    System.out.println("我是代码块");
  }
  static{
    System.out.println("我是静态代码块");
  }
  public static void main(String[] args) {
        A a = new A();
        A a1 = new A();
    }
}

结果:

我是静态代码块
我是代码块
我是代码块

静态代码块只执行一次,而代码块每创建一个实例,就会打印一次。

实例变量的初始化时机

程序可在3个地方对实例变量执行初始化:

上面第一种和第二种方式比第三种方式更早执行,但第一、二种方式的执行顺序与他们在源程序中的排列顺序相同。

同样在上面那个代码上加上一个变量 weight 的成员变量,我们来验证下上面的初始化顺序:

1、定义实例变量指定初始值非静态初始化块对实例变量指定初始值 之后:

public class A{
    {
        weight = 2.1;
        System.out.println("我是代码块");
    }
    double weight = 2.0;
    static{
        System.out.println("我是静态代码块");
    }
    public static void main(String[] args) {
        A a = new A();
        A a1 = new A();
        System.out.println(a.weight);
    }
}

结果是:

我是静态代码块
我是代码块
我是代码块
2.0

2、定义实例变量指定初始值非静态初始化块对实例变量指定初始值 之前:

public class A{
	double weight = 2.0;
    {
        weight = 2.1;
        System.out.println("我是代码块");
    }
    static{
        System.out.println("我是静态代码块");
    }
    public static void main(String[] args) {
        A a = new A();
        A a1 = new A();
        System.out.println(a.weight);
    }
}

结果为:

我是静态代码块
我是代码块
我是代码块
2.1

大家有没有觉得很奇怪?

我来好好说清楚下:

定义实例变量时指定的初始值、初始代码块中为实例变量指定初始值的语句的地位是平等的,当经过编译器处理后,他们都将会被提取到构造器中。也就是说,这条语句 double weight = 2.0; 实际上会被分成如下 2 次执行:

  • double weight; : 创建 Java 对象时系统根据该语句为该对象分配内存。
  • weight = 2.1; : 这条语句将会被提取到 Java 类的构造器中执行。

只说原理,大家肯定不怎么信,那么还有拿出源码来,这样才有信服能力的吗?是不?

这里我直接使用软件将代码的字节码文件反编译过来,看看里面是怎样的组成?

第一个代码的反编译源码如下:

public class A
{
  double weight;
  public A()
  {
    this.weight = 2.1D;
    System.out.println("我是代码块");
    this.weight = 2.0D;
  }
  static
  {
    System.out.println("我是静态代码块");
  }
  public static void main(String[] args)
  {
    A a = new A();
    A a1 = new A();
    System.out.println(a.weight);
  }
}

第二个代码反编译源码如下:

public class A
{
  double weight;
  public A()
  {
    this.weight = 2.0D;
    this.weight = 2.1D;
    System.out.println("我是代码块");
  }
  static
  {
    System.out.println("我是静态代码块");
  }
  public static void main(String[] args)
  {
    A a = new A();
    A a1 = new A();
    System.out.println(a.weight);
  }
}

这下子满意了吧!

通过反编译的源码可以看到该类定义的 weight 实例变量时不再有初始值,为 weight 指定初始值的代码也被提到了构造器中去了,但是我们也可以发现之前规则也是满足的。

他们的赋值语句都被合并到构造器中,在合并过程中,定义的变量语句转换得到的赋值语句,初始代码块中的语句都转换得到的赋值语句,总是位于构造器的所有语句之前,合并后,两种赋值语句的顺序也保持了它们在 Java 源代码中的顺序。

大致过程应该了解了吧?如果还不怎么清楚的,建议还是自己将怎个过程在自己的电脑上操作一遍,毕竟光看不练假把式。

类变量的初始化时机

JVM 对每一个 Java 类只初始化一次,因此 Java 程序每运行一次,系统只为类变量分配一次内存空间,执行一次初始化。程序可在两个地方对类变量执行初始化:

这两种方式的执行顺序与它们在源代码中的排列顺序相同。

还是用上面那个示例,我们在其基础上加个被 static 修饰的变量 height:

1、定义类变量时指定初始值静态初始化代码块中对类变量指定初始值 之后:

public class A{
    double weight = 2.0;
    {
        weight = 2.1;
        System.out.println("我是代码块");
    }
    static{
        height = 10.1;
        System.out.println("我是静态代码块");
    }
    static double height = 10.0;
    public static void main(String[] args) {
        A a = new A();
        A a1 = new A();
        System.out.println(a.weight);
        System.out.println(height);
    }
}

运行结果:

我是静态代码块
我是代码块
我是代码块
2.1
10.0

2、定义类变量时指定初始值静态初始化代码块中对类变量指定初始值 之前:

public class A{
    static double height = 10.0;
    double weight = 2.0;
    {
        weight = 2.1;
        System.out.println("我是代码块");
    }
    static{
        height = 10.1;
        System.out.println("我是静态代码块");
    }
    public static void main(String[] args) {
        A a = new A();
        A a1 = new A();
        System.out.println(a.weight);
        System.out.println(height);
    }
}

运行结果:

我是静态代码块
我是代码块
我是代码块
2.1
10.1

其运行结果正如我们预料,但是我们还是看看反编译后的代码吧!

第一种情况下反编译的代码:

public class A
{
  double weight;
  public A()
  {
    this.weight = 2.0D;

    this.weight = 2.1D;
    System.out.println("我是代码块");
  }
  static
  {
    System.out.println("我是静态代码块");
  }
  static double height = 10.0D;
  public static void main(String[] args)
  {
    A a = new A();
    A a1 = new A();
    System.out.println(a.weight);
    System.out.println(height);
  }
}

第二种情况下反编译的代码:

public class A
{
  static double height = 10.0D;
  double weight;
  public A()
  {
    this.weight = 2.0D;

    this.weight = 2.1D;
    System.out.println("我是代码块");
  }
  static
  {
    height = 10.1D;
    System.out.println("我是静态代码块");
  }
  public static void main(String[] args)
  {
    A a = new A();
    A a1 = new A();
    System.out.println(a.weight);
    System.out.println(height);
  }
}

通过反编译源码,可以看到第一种情况下(定义类变量时指定初始值静态初始化代码块中对类变量指定初始值 之后):

我们在 静态初始化代码块中对类变量指定初始值 已经不存在了,只有一个类变量指定的初始值 static double height = 10.0D; , 而在第二种情况下(定义类变量时指定初始值静态初始化代码块中对类变量指定初始值 之前)和之前的源代码顺序是一样的,没啥区别。

上面的代码中充分的展示了类变量的两种初始化方式 :每次运行该程序时,系统会为 A 类执行初始化,先为所有类变量分配内存空间,再按照源代码中的排列顺序执行静态初始代码块中所指定的初始值和定义类变量时所指定的初始值。

父类构造器

当创建任何 Java 对象时,程序总会先依次调用每个父类非静态初始化代码块、父类构造器(总是从 Object 开始)执行初始化,最后才调用本类的非静态初始化代码块、构造器执行初始化。

隐式调用和显示调用

当调用某个类的构造器来创建 Java 对象时,系统总会先调用父类的非静态初始化代码块进行初始化。这个调用是隐式执行的,而且父类的静态初始化代码块总是会被执行。接着会调用父类的一个或多个构造器执行初始化,这个调用既可以是通过 super 进行显示调用,也可以是隐式调用。

当所有父类的非静态初始代码块、构造器依次调用完成后,系统调用本类的非静态代码块、构造器执行初始化,最后返回本类的实例。至于调用父类的哪个构造器执行初始化,分以下几种情况:

注:super 和 this 必须在构造器的第一行,且不能同时存在。

推荐一篇博客:Java初始化顺序 文章从无继承和继承两种情况下分析了 Java 初始化的顺序。

访问子类对象的实例变量

调用被子类重写的方法

父子实例的内存控制

继承成员变量和继承方法的区别

方法的行为总是表现出它们实际类型的行为;实例变量的值总是表现出声明这些变量所用类型的行为。

内存中的子类实例

父、子类的类变量

final 修饰符

final 可以修饰变量、方法、类。

final 修饰的实例变量只能在如下位置指定初始值:

final 修饰的类变量只能在如下位置指定初始值:

第 3 课 —— 常见 Java 集合的实现细节

Java 集合框架类图:

Set 和 Map

Set 代表一种集合元素无序、集合元素不可重复的集合,Map 则代表一种由多个 key-value 对组合的集合,Map 集合类似于传统的关联数组。

Set 和 Map 的关系

1、Map 集合中的 key 不能重复且没有顺序。将这些 key 组合起来就是一个 Set 集合。所以有一个 Set<k> keySet() 方法来返回所有 key 组成的 Set 集合。

2、Set 也可以转换成 Map。(在 Set 中将 每一对 key 和 value 存放在一起)

HashMap 和 HashSet

HashSet:系统采用 Hash 算法决定集合元素的存储位置。(基于 HashMap 实现的)

HashMap:系统将 value 当成 key 的附属,系统根据 Hash 算法决定 key 的存储位置。

HashSet 的绝大部分方法都是通过调用 HashMap 的方法实现的,因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。

TreeMap 和 TreeSet

TreeSet 底层使用 TreeMap 来包含 Set 集合中的所有元素。

TreeMap 采用的是一种“红黑树”的排序二叉树来保存 Map 中每个 Entry —— 每个 Entry 都被当成 “红黑树” 的一个节点对待。

Map 和 List

Map 的 values() 方法

不管是 HashMap 还是 TreeMap ,它们的 values() 方法都可以返回其所有 value 组成的 Collection 集合,其实是一个不存储元素的 Collection 集合,当程序遍历 Collection 集合时,实际上就是遍历 Map 对象的 value。

HashMap 和 TreeMap 的 values() 方法并未把 Map 中的 values 重新组合成一个包含元素的集合对象,这样就可以降低系统内存开销。

Map 和 List 的关系

底层实现很相似;用法上很相似。

ArrayList 和 LinkedList

List 集合的实现类,主要有 ArrayList 、Vector 和 LinkedList。

Vector 和 ArrayList 在更多元素添加进来时会请求更大的空间。Vector 每次请求其大小的双倍空间,而 ArrayList每次对 size 增长 50%.

而 LinkedList 还实现了 Queue 接口, 该接口比 List 提供了更多的方法,包括 offer(), peek(), poll()等.

注意: 默认情况下 ArrayList 的初始容量非常小, 所以如果可以预估数据量的话, 分配一个较大的初始值属于最佳实践, 这样可以减少调整大小的开销。

ArrayList与LinkedList性能对比

时间复杂度对比如下:

LinkedList 更适用于:

Iterator 迭代器

是一个迭代器接口,专门用于迭代各种 Collection 集合,包括 Set 集合和 List 集合。

第 4 课 —— Java 的内存回收

Java 引用的种类

对象在内存中的状态

JVM 垃圾回收机制,是否回收一个对象的标准在于:是否还有引用变量引用该对象?只要有引用变量引用该对象,垃圾回收机制就不会回收它。

Java 语言对对象的引用有:

强引用

程序创建一个对象,并把这个对象赋给一个引用变量,这个引用变量就是强引用。当一个对象被一个或者一个以上的强引用变量所引用时,它处于可达状态,它是不会被系统的垃圾回收机制回收。

软引用

软引用需要通过 SoftReference 类来实现,当一个对象只具有软引用时,它有可能会被垃圾回收机制回收。对于只有软引用的对象而言,当系统内存空间足够时,它不会被系统回收,程序也可使用该对象;当系统内存空间不足时,系统将会回收它。

弱引用

弱引用和软引用有点相似,区别在于弱引用所引用对象的生存期更短。

虚引用

虚引用主要用于跟踪对象被垃圾回收的状态,虚引用不能单独使用,虚引用必须和引用队列联合使用。

Java 的内存泄漏

ArrayList.java 中的 remove 方法

public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
    }

其中 elementData[--size] = null; // clear to let GC do its work 语句是清除数组元素的引用,避免内存的泄漏,如果没有这句的话,那么就是只有两个作用:

垃圾回收机制

垃圾回收的基本算法

对于一个垃圾回收器的设计算法来说,大概有如下几个设计:

堆内存的分代回收

1、Young 代

2、Old 代

3、Permanent 代

内存管理小技巧

第 5 课 —— 表达式中的陷阱

关于字符串的陷阱

JVM 对字符串的处理

String java = new String("Java") 这句创建了两个字符串对象,一个是 “Java” 这个直接量对应的字符串对象,另外一个是 new String() 构造器返回的字符串对象。

Java 程序中创建对象的方法:

对于 Java 程序的字符直接量,JVM 会使用一个字符串池来保护它们;当第一次使用某个字符串直接量时,JVM 会将它放入字符串池进行缓存。在一般的情况下,字符串池中的字符串对象不会被垃圾回收器回收,当程序再次需要使用该字符串时,无需重新创建一个新的字符串,而是直接让引用变量指向字符串池中已有的字符串。

不可变的字符串

String 类是一个不可变类,当一个 String 对象创建完成后,该 String 类里包含的字符序列就被固定下来,以后永远不能修改。

如果程序需要一个字符序列会发生改变的字符串,那么建议使用 StringBuilder (效率比 StringBuffer 高)

字符串比较

如果要比较两个字符串是否相同,用 == 进行判断就行,但如果要判断两个字符串所包含的字符序列是否相同,则应该用 String 重写过的 equals() 方法进行比较。

public boolean equals(Object anObject) {
        //如果两个字符串相同
        if (this == anObject) {
            return true;
        }
        //如果anObject是String类型
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            //n代表字符串的长度
            int n = value.length;
            //如果两个字符串长度相等
            if (n == anotherString.value.length) {
                //获取当前字符串、anotherString底层封装的字符数组
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                //逐一比较v1 和 v2数组中的每个字符
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

还可以使用 String 提供的 compareTo() 方法返回两个字符串的大小

public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

表达式类型的陷阱

表达式类型的自动提升

复合赋值运算符的陷阱

Java 语言允许所有的双目运算符和 = 一起结合组成复合赋值运算符,如 +=、-=、*=、/=、%= 、&= 等,复合赋值运算符包含了一个隐式的类型转换。

//下面这两条语句不等价
a = a + 5;		//
a += 5;			//实际上等价于 a = (a的类型) (a + 5);

复合赋值运算符会自动的将它计算的结果值强制转换为其左侧变量的类型。

输入法导致的陷阱

注释的字符必须合法

转义字符的陷阱

泛型可能引起的错误

原始类型变量的赋值

原始类型带来的擦除

当把一个具有泛型信息的对象赋给另一个没有泛型信息的变量时,所有在尖括号之间的类型信息都会丢弃。

创建泛型数组的陷阱

Java 中不允许创建泛型数组

正则表达式的陷阱

有些符号本身就是正则表达式,我们需要对符号做转义运算。

多线程的陷阱

不要调用 run 方法

开启线程是用 start() 方法,而不是 run() 方法。

静态的同步方法

对于同步代码块而言,程序必须显式为它指定同步监视器;对于同步非静态方法而言,该方法的同步监视器是 this —— 即调用该方法的 Java 对象;对于静态的同步方法而言,该方法的同步监视器不是 this,而是该类本身。

第 6 课 —— 流程控制的陷阱

switch 语句陷阱

break 语句不要忘记写

switch 的表达式类型:

标签引起的陷阱

Java 中的标签通常是和循环中的 break 和 continue 结合使用,让 break 直接终止标签所标识的循环,让 continue 语句忽略标签所标识的循环的剩下语句。

。。

第 7 课 —— 面向对象的陷阱

instanceof 运算符的陷阱

instanceof 它用于判断前面的对象是否是后面的类或其子类、实现类的实例。如果是返回 true,否则返回 false。

instanceof 运算符前面操作数的编译时类型必须是:

构造器陷阱

构造器是 Java 中每个类都会提供的一个“特殊方法”。构造器负责对 Java 对象执行初始化操作,不管是定义实例变量时指定的初始值,还是在非静态初始化代码块中所做的操作,实际上都会被提取到构造器中执行。

构造器不能声明返回值类型,也不能使用void声明构造器没有返回值。

构造器创建对象吗

构造器并不会创建 Java 对象,构造器只是负责执行初始化,在构造器执行之前,Java 对象所需要的内存空间,是由 new 关键字申请出来的。绝大部分时候,程序使用 new 关键字为一个 Java 对象申请空间之后,都需要使用构造器为这个对象执行初始化,但在某些时候,程序创建 Java 对象无需调用构造器,如下:

package com.zhisheng.test;

import java.io.*;

/**
 * Created by 10412 on 2017/5/31.
 */
class Wolf implements Serializable
{
    private String name;

    public Wolf(String name) {
        System.out.println("调用了有参构造方法");
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Wolf wolf = (Wolf) o;

        return name != null ? name.equals(wolf.name) : wolf.name == null;

    }

    @Override
    public int hashCode() {
        return name != null ? name.hashCode() : 0;
    }
}

public class SerializableTest
{
    public static void main(String[] args) {
        Wolf w = new Wolf("灰太狼");
        System.out.println("对象创建完成");
        Wolf w2 = null;
        ObjectInputStream ois = null;
        ObjectOutputStream oos = null;
        try {
            //创建输出对象流
            oos = new ObjectOutputStream(new FileOutputStream("a.bin"));
            //创建输入对象流
            ois = new ObjectInputStream(new FileInputStream("a.bin"));
            //序列输出java 对象
            oos.writeObject(w);
            oos.flush();
            //反序列化恢复java对象
            w2 = (Wolf) ois.readObject();
            System.out.println(w);
            System.out.println(w2);
            //两个对象的实例变量值完全相等,输出true
            System.out.println(w.equals(w2));
            //两个对象不同,输出false
            System.out.println(w == w2);
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }finally {
            if (ois!=null)
                try {
                    ois.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            if (oos!=null)
                try {
                    oos.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
        }

    }
}

程序运行结果:

调用了有参构造方法
对象创建完成
com.zhisheng.test.Wolf@1b15382
com.zhisheng.test.Wolf@1b15382
true
false

正如结果所示:创建 Wolf 对象时,程序调用了相应的构造器来对该对象执行初始化;当程序通过反序列化机制恢复 Java 对象时,系统无需在调用构造器来进行初始化。通过反序列化恢复出来的 Wolf 对象和原来的 Wolf 对象具有完全相同的实例变量值,但系统会产生两个对象。

无限递归构造器

public class ConstrutionTest
{
    ConstrutionTest ct;
    {
        ct = new ConstrutionTest();
    }
    public ConstrutionTest() {
        System.out.println("无参构造器");
    }
    public static void main(String[] args) {
        ConstrutionTest ct = new ConstrutionTest();
    }
}

运行结果抛出异常 java.lang.StackOverflowError

因为不管定义实例变量时指定的初始值,还是在非静态初始化代码块中执行的初始化操作,最终都将提取到构造器中执行,因为代码中递归调用了类的构造器,最终导致出现 java.lang.StackOverflowError 异常。

到底调用哪个重载方法

1、第一阶段 JVM 将会选取所有可获得并匹配调用的方法或者构造器

2、第二个阶段决定到底要调用哪个方法,此时 JVM 会在第一阶段所选取的方法或者构造器中再次选取最精确匹配的那一个。

public class OverrideTest
{
    public void info(Object obj, int a) {
        System.out.println("obj 参数" + obj);
        System.out.println("整型参数 " + a);
    }

    public void info(Object[] obj, double a) {
        System.out.println("obj 参数" + obj);
        System.out.println("整型参数 " + a);
    }

    public static void main(String[] args) {
        OverrideTest o = new OverrideTest();
        o.info(null, 5);
    }
}

报错如下:

Error:(20, 10) java: 对info的引用不明确
  com.zhisheng.test.OverrideTest 中的方法 info(java.lang.Object,int) 和 com.zhisheng.test.OverrideTest 中的方法 info(java.lang.Object[],double) 都匹配

在这种复杂的条件下,JVM 无法判断哪个方法更匹配实际调用,将会导致程序编译错误。

方法重写的陷阱

无法重写父类 private 方法。如果子类有一个与父类 private 方法具有相同方法名、相同形参列表、相同返回值类型的方法,依然不是重写,只是子类定义了一个与父类相同的方法。

static 关键字

static 可以修饰类中定义的成员:field、方法、内部类、初始化代码块、内部枚举类

静态方法属于类

被 static 修饰的成员(field、方法、内部类、初始化块、内部枚举类)属于类本身,而不是单个的 Java 对象。静态方法也是属于类。

第 8 课 —— 异常捕捉的陷阱

正确关闭资源的方式

finally 块陷阱

finally 执行顺序,看我以前写的一篇文章《深度探究Java 中 finally 语句块》

catch 块用法

在 try 块后使用 catch 块来捕获多个异常时,程序应该小心多个 catch 块之间的顺序:捕获父类异常的 catch 块都应该排在捕获子类异常的 catch 块之后(先处理小异常,再处理大异常),否则出现编译错误。

继承得到的异常

子类重写父类方法时,不能声明抛出比父类方法类型更多、范围更大的异常。

二叉树性质:

选择排序

直接选择排序

需要经过 n - 1 趟比较

第一趟比较:程序将记录定位在第一个数据上,拿第一个数据依次和它后面的每个数据进行比较,如果第一个数据大于后面某个数据,交换它们。。依此类推,经过第一趟比较,这组数据中最小的数据被选出来,它被排在第一位。

第二趟比较:程序将记录定位在第二个数据上,拿第二个数据依次和它后面每个数据进行比较,如果第二个数据大于后面某个数据,交换它们。。依次类推,经过第二趟比较,这组数据中第二小的数据被选出,它排在第二位

。。

按此规则一共进行 n-1 趟比较,这组数据中第 n - 1小(第二大)的数据被选出,被排在第 n -1 位(倒数第一位);剩下的就是最大的数据,它排在最后。

直接选择排序的优点就是算法简单,容易实现,缺点就是每趟只能确定一个元素,n个数组需要进行 n-1 趟比较。

堆排序

交换排序

冒泡排序

第一趟:依次比较0和1,1和2,2和3 ... n-2 和 n - 1 索引的元素,如果发现第一个数据大于后一个数据,交换它们,经过第一趟,最大的元素排到了最后。

第二趟:依次比较0和1,1和2,2和3 ... n-3 和 n - 2 索引的元素,如果发现第一个数据大于后一个数据,交换它们,经过第二趟,第二大的元素排到了倒数第二位

。。

第 n -1 趟:依次比较0和1元素,如果发现第一个数据大于后一个数据,交换它们,经过第 n - 1 趟,第二小的元素排到了第二位。

快速排序

从待排的数据序列中任取一个数据作为分界值,所有比它小的数据元素一律放在左边,所有比他大的元素一律放在右边,这样一趟下来,该序列就分成了两个子序列,接下来对两个子序列进行递归,直到每个子序列只剩一个,排序完成。

插入排序

直接插入排序

依次将待排序的数据元素按其关键字值的大小插入前面的有序序列。

折半插入排序

当第 i - 1 趟需要将第 i 个元素插入前面的 0 ~ i -1 个元素序列中时: