排序

一些下界

• 简单排序算法的下界
  所谓的简单排序指的是指通过交换相邻元素进行排序的算法。
  由于 $N$ 个互异数的数组的平均逆序数是 $N*(N-1)/4$
  所以一个简单排序算法平均都需要 $\Omega(N^2)$的运行时间。
  因此为了使排序算法以亚二次时间运行，必须执行一些比较，特别是对相距较远的元素进行比较

• 排序算法的一般下界
  所谓排序算法的一般下界，指的是 只用到比较的任意排序算法
  它们的最坏情况下都需要 $\left\lceil \log N! \right\rceil$（即 $\Omega(N\log N)$） 次比较，因此归并排序和堆排序在一个常数因子范围内是最优的。 并且平均都需要 $\log N!$ 次比较

插入排序

插入排序时最为基础的排序算法，它以 $O(N^2)$ 的运行时间

实现思路

实现思路如下

1. 当已排序的序列大小为0时，将插入的待排序的元素放入序列首部
2. 当已排序的序列大小不为0时，将插入的待排序的元素与已排序序列中的元素从第一个位置开始逐一比较，移过那些比待排序元素小的元素，停留在第一个比待排序元素大的元素的位置上，将后面的元素右移，然后在该位置插入待排序的元素。
3. 重复步骤二，知道待排序的序列大小变为0,。

   希尔排序

   重要性质

   一个$h_k$ 排序的文件（然后将是$h_{k-1}排序的$）将保持它的$h_k$排序性。
   如果没有这个重要性质，那么前面各趟的排序结果将会被后面的排序所打乱，从而使得该算法就没什么价值

   实现思路

   希尔算法使用一个增量序列 $h_1,h_2,h_3…h_k$($h_1=1$)来实现排序。而增量序列的选择将对运行时间有着决定性的作用。
   在使用增量 $h_k$ 的一趟排序后，对于每一个$i$我们都有 $a[i]<=a[i+h_k]$，所以相距 $h_k$的元素都被排序。此时称文件是 $h_k$排序的。
   在使用增量 $h_k$ 排序完后，我们再使用使用增量 $h_{k-1}$ 进行排序，直到 $h_1$ 为止。

一趟 $h_k$ 排序的一般做法是，对于$h_k,h_k+1,h_k+2,…,N$中的每一个位置$i$，把其上的元素放在$i,i-h_k,i-2h_k,…,i-nh_k$ 中的正确的位置

下图可直观感受下希尔排序

下面是几种常见的增量序列的选择

• Shell 增量序列（希尔增量）
  $h_t = \left\lfloor N/2\right\rfloor , h_k =\left\lfloor h_{k+1}/2 \right\rfloor$(流行但不好)
  使用 shell 增量序列的希尔排序最坏情形运行时间为$\Theta(N^2)$

• Hibbard 增量序列
  $h_i = 2^i-1$
  使用 Hibbard 增量的希尔排序最坏情形运行时间为$\Theta(N^{3/2})$

• Sedgewick 增量序列
  该增量序列中的项或者以$h_i = 9 4^i - 9 2^i + 1$的形式，或者以 $h_i = 4^i - 3 * 2^i + 1$的形式，其中最好的序列是 ${1,5,19,41,109…}$
  使用 Sedgewick 增量的希尔排序最坏情形运行时间为$O(N^{4/3})$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public void shellSort(int[] a) {
    int index = (int) Math.floor(Math.log(a.length/2 + 1)/Math.log(2)) + 1;
    int gap;
    int temp;
    int j;
    for (int i = index; i > 0; i--) {
        gap = (int) Math.pow(2,i) - 1;
        for (int pos = gap; pos < a.length; pos++) {
            temp = a[pos];
            for (j = pos; j >= gap && temp <= a[j-gap] ; j-=gap) {
                a[j] = a[j-gap];
            }
            a[j] = temp;
        }
    }
}

希尔排序小结

希尔排序的性能在实践中是完全可以接受的，即使是对于数以万计的 N 任是如此。编程的简单特点使得它成为对适度地大量的输入数据经常选用的算法。

堆排序

实现思路

这里以让一个乱序的序列变成一个递减序列为例

1. 用乱序的序列中的元素构造一个最小堆(二叉堆实现)
   在这个阶段需要花费 $O(N)$ 来构造最小堆。
   在这一阶段最多用到 $2N$ 次比较

2. 使用 deleteMin 方法删除最小堆的根节点
   这里的 deleteMin 方法与普通堆的 deleteMin 方法有所不同。堆排序中的 deleteMin 方法会将根元素移动到堆的最末尾，然后让堆缩小1。
   而这么做的原因在于解决堆排序的空间问题，即不再需要使用一个附加的数组来存储排序好的序列了
   在这个阶段每一次 deleteMin 操作需要花费 $O(\log N)$，总共需要 N 次操作，所以总共需要花费 $O(N\log N)$
   在这一阶段，第 $i$ 次 deleteMin 操作最多用到 $2\left\lfloor \log i\right\rfloor$ 次比较，总共需要 N 次操作，所以总数最多为 $2N\left\lfloor \log N\right\rfloor - O(N)$ 次比较。

3. 当堆的大小减到0的时候，排序结束，返回数组。
   将前两个步骤的比较次数和运行时间相加
   比较次数最多为 $2N+2N\left\lfloor \log N\right\rfloor - O(N)$，平均比较次数为$2N\left\lfloor \log N\right\rfloor - O(N\log\log N)$
   运行时间为 $O(N+N\log N) = O(N\log N)$

示例图如下

代码实现

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

public class HeapSort {
    
    private int[] heap;
    private int currentSize;
    
    public void upFilter(int pos) {
        int temp = heap[pos];
        while ((pos > 0) && (temp < heap[(pos+1)/2-1])) {
            heap[pos] = heap[(pos+1)/2-1];
            pos = ( pos + 1 ) / 2 - 1;
        }
        heap[pos] = temp;
    }

    public void downFilter(int pos) {
        int temp = heap[pos];
        int child = (pos + 1) * 2 - 1;
        while (child < currentSize) {
            if ((child != currentSize - 1) && (heap[child + 1] < heap[child])) {
                child += 1;
            }
            if (heap[child] < temp) {
                heap[pos] = heap[child];
                pos = child;
                child = (pos + 1) * 2 - 1;
            } else {
                break;
            }
        }
        heap[pos] = temp;
    }
    
    public void insert(int ele) {
        currentSize += 1;
        if (currentSize > heap.length) {
            return;
        }
        heap[currentSize - 1] = ele;
        upFilter(currentSize - 1);
        
    }

    public void deleteMin() {
        int temp = heap[0];
        heap[0] = heap[currentSize - 1];
        currentSize -= 1;
        downFilter(0);
        heap[currentSize] = temp;
    }
    
    public void buildHeap(int[] a) {
        heap = new int[a.length];
        currentSize = 0;
        for (int i = 0; i < a.length; i++) {
            insert(a[i]);
        }
    }
    
    public void heapSort(int[] a) {
        buildHeap(a);
        for (int i = 0; i < a.length; i++) {
            deleteMin();
        }
        displayArray(heap);
    }

    public void displayArray(int[] a) {
        for (int item : a) {
            System.out.print(item+",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] a = {5,2,8,3,1,2,9,20,26,22,17};
        heapSort.displayArray(a);
        heapSort.heapSort(a);
        heapSort.displayArray(a);

    }
}

堆排序小结

• 优点

  • 堆排序以 $O(N\log(N))$ 的运行时间来排序

• 缺点

  • 该算法的主要问题在于他使用了一个附加的数组。因此，存储需要增加一倍。而回避这一问题的聪明方法是在每一次 deleteMin 的时候，堆缩小1。因此位于堆中的最后一个单元可以用来存放刚刚用 deleteMin 删去的元素。

  • 该算法的还有一个问题就是排序时，元素之间的比较次数很多。
    而 java 对象元素之间的比较的开销是比较大的。

归并排序

虽然说堆排序已经将运行时间降低为 $O(N\log N)$,但他的一次排序中比较次数过多，使用java 编程时比较所产生的的开销会比较大，所以我们引入了归并排序，它只需要$O(N)$次比较,但也只需要 $O(N\log N)$ 的运行时间。

实现思路

归并排序的整体思想是”分治”。
基本的归并算法是取两个输入数组，一个输出数组，三个变量attr,bttr,cttr分别用来记录这三个数组中的位置信息。
一次归并的步骤如下：

1. 两个输入数组a,b 从attr,bttr从0开始，比较$a[attr],b[bttr]$，将小的元素放入数组c，然后使attr,cttr 或者 bttr,cttr 加一。重复如上操作，直到两个输入数组中的一个数组全部被放入输出数组中
2. 将另一个输入数组的剩余部分放入到输出数组

而归并排序的思路为：

1. 先“分”：将输入的序列分为对半分为两部分，对于每部分继续对半分直到不能分为止
2. 后“治”：运用上面的归并步骤归并分好的两部分。

示例图如下

代码实现

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

package sort;

public class MergeSort {

    public void mergeSort(int[] a) {
        int[] temp = new int[a.length];
        merge(a, temp,0,a.length/2);
        merge(a, temp,a.length/2 + 1, a.length - 1);

    }

    public void merge(int[] a, int[] temp, int left, int right) {
        int center = (left + right) / 2;
        if (left < center) {
            merge(a, temp, left, center);
            merge(a, temp, center + 1, right);
        }

        int i = left;
        int j = left;
        int k = center + 1;
        while (i <= right) {

            if ( j > center) {
                while ( k <= right) {
                    temp[i++] = a[k++];
                }
            }

            if ( k > right) {
                while ( j <= center) {
                    temp[i++] = a[j++];
                }
            }

            if (j <= center && a[j] <= a[k]) {
                temp[i++] = a[j++];
            }
            if (k <= right && a[k] < a[j]) {
                temp[i++] = a[k++];
            }
        }

        for (int l = left; l <= right; l++) {
            a[l] = temp[l];
        }
    }

    public void displayArray(int[] a) {
        for (int item : a) {
            System.out.print(item+",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] a = {5,2,8,3,1,2,9,20,26,22,17};
        mergeSort.displayArray(a);
        mergeSort.mergeSort(a);
        mergeSort.displayArray(a);

    }
}

归并排序小结

虽然归并排序的运行时间是 $O(N\log N)$ ，但是它有一个明显的问题，即合并两个已排序的表用到线性附加内存。在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加操作，它明显减慢了排序的速度。这种拷贝可以通过在递归的那些交替层次上审慎的交换 a 和 tempArray 的角色得以避免。
与其他的$O(N\log N)$排序算法比较，归并排序的运行时间严重依赖于比较元素和在数组中元素移动的相对开销。这与具体的编程语言相关，在 java 中由于元素移动是引用的赋值，所以元素移动是比较容易的，但是当执行一次泛型比较时(使用comparator)进行一次元素比较，开销可能是昂贵的。
事实上，它就是Java标准类库中泛型排序所使用的算法

快速排序

实现思路

快速排序也是一种分治的递归算法
一个quickSort其基本步骤如下

1. 如果 $S$ 中元素个数是 0 或 1 ，则返回。
2. 取 $S$ 中任一元素 $v$, 称之为枢纽元
3. 将 $S - {v}$($S$中其余元素)划分为两个不相交的集合，$S_1 = {x\in S - {v}\space |\space x\leq v}$ 和 $S_2 = {x\in S - {v}\space |\space x\geq v}$
4. 返回${quickSort(S_1),v,quickSort(S_2)}$

而快速排序需要注意以下几点

• 选取枢纽元
  枢纽元的选取将决定该算法的好坏，一个较好的枢纽元，应该是能将待排序的序列分成两个大小近似相等的部分。
  下面将介绍三种选取枢纽元的方法

  • 错误的方法
    直接选取序列中的第一个元素作为枢纽元，这时，如果输入是预排序的或者是反序的，那么这样的枢纽元将产生一个劣质的分割，因为所有的元素不是被划入$S_1$就是被划入$S_2$。更糟糕的是这种划分将会出现在每个递归调用中。因此这时的快速排序的运行时间将变为 $O(N^2)$

  • 安全但开销较大的方法
    通过随机数生成器随机选取枢纽元，这是一个非常安全的策略，但是随机数的生成一般开销很大，根本减少不了算法的其余部分的平均运行时间

  • 推荐的方法 三数中值分割法
    该方法的一般做法是选取待排序序列的第一个元素、最后一个元素以及最中间的元素，对这三个数排序选择他们的中值作为枢纽元。这种方法既避免了方法一中输入序列中出现预先排序的序列的情况，也避免了方法二中生成随机数开销过大的问题，所以是个推荐的方法

• 分割策略
  分割是一种容易出错或低效的操作，但使用一种已知方法是安全的。
  下面是一个已被证明能给出好结果的分割策略，其步骤如下

  1. 将枢纽元与最后的元素交换使得枢纽元离开要被分割的数据段，而$i$从第一个元素开始，而$j$从倒数第二个元素开始，

  2. 当$i$在$j$左边时，我们将$i$右移，移过那些小于枢纽元的元素，并将$j$左移，移过那些大于枢纽元的元素。

  3. 当 $i$ 和 $j$ 都停止时，$i$指向一个“大元素”，$j$指向一个“小元素”，互换$i$和$j$所指向的两个元素，重复第二步的过程。直到 $i$ 在 $j$ 的右边，执行第四步

  4. 互换 $i$ 指向的元素和枢纽元

     而这个分割策略还需要思考一个问题，那就是当序列中有元素与枢纽元相等时，是否应该移过该元素

  • 移过（不推荐）
    移过虽然能减少交换次数，但是由于枢纽元要与$i$最后所抵达的位置中的元素互换，这样会产生两个非常不均衡的子数组。
    例如当数组元素都相等时，我们会首先让$i$ 右移，移过那些小于等于枢纽元的元素，直到与$j$交错，因为在这个例子中所有元素都相等，那么$i$会一直移到倒数第二个元素，这样会使得 $S_1$ 有 $N-1$ 个元素 而 $S_2$ 只有 $1$ 个元素，相当于没有分割，其运行时间将会变为 $O(N^2)$，所以并不推荐。

  • 不移过（推荐）
    不移过虽然会使得交换次数变多，但是其正面效果确是 $i$ 和 $j$ 将在中间交错，即会产生两个较为均衡的子数组，所以是个推荐的做法

    示例图如下

• 小数组
  对于很小的数组($N \leq 20$) 快速排序不如插入排序。不仅如此，因为快速排序是递归的(即在递归过程中会将一个大数组分解成为一个个小数组)，所以这样的情形会经常发生。
  通常的解决方法是对于小数组，采取诸如插入排序这样的对小数组有效的排序算法。使用这种策略实际上可以节省 $15%$ 的运行时间。
  一种好的截止范围是 $N=10$，即当 $N\leq10$时，选择插入算法，当 $N > 10$ 时采取快速排序

除了上述几点注意点外，还可以做一些优化，即在用三数中值法时，可以将最小元素放在第一个位置，最大元素放在最后一个位置，而将枢纽元与倒数第二个元素互换。这样做的好处不仅是减少了交换次数，还提供了一个警戒线，即由于第一个元素一定比枢纽元小，所以可以把它作为$j$的警戒线，同理倒数第一个元素可以作为 $i$ 的警戒线
这时分割策略也相应进行一下调整，即$i$从第二个元素开始，而$j$从第倒数第三个元素开始

选择问题的线性期望时间算法——快速选择

之前，我们可以通过使用优先队列，以时间 $O(N + k\log N)$ 找到第 k 个最大（或最小）元，对于查找中值的特殊情况，它给出一个 $O(N\log N)$算法
而快速选择算法虽然最坏情况的运行时间为 $O(N^2)$（由于分割不均衡，导致其中一个子数组为空的情况），但其平均运行时间为 $O(N)$
其基本思路与快速排序大同小异

1. 如果 $S$ 中元素个数是 1 ，则返回该元素。如果正在使用小数组的截止方法且在截止范围内，则用插入排序将 $S$ 排序并返回第 k 个元素。

2. 取 $S$ 中任一元素 $v$, 称之为枢纽元

3. 将 $S - {v}$($S$中其余元素)划分为两个不相交的集合，$S_1 = {x\in S - {v}\space |\space x\leq v}$ 和 $S_2 = {x\in S - {v}\space |\space x\geq v}$

4. 步骤四有如下几种可能

   • 如果 $k \leq|S_1|$，那么第 $k$ 个最小元必然在 $S_1$ 中，那么使用序列 $S_1$重复执行上述步骤；

   • 如果 $k > |S_1|+1$，那么第 $k$ 个最小元必然在 $S_2$ 中，那么使用序列 $S_2$ 重复执行上述步骤;

   • 如果 $k = |S_1|+1$，那么第 $k$ 个最小元正好是枢纽元，返回该枢纽元，结束程序

代码实现

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

package sort;

public class QuickSort {

    public void insertSort(int[] a, int left,int right){
        int[] temp = new int[right - left +1];
        for (int i = left; i <= right - 1; i++) {
            int min = a[i];
            int minPos = i;
            for (int j = i + 1; j <= right; j++) {
                if (a[j] < min) {
                    minPos = j;
                    min = a[j];
                }
            }
            swapElement(a,i,minPos);
        }
    }
    public void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }
    public void quickSort(int[] a, int left, int right) {
        //在 N < 10 时使用插入排序
        if (right - left < 10) {
            insertSort(a,left,right);
            return;
        }

        int hubDollar = findHubDollar(a, left, right);
        int center = (left + right) / 2;
        swapElement(a, center, right - 1);
        int i = left + 1;
        int j = right - 2;
        while ( i <= j) {
            for (; a[i] < hubDollar; i++);
            for (; a[j] > hubDollar; j--);
            if (i <= j) {
                swapElement(a, i++, j--);
            }
        }
        swapElement(a, i, right - 1);
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }

    public int findHubDollar(int[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[center] < a[left]) {
            swapElement(a, center, left);
        }
        if (a[right] < a[left]) {
            swapElement(a, right, left);
        }
        if (a[right] < a[center]) {
            swapElement(a, right, center);
        }
        return a[center];
    }

    public void swapElement(int[] a, int pos1, int pos2) {
        int temp = a[pos1];
        a[pos1] = a[pos2];
        a[pos2] = temp;
    }

    public void displayArray(int[] a) {
        for (int item : a) {
            System.out.print(item+",");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] a = {5,2,8,3,1,2,9,20,26,22,17};
        quickSort.displayArray(a);
        quickSort.quickSort(a);
        quickSort.displayArray(a);

    }
}

快速排序小结

快速排序是实践中的一种快速的排序算法，在C++ 或对 Java 中基本类型的排序十分有用。它的平均运行时间是$O(N \log N)$。该算法之所以特别快，主要是由于非常精炼和高度优化的内部循环。它的最坏情况是 $O(N^2)$,但经过稍许努力，可使这些情形极难出现。

桶排序

实现思路

对于一个输入数据 $A_1,A_2,…,A_i(A_i\leq M)$ 我们可以建立一个大小为 M 的且被初始化全为0的 count 数组，当扫描到元素 $A_i$ 时，我们便让 $count[A_i] += 1$ 。当输入完毕后，扫描数组 count ，打印出排序结果

桶排序小结

桶排序虽然运行时间为 $O(M+N)$ 但其限制条件很强，一般只适用于小整数的情况。面对这些情况，使用快速排序之类的算法就有点小题大做了，这时便可以考虑桶排序

外部排序

当待排序的数据量很大，而所给内存很小时，上述的几种内部排序算法就无法满足条件，而需要接下来的外部排序算法。
外部排序算法通过每次执行从外存取得数据，装入内存，使内存装满，然后对内存中的数据进行排序，在转到外存这一重复操作来将数据进行排序。
它的实现思路与归并排序大同小异。

实现思路

首先我们将把每组排过序的记录称为顺串，并假设内存能容纳 $M$ 个记录，且有 $N$ 个待排序的记录

接着对于外部排序有以下三种思路

• 简单算法（2路合并）
  该算法将需要 $\left\lceil \log N/M \right\rceil$ 趟工作，外加一趟初始的顺串构造，并且需要4个磁盘带 $T_{a1},T_{a2},T_{b1},T_{b2}$。

  下面是具体思路

  1. 每次从 $N$ 个记录中取 $M$ 个记录，在内存中对它们进行排序，然后依次交替存在磁盘带 $T_{b1},T_{b2}$ 上

  2. 每次取出 $T_{b1},T_{b2}$ 中的第一个顺串，对他们进行归并（参考归并排序），使之成为一个长度为 $2^iM$ 的顺串（$i$为执行步骤二和三的总次数），并将他们依次交替存放在 磁盘带 $T_{a1},T_{a2}$，直到$T_{b1},T_{b2}$ 取尽为止。

  3. 每次取出 $T_{a1},T_{a2}$ 中的第一个顺串，对他们进行归并（参考归并排序），使之成为一个长度为 $2^iM$ 的顺串（$i$为执行步骤二和三的总次数），并将他们依次交替存放在 磁盘带 $T_{b1},T_{b2}$，直到$T_{a1},T_{a2}$ 取尽为止。

  4. 重复执行步骤二、三，直到 $2^iM \geq N$

• 多路合并（k路合并）
  如果我们有额外的磁盘带，那么为了减少排序所需要的躺数，我们可以使用$k$路排序。
  它需要 $\left\lceil \log_k N/M \right\rceil$ 趟工作，外加一趟初始的顺串构造，并且需要 $2k$个 磁盘带 $T_{a1},T_{a2},…,T_{ak},T_{b1},T_{b2},…,T_{bk}$

  下面是具体思路

  1. 每次从 $N$ 个记录中取 $M$ 个记录，在内存中对它们进行排序，然后依次交替存在磁盘带 $T_{b1},T_{b2},…,T_{bk}$ 上

  2. 每次取出 $T_{b1},T_{b2},…,T_{bk}$ 中的第一个顺串，对他们进行归并（参考归并排序），使之成为一个长度为 $k^iM$ 的顺串（$i$为执行步骤二和三的总次数），并将他们依次交替存放在 磁盘带 $T_{a1},T_{a2},…,T_{ak}$，直到$T_{b1},T_{b2},…,T_{bk}$ 取尽为止。

  3. 每次取出 $T_{a1},T_{a2},…,T_{ak}$ 中的第一个顺串，对他们进行归并（参考归并排序），使之成为一个长度为 $2^iM$ 的顺串（$i$为执行步骤二和三的总次数），并将他们依次交替存放在 磁盘带 $T_{b1},T_{b2},…,T_{bk}$，直到$T_{a1},T_{a2},…,T_{ak}$ 取尽为止。

  4. 重复执行步骤二、三，直到 $k^iM \geq N$

     示例图如下

     这里与第一种简单算法（二路合并）不同的地方在于归并这一操作。
     在二路合并中，我们只需比较在两个顺串中一共两个元素的大小，这可以用简单的逻辑判断来实现
     但在多路合并中，我们需要比较 k 个顺串中一共 k 个元素的大小，这里我们就不能用简单的逻辑判断来实现，而是可以通过构造一个优先队列，通过一个 deleteMin 操作来实现输出最小元，然后通过一个 insert 操作来新增一个元素用于同堆中剩下的其他元素进行比较

• 多项合并
  多路合并的主要缺点在于需要额外的大量磁盘带（$2k$），例如针对一个3路排序，它就需要额外的6个磁盘带。
  而多项合并只需要 $k+1$ 个磁盘带
  多项合并的第一次分配是十分重要的，对于一个 $k$ 路合并，如果顺串的个数是一个斐波那契数 $F_N$，那么分配这些顺串的最好方式是分裂为 $F^{(k)}(N-1),F^{(k)}(N-2),F^{(k)}(N-3),…,F^{(k)}(N-k)$，
  使得$F^{(k)}(N) = F^{(k)}(N-1)+F^{(k)}(N-2)+F^{(k)}(N-3)+…+F^{(k)}(N-k)$

  如果顺串的个数不是一个斐波那契数，则用一些哑顺串填补磁盘带，使个数变为一个斐波那契数。

  一个多项合并的具体思路如下($k=2$)，他需要3个额外磁盘带$T_1,T_2,T_3$

  1. 用上述方式，将顺串分配给 $T_2,T_3$，其中$T_2$分到$F_{N-1}$ 个，$T_3$ 分到 $F_{N-2}$ 个
  2. 归并含有顺串的两个磁盘带（例如$T_2,T_3$），将归并好的顺串存入到没有顺串的磁盘带（例如 $T_1$），归并之后 $T_1$ 含有 $F_{N-2}$ 个顺串， $T_2$ 有 $F_{N-1} - F_{N-2} = F_{N-3}$ 个顺串，$T_3$ 有0个顺串

  3. 重复步骤二，直到顺串的个数为 1 且只有一个磁盘带中有顺串为止

     示例图如下

还有一个需要考虑的地方就是如何考虑构造顺串
虽然有种简单的办法，那就是将 $M$ 个记录全读入到内存中(内存只能容纳 $M$ 个记录) ，然后对这 $M$ 个记录进行排序，得到一个顺串。
但是这种方法并不好，我们还有一个更为流行的方法，称为替换选择。它的步骤如下

• 首先，将 $M$ 个记录读入内存，并构造一个优先队列。

• 然后对优先队列执行一次 deleteMin 操作，输出一个最小值，此时从输入磁盘带上读入一个记录，比较该记录与输出的记录的大小。

  • 若该记录小于输出的记录，则不能把它放入当前的顺串，而是将它放入一个死区（类似堆排序）

  • 若该记录大于输出的记录，那么就插入该记录

• 直到当前优先队列的大小变为0，表示一个顺串构造完毕，此时用死区的记录以及从输入磁盘带上读取的新记录再构造一个新的优先队列，重复以上步骤，直到输入磁盘带中的记录读完，完成顺串的构造

示例图如下

一些排序算法运行时间的比较