算法工作原理
Chapter 3 Sorting Algorithms

第 3 章：排序算法

排序是重新排列一系列对象的过程,以使它们按某种逻辑顺序排列。例如,您的信用卡账单按日期顺序显示交易,您将书籍按作者和标题字母顺序排列在书架上。排序是计算机科学中的一个基本操作,在许多应用程序中起着关键作用。有各种经典的排序算法体现了不同的方法来解决这个问题。

在本章中,我们将考虑几种经典的排序方法和一种重要的数据结构,即优先级队列。我们首先讨论几种基本的排序方法,包括选择排序、插入排序和希尔排序。这些方法在许多应用程序中都很合适,但对于大规模问题,我们转向归并排序和快速排序,这两种递归排序算法可用于对大量项目进行排序。我们最后讨论优先级队列及其在排序和其他应用程序中的使用。

基本排序

最简单的排序算法执行以下操作:

  • 选择排序:找到最小的项目并与第一个条目交换,然后找到第二小的项目并与第二个条目交换,依此类推。
  • 插入排序:依次取出每个项目,并将其插入到已考虑的项目中的适当位置(保持它们有序)。

这些操作反映了人类通常执行排序任务的方式,对于小规模问题很有效。但是,它们不能很好地扩展,对于排序大型数组变得不切实际。

选择排序

选择排序是一种简单的排序算法,工作原理如下:首先,找到数组中最小的项目并与第一个条目交换(如果第一个条目已经是最小的,则与自身交换)。然后,找到下一个最小的项目并与第二个条目交换。继续这样做,直到整个数组排序完毕。

选择排序的内部循环这里是选择排序的 Java 实现:

public static void selectionSort(Comparable[] a) {
    int N = a.length;
    // 遍历数组从左到右
    for (int i = 0; i < N; i++) {
        // 找到未排序子数组中的最小元素的索引
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        // 将最小元素交换到正确的位置
        exch(a, i, min);
    }
}

选择排序使用大约 ~N^2/2 次比较和 N 次交换来对长度为 N 的数组进行排序。它的运行时间不受输入的影响 - 对于已经有序的数组或者所有元素都相等的数组来说,它的运行时间和随机排序的数组差不多。

插入排序

插入排序是另一种简单的排序算法,它通过逐步构建最终的有序数组来工作。与快速排序、堆排序或归并排序等更高级的算法相比,它在处理大型数组时效率较低,但也有一些优点:

  • 它对于小型数据集很高效。
  • 它在实践中比选择排序更高效。
  • 它是稳定的,即不会改变相等键元素的相对顺序。
  • 它是就地的,只需要 O(1) 的额外内存空间。
  • 它是在线的,即可以在接收列表的同时对其进行排序。

这里是插入排序的 Java 实现:

public static void insertionSort(Comparable[] a) {
    int N = a.length;
    // 从第二个元素开始遍历数组
    for (int i = 1; i < N; i++) {
        // 将当前元素插入到已排序的子数组中的正确位置
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

插入排序的内部循环将较大的元素向右移动一个位置,为当前元素腾出空间。插入排序的运行时间取决于输入项的初始顺序。例如,如果数组很大且其条目已经按顺序排列(或几乎按顺序排列),那么插入排序要快得多,比随机排序或逆序排列的情况快得多。

希尔排序

希尔排序是插入排序的一种简单扩展,通过允许交换相距较远的数组条目来提高速度,从而产生可以有效排序的部分有序数组,最终由插入排序完成。

其思想是重新排列数组,使其具有这样的属性:取每隔h个条目(从任何地方开始)可以得到一个有序的子序列。这样的数组被称为h-有序。换句话说,一个h-有序数组是h个独立的有序子序列,交织在一起。通过对某些较大的h值进行h-排序,我们可以在数组中移动项目很长的距离,从而使对较小的h值进行h-排序变得更容易。对任何以1结尾的h值序列使用这种过程都会产生一个有序的数组:这就是希尔排序。

以下是Java中希尔排序的实现:

public class MaxPQ<Key extends Comparable<Key>> {
    // 存储优先队列的数组
    private Key[] pq;
    // 优先队列中的元素个数
    private int N;
    
    public MaxPQ(int capacity) {
        // 初始化优先队列数组
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        // 判断优先队列是否为空
        return N == 0;
    }
   
    public void insert(Key key) {
        // 向优先队列中插入元素
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        // 删除并返回优先队列中的最大元素
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        // 上浮操作,将元素k上浮到合适的位置
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        // 下沉操作,将元素k下沉到合适的位置
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolea
```以下是该 Markdown 文件的中文翻译版本。对于代码部分,仅翻译注释,代码本身不进行翻译。
 
```java
n less(int i, int j) {
    return pq[i].compareTo(pq[j]) < 0;
}
 
private void exch(int i, int j) {
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}
}

这段代码使用一个数组 pq 来实现一个最大堆。insert() 和 delMax() 操作通过使用 swim() 和 sink() 辅助方法来维护堆的性质,通过交换父节点和子节点的值来恢复堆的顺序。

秒表

一个更有用的抽象数据类型是一个简单有效的秒表抽象,如下所示。要使用它,请在您想要启动计时器时创建一个 Stopwatch 对象,然后使用 elapsedTime() 方法获取对象创建以来经过的时间(以秒为单位)。该实现使用 Java 的 System.currentTimeMillis() 获取自 1970 年 1 月 1 日午夜以来的当前时间(以毫秒为单位)。

实例变量 start 记录了秒表创建的时间,elapsedTime() 使用 start 来计算经过的时间。显示的客户端代码是典型的:它执行一些计算,并使用 Stopwatch 来计时计算所需的时间。Stopwatch 数据类型是一个有效的抽象,因为它将秒表的概念(接口)与实现(使用 Java 的 System.currentTimeMillis())分离开来。这种接口和实现的分离是抽象数据类型的一个基本特征,我们将在本书的每个 ADT 中看到。

总结

抽象数据类型是面向对象编程中的一个essential元素,在现代编程中广泛使用。在本节中,我们已经看到:

  • 将抽象数据类型定义为一个 Java 类,使用实例变量来定义数据类型的值,并使用实例方法来实现对这些值的操作。
  • 开发同一 API 的多种实现,使用同一抽象数据类型的不同表示。以下是该 Markdown 文件的中文翻译。对于代码部分,我只翻译了注释,而没有翻译代码本身。

抽象数据类型

  • 区分抽象数据类型的 API、客户端和实现。
  • 设计抽象数据类型的 API。
  • 开发客户端和测试客户端,用于测试和调试。
  • 使用断言推理抽象数据类型实现的正确性。
  • 比较同一 API 的不同实现的性能。

这些活动是任何 Java 程序开发的essential部分。我们编写的每个 Java 程序都会涉及使用来自库的抽象数据类型;许多程序还会涉及开发新的抽象数据类型。在下一节中,我们将考虑三种基本的抽象数据类型,它们是大量程序的essential组件,在第 1.4 节中,我们将详细考虑分析实现性能特征的过程。

Chapter 2 Algorithms FundamentalsChapter 4 Searching Algorithms