排序算法——基于比较的算法

Algorithm

基础排序算法涉及到选择（冒泡）排序、插入排序、希尔排序、归并排序、快速排序、堆排序、优先队列，这几种算法分别拥有不同的特点及实现，下面就简单介绍一下。

公共方法

在统一介绍之前，利用Java特性，这里先抽象出几个公共的方法特性。另外，所有元素都实现了Comparable接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
abstract class BaseSort {
       public abstract void sort(Comparable[] a);

       protected boolean less(Comparable[] a, int i, int j) {
           return a[i].compareTo(a[j]) < 0;
       }

       protected void exchange(Comparable[] a, int i, int j) {
           Comparable temp =a[i];
           a[i] = a[j];
           a[j] = temp;
       }
   }

选择排序

选择排序是对冒泡排序的一种改进，减少了交换次数。以从小到大的排序为例，从第一位开始，依次向后遍历并将剩余数组中最小的元素交换到遍历的起点。

  • 从起点遍历，依次减小遍历范围
  • 找出遍历的剩余数组中的最小值
  • 与遍历起点交换
1
2
3
4
5
6
7
8
9
10
11
12
class SelectionSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++)
                if (less(a, j, min)) min = j;
            exchange(a, i, min);
        }
    }
}

性能：比较 N^2/2 + 交换 3/2 N，最差情况N^2级别

插入排序

插入排序可以理解为打扑克牌时的动作，将牌插入手中牌堆合适的位置。

以从小到大的排序为例，如果此时插入的牌在手牌中第一次找到了比他小的牌，那么此时位置确定，因为前面的牌都比要插入的小，且已排好顺序。

  • 第一位不用排序
  • 第二位开始与前面的元素进行比较
  • 若比他前一位小，则交换位置
  • 找到第一个比他小的，即确定位置
  • 遍历直至最后
1
2
3
4
5
6
7
8
9
class InsertionSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            for (int j = i; j > 0 && less(a, j, j - 1); j--)
                exchange(a, j, j - 1);
    }
}

性能：比较 N^2/4 + 交换 N^2/4 ，最差情况N^2级别

希尔排序

插入排序面对数据量较小时还可以，但是对于数据偏大则有些力不从心了。希尔排序是针对插入排序的一种优化切分算法，采用分治思想。时间复杂度突破了N^2级别，但是空间复杂度却能保持O (1)。而快速排序算法采用的辅助栈则在空间上无法比拟希尔排序。

  • 先将序列分成较多个子序列分别进行排序，再分成较少个子序列分别进行排序，直到最后为一个序列排序
  • 子序列的排序使用插入排序

这里的子序列是通过增量h来分割的，每隔h位形成一个有序的子序列。这里采用1/3切分，性能较好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class ShellSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        int h = 1;
        while (h < a.length / 3) h = h * 3 + 1;
        while (h >= 1) {
            for (int i = h; i < a.length; i++)
                for (int j = i; j > h && less(a, j, j - h); j -= h)
                    exchange(a, j, j - h);
            h /= 3;
        }
    }
}

性能：在 NlogN 和 N^2 之间。

归并排序

归并排序是典型的分治思想算法，通过将数组分为各个小数组并排序后合并实现有序。

由于归并排序总是将数组分为2个子数组，所以，在算法执行的过程中可以将其排序视作二叉树，其算法所需的复杂度也在NlogN级别。

合并

合并是将两个有序的数组合并成一个有序的大数组，这是归并排序的基石。

借助辅助数组aux[]，将原数组复制到aux[]中，然后依次复制回原数组中，将a[lo...mid]和a[mid+1...hi]归并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
abstract class MergeSort extends BaseSort {
    protected Comparable[] aux;

    protected void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for (int k = lo; k < hi; k++)
            aux[k] = a[k];
        for (int k = lo; k <= hi; k++)
            if (j > hi) a[k] = aux[i++];
            else if (i > mid) a[k] = aux[j++];
            else if (less(a, j, i)) a[k] = aux[j++];
            else a[k] = aux[i++];
    }
}

自顶向下的归并

对于一个大数组，自然而然的可以考虑使用将其分为两个小数组进行排序然后归并，子数组再次分裂……直至只有两个元素的子数组，此时开始收敛，向上归并。

  • 化整为零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MergeUBSort extends MergeSort {

    @Override
    public void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) >>> 1;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }
}

对于小规模的子数组可以采用插入排序进行优化，一般可以提高10%左右的性能。

同时也可以不将元素复制到辅助数组，减少复制到辅助数组的时间开销，但是空间无法减小，这也是归并排序的缺陷之一。

性能：1/2NlogN~NlogN

自底向上的归并排序

在分治思想中，我们处理的问题大多都由大问题转化为小问题，故干脆可以直接从小问题处理入手，转而合并为大问题。

  • 循序渐进
1
2
3
4
5
6
7
8
9
10
class MergeBUSort extends MergeSort {

    @Override
    public void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        for (int sz = 1; sz < a.length; sz += sz)
            for (int lo = 0; lo < a.length - sz; lo += sz + sz)
                merge(a, lo, lo + sz - 1, Math.min(a.length - 1, lo + sz + sz - 1));
    }
}

上述代码进行logN次的两两归并。

性能：1/2NlogN~NlogN。

  • 自底向上在数组大小为2的幂时，与自顶向下性能一样，只是访问顺序不同。
  • 自底向上更适合使用链表作为数据结构排序。

快速排序

快速排序利用分治思想，将首位作为标杆，将比他小的放在左边，比他大的放在右边。然后再对两个子数组进行排序。

最终

这里采用指针探测法实现。

切分 partition

1
2
3
4
5
6
7
8
9
10
11
private int partition(Comparable[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    while (true) {
        while (less(a, ++i, lo)) if (i == hi) break;
        while (less(a, lo, --j)) if (j == lo) break;//可不必判断
        if (i >= j) break;
        exchange(a, i, j);
    }
    exchange(a, lo, j);
    return j;
}
  • 使用头尾两个指针i和j，以数组第一位元素v为标杆。
  • 若i比v小，则继续遍历，直至比v大停止。
  • 若j比v大，则继续遍历，直至比v小停止。
  • 交换i和j。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class QuickSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi) {
        ···
    }
}

性能：一般情况 NlogN ，最差情况N^2级别。

快速排序优化

快速排序在重复数据较小或随机排列数据较多时性能比较好，若在重复数据多，则此时最差情况可达到N^2级别。为此，针对快速排序的优化算法也是十分重要的一点。

小数组使用插入排序

插入排序在小数组时性能不错，而对于快排来说，小数组的性能反而不佳。对于小数组的界定一般在5~15之间，具体依据操作系统优化而定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class QuickSort extends BaseSort {

 private static final int MAX = 10;//5~15依据操作系统而定

    ···
    private void sort(Comparable[] a, int lo, int hi) {
        if (hi >= lo + MAX) {
         new InsertionSort.sort(a, lo, hi);//转向插入排序
         return;
        }
        ···
    }
    ···
}
三向切分优化重复数组的性能

维护lt和gt两个指针，从左右向中心遍历，维护切分区域。通过与i遍历指针交换，使得lolt < ltgt < gt~hi。对于大量重复的数组，此种方法可以减少大量的交换开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Quick3WaySort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) return;
        int lt = lo, gt = hi, i = lt + 1;
        while (i <= gt) {
            int comp = a[i].compareTo(a[lo]);
            if (comp < 0) exchange(a, i++, lt++);
            else if (comp > 0) exchange(a, i, gt--);
            else i++;
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }
}

当然三向切分也可以使用插入排序优化性能。

性能：在大小为N，主键值出现的频率为H，性能为**~NH。
**在重复键值较多的情况下，可以将性能由N^2优化至N级别。

堆排序

堆排序的实现基础是在二叉堆上完成的。

二叉堆

二叉堆是一种完全（或近似）二叉树。其两个子结点一定大于（小于）或等于父结点。大于或小于取决于是最大堆还是最小堆。

  • 在一个父节点为k的位置，其子结点为2k 和2k+1。

利用这个性质，在二叉堆中上下移动只需要将k/2或k=2*k即可。

二叉堆结构

这里的实现我们是以数组为基础的数据结构实现的。

因为无法完成上下移动，所以数组第0个位置是不存放数据以及使用的！

在之后的操作中，我们以最大堆为例子。（最小堆仅仅是比较大小的方向不同）

堆的基础算法

在对堆进行添加删除操作时，需要对堆进行恢复，此时需要借助两个辅助操作。

  • 如果此时某个结点的优先级上升，则此时需要从下至上恢复堆——上浮 swim
  • 如果此时某个结点的优先级下降，则此时需要从上至下恢复堆——下沉 sink
上浮 swim

如果某个子结点比其父结点优先级更高，则此时需要子结点中优先级最高的与其父结点交换，进行上浮，直至到合适位置（堆顶或不再更大）。

1
2
3
4
5
6
private void swim(Comparable[] a, int k) {
    while (k > 1 && less(a, k / 2, k)) {
        exchange(a, k / 2, k);
        k /= 2;
    }
}
下沉 sink

如果某个父结点比其子结点优先级更低，则此时需要父结点与子节点中优先级最高的交换，进行下沉，直至到合适位置（堆底部或不再更小）。

1
2
3
4
5
6
7
8
private void sink(Comparable[] a, int k) {
    while (k * 2 <= a.length - 1) {
        int j = k * 2;
        if (j < a.length - 1 && less(a, j, j + 1)) j++;
        if (!less(a, k, j)) break;
        k = j;
    }
}

堆排序实现

堆排序的实现分为两步：

  • 构造堆序列
  • 通过下沉操作不断的返回堆顶值（最大/小值）至数组末尾，形成有序数列。

给定一个数组，将其排序为堆排序，则是构造堆。
此过程中，可以用上浮和下沉实现。但是下沉操作仅需2N次比较以及小于N次交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MaxHeapSort extends BaseSort {

    @Override
    public void sort(Comparable[] a) {
        int N = a.length;
        for (int k = N / 2; k >= 1; k--)
            sink(a, k);
        while (N > 1) {
            exchange(a, 1, N--);
            sink(a, 1);
        }
    }

    private void swim(Comparable[] a, int k) {
        ···
    }

    private void sink(Comparable[] a, int k) {
        ···
    }
}

性能：堆排序可以达到稳定的NlogN开销和恒定的额外空间。
劣势：对于一些空间紧张的情况而言，可以很简洁的实现较好的性能。但是在现代操作系统中使用较少，因为其无法利用缓存。这是其相对于快速排序、希尔排序、归并排序的劣势。
通过堆实现的优先队列非常重要，因为其能很好的将插入和删除最大（最小）元素的操作保证对数级开销。

可以通过先下沉后上浮的方式，优化算法，减少接近一半的比较次数，但是会损失额外的空间。

优先队列

优先队列是基于堆的完全二叉树表示

其将数据存储于pq[1...N]中，pq[0]未使用。

  • 构造器可以传入数组或Collection作为参数，只需将其按照堆构造方法自底向上依次进行下沉即可。

基础方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//表示优先级更高的比较，这里允许传入自定义的比较器修改优先级，默认最小优先队列
      private boolean greater(int i, int j) {
          if (comparator == null) return pq[i].compareTo(pq[j]) < 0;
          return comparator.compare(pq[i], pq[j]) < 0;
      }

      private void exchange(int i, int j) {
          Key temp = pq[i];
          pq[i] = pq[j];
          pq[j] = temp;
      }
      
      private void resize(int capacity) {
          Key[] copy = (Key[]) new Object[capacity];
          for (int i = 1; i <= N; i++) {
              copy[i] = pq[i];
          }
          pq = copy;
      }

同样排序也需要下沉和上浮的操作进行辅助。实现和堆排序中类似，键值key实现了Comparable接口，使用一个pq数组维护，N表示真实数组填充的数据。

上浮 swim

1
2
3
4
5
6
private void swim(int k) {
    while (k > 1 && greater(k, k / 2)) {
        exchange(k, k / 2);
        k /= 2;
    }
}

下沉 sink

1
2
3
4
5
6
7
8
9
private void sink(int k) {
    while (k * 2 >= N) {
        int j = k * 2;
        if (j < N - 1 && greater(j + 1, j)) j++;
        if (!greater(j, k)) break;
        exchange(k, j);
        k = j;
    }
}

添加 insert

只需将要添加的元素放入队尾，然后上浮到合适位置即可。

1
2
3
4
5
public void insert(Key key) {
    if (N == pq.length - 1) resize(pq.length * 2);
    pq[++N] = key;
    swim(N);
}

删除最小值（优先级最高）

将队列的最小值即数组的第1位返回，并与最后一位交换（置空），将新的首位元素下沉至合适位置。

1
2
3
4
5
6
7
8
public Key deletMin() {
    Key min = pq[1];
    exchange(1, N--);
    sink(1);
    pq[N + 1] = null;
    if (N == (pq.length - 1) / 4) resize(pq.length / 2);
    return min;
}

完整代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class PriorityQueue<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    private Comparator<? super Key> comparator;

    public PriorityQueue() {
        this(10);
    }

    public PriorityQueue(int maxN) {
        N = 0;
        pq = (Key[]) new Object[maxN + 1];
    }

    public PriorityQueue(Comparator<? super Key> comparator) {
        this(10, comparator);
    }

    public PriorityQueue(int maxN, Comparator<? super Key> comparator) {
        this(maxN);
        this.comparator = comparator;
    }

    public void setComparator(Comparator<? super Key> comparator) {
        this.comparator = comparator;
    }

    public void insert(Key key) {
        if (N == pq.length - 1) resize(pq.length * 2);
        pq[++N] = key;
        swim(N);
    }

    public Key deletMin() {
        Key min = pq[1];
        exchange(1, N--);
        sink(1);
        pq[N + 1] = null;
        if (N == (pq.length - 1) / 4) resize(pq.length / 2);
        return min;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private void swim(int k) {
        while (k > 1 && greater(k, k / 2)) {
            exchange(k, k / 2);
            k /= 2;
        }
    }

    private void sink(int k) {
        while (k * 2 >= N) {
            int j = k * 2;
            if (j < N - 1 && greater(j + 1, j)) j++;
            if (!greater(j, k)) break;
            exchange(k, j);
            k = j;
        }
    }

    private boolean greater(int i, int j) {
        if (comparator == null) return pq[i].compareTo(pq[j]) < 0;
        return comparator.compare(pq[i], pq[j]) < 0;
    }

    private void exchange(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private void resize(int capacity) {
        Key[] copy = (Key[]) new Object[capacity];
        for (int i = 1; i <= N; i++) {
            copy[i] = pq[i];
        }
        pq = copy;
    }
}

性能

  • 增加、删除操作均在logN级别内。

索引优先队列

在实现优先队列的基础之上，可以额外维护一个逆序数组qp[]使其能快速访问队列中任意元素（键值key）。

其中qp[pq[i]] = pq[qp[i]] = key。

为了能够快速找到pq[]中元素值对应的下标，我们需要额外设置一个数组qp[]，它的作用是存储与对象相关的整数在pq[]数组中的下标，并在上浮和下沉的过程中同时维护它。

索引优先队列结构

初始化

与优先队列不同的是，这里采用整数数组pq[]维护索引下标以及其堆的顺序，用pq[]维护元素与索引对应的位置关系，用额外的keys[]维护元素队列，keys中的数据位置不做改变。

  • 将qp[]初始化为-1，可以快速判断某位置是否包含元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class IndexPriorityQueue<Key extends Comparable<Key>> {
        private int[] pq;
        private int[] qp;
        private Key[] keys;
        private int N;
        private Comparator<? super Key> comparator;

        public IndexPriorityQueue(int maxN) {
            N = 0;
            pq = new int[maxN + 1];
            qp = new int[maxN + 1];
            keys = (Key[]) new Object[maxN + 1];
	        for (int i = 0; i < pq.length; i++) {
	            pq[i] = -1;
	            qp[i] = -1;
	        }
        }

        private boolean greater(int i, int j) {
            if (comparator == null) return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
            return comparator.compare(keys[pq[i]], keys[pq[j]]) < 0;
        }

        private void exchange(int i, int j) {
            int temp = pq[i];
            pq[i] = pq[j];
            pq[j] = temp;
            qp[pq[i]] = i;
            qp[pq[j]] = j;
        }

        public boolean contains(int k) {
            return qp[k] != -1;
        }
        ···
    }

上浮和下沉

上浮和下沉操作与优先队列相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void swim(int k) {
    while (k > 1 && greater(k, k / 2)) {
        exchange(k, k / 2);
        k /= 2;
    }
}

private void sink(int k) {
    while (k * 2 >= N) {
        int j = k * 2;
        if (j < N - 1 && greater(j + 1, j)) j++;
        if (!greater(j, k)) break;
        exchange(k, j);
        k = j;
    }
}

改变 change

改变优先队列中索引的值。（注意keys中的数据位置并未改变）

1
2
3
4
5
6
public void change(int k, Key key) {
    if (!contains(k)) return;
    keys[k] = key;
    swim(qp[k]);
    sink(qp[k]);
}

插入 insert

插入数据的同时，要维护qp[]数组。

1
2
3
4
5
6
7
8
9
10
public void insert(int k, Key key) {
    if (contains(k)) change(k, key);
    else {
        ++N;
        pq[N] = k;
        pq[k] = N;
        keys[k] = key;
        swim(k);
    }
}

最小值 min

1
2
3
public Key min() {
    return keys[pq[1]];
}

删除最小值并返回索引（优先级最高）

1
2
3
4
5
6
7
8
9
10
11
12
13
public int deletMin() {
    if (isEmpty()) throw new NoSuchElementException();
    int min = pq[1];
    exchange(1, N--);
    sink(1);

    assert min== pq[N+1];

    pq[N + 1] = -1;
    qp[min] = -1;
    keys[min] = null;
    return min;
}

删除 delete

1
2
3
4
5
6
7
8
9
10
11
12
public Key delete(int k) {
    if (!contains(k)) return null;
    int index = qp[k];
    Key del = keys[k];
    exchange(index, N--);
    swim(index);
    sink(index);
    pq[N + 1] = -1;
    qp[k] = -1;
    keys[k] = null;
    return del;
}

完整代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
class IndexPriorityQueue<Key extends Comparable<Key>> implements Iterable<Integer> {
    private int[] pq;
    private int[] qp;
    private Key[] keys;
    private int N;
    private Comparator<? super Key> comparator;

    public IndexPriorityQueue() {
        this(10);
    }

    public IndexPriorityQueue(int maxN) {
        N = 0;
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];
        keys = (Key[]) new Object[maxN + 1];
        for (int i = 0; i < qp.length; i++) qp[i] = -1;
    }

    public IndexPriorityQueue(Comparator<? super Key> comparator) {
        this(10, comparator);
    }

    public IndexPriorityQueue(int maxN, Comparator<? super Key> comparator) {
        this(maxN);
        this.comparator = comparator;
    }

    public void setComparator(Comparator<? super Key> comparator) {
        this.comparator = comparator;
    }

    private boolean greater(int i, int j) {
        if (comparator == null) return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
        return comparator.compare(keys[pq[i]], keys[pq[j]]) < 0;
    }

    private void exchange(int i, int j) {
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    public boolean contains(int k) {
        return qp[k] != -1;
    }

    private void swim(int k) {
        while (k > 1 && greater(k, k / 2)) {
            exchange(k, k / 2);
            k /= 2;
        }
    }

    private void sink(int k) {
        while (k * 2 >= N) {
            int j = k * 2;
            if (j < N - 1 && greater(j + 1, j)) j++;
            if (!greater(j, k)) break;
            exchange(k, j);
            k = j;
        }
    }

    public void change(int k, Key key) {
        if (!contains(k)) return;
        keys[k] = key;
        swim(qp[k]);
        sink(qp[k]);
    }

    public void insert(int k, Key key) {
        if (contains(k)) change(k, key);
        else {
            ++N;
            pq[N] = k;
            pq[k] = N;
            keys[k] = key;
            swim(k);
        }
    }

    public Key min() {
        return keys[pq[1]];
    }

    public int minIndex() {
        return pq[1];
    }

    public int deletMin() {
        if (isEmpty()) throw new NoSuchElementException();
        int min = pq[1];
        exchange(1, N--);
        sink(1);

        assert min == pq[N + 1];

        pq[N + 1] = -1;
        qp[min] = -1;
        keys[min] = null;
        return min;
    }

    public Key delete(int k) {
        if (!contains(k)) return null;
        int index = qp[k];
        Key del = keys[k];
        exchange(index, N--);
        swim(index);
        sink(index);
        pq[N + 1] = -1;
        qp[k] = -1;
        keys[k] = null;
        return del;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    @NotNull
    @Override
    public Iterator<Integer> iterator() {
        return new IndexPQIterator();
    }

    private class IndexPQIterator implements Iterator<Integer> {
        private IndexPriorityQueue<Key> copy;

        public IndexPQIterator() {
            copy = new IndexPriorityQueue<>(pq.length - 1);
            for (int i = 1; i < N; i++)
                copy.insert(pq[i], keys[pq[i]]);
        }

        @Override
        public boolean hasNext() {
            return !copy.isEmpty();
        }

        @Override
        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.deletMin();
        }
    }
}

本文标题:排序算法——基于比较的算法

文章作者:

发布时间:2018-09-29, 18:52:28

最后更新:2020-09-12, 16:12:15

原始链接:http://yif-hong.github.io/2018/09/29/BaseSort/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 公共方法
  2. 2. 选择排序
  3. 3. 插入排序
  4. 4. 希尔排序
  5. 5. 归并排序
    1. 5.1. 合并
    2. 5.2. 自顶向下的归并
    3. 5.3. 自底向上的归并排序
  6. 6. 快速排序
    1. 6.1. 切分 partition
    2. 6.2. 快速排序优化
      1. 6.2.1. 小数组使用插入排序
      2. 6.2.2. 三向切分优化重复数组的性能
  7. 7. 堆排序
    1. 7.1. 二叉堆
    2. 7.2. 堆的基础算法
      1. 7.2.1. 上浮 swim
      2. 7.2.2. 下沉 sink
    3. 7.3. 堆排序实现
  8. 8. 优先队列
    1. 8.1. 基础方法
    2. 8.2. 上浮 swim
    3. 8.3. 下沉 sink
    4. 8.4. 添加 insert
    5. 8.5. 删除最小值（优先级最高）
    6. 8.6. 完整代码实现
    7. 8.7. 性能
  9. 9. 索引优先队列
    1. 9.1. 初始化
    2. 9.2. 上浮和下沉
    3. 9.3. 改变 change
    4. 9.4. 插入 insert
    5. 9.5. 最小值 min
    6. 9.6. 删除最小值并返回索引（优先级最高）
    7. 9.7. 删除 delete
    8. 9.8. 完整代码实现
|