maximus's blog
0%

全面内部外部排序算法总结C语言

发表于 分类于
本文字数： 24k 阅读时长 ≈ 22 分钟

排序算法总结

  • 排序算法是《数据结构与算法》中最基本的算法之一。
  • 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
  • 常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

  1. 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
  2. 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排 序算法是稳定的；否则称为不稳定的。
  3. 内部排序：数据元素全部放在内存中的排序。
  4. 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

内部排序

（一）选择排序

直接选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

  • 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

  • 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

  • 重复第二步，直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void swap(int *a,int *b) //交換兩個變數
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len) 
{
    int i,j;

        for (i = 0 ; i < len - 1 ; i++) 
    {
                int min = i;
                for (j = i + 1; j < len; j++)     //走訪未排序的元素
                        if (arr[j] < arr[min])    //找到目前最小值
                                min = j;    //紀錄最小值
                swap(&arr[min], &arr[i]);    //做交換
        }
}
2. 动图演示

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  • 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
    堆排序的平均时间复杂度为 Ο(nlogn)。
    1. 算法步骤

  • 创建一个堆 H[0……n-1]；

  • 把堆首（最大值）和堆尾互换；

  • 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

  • 重复步骤 2，直到堆的尺寸为 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
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    int i;
    // 初始化，i從最後一個父節點開始調整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}
2. 动图演示

（二）插入排序

直接插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

1. 算法步骤

  • 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

  • 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void insertion_sort(int arr[], int len){
            int i,j,key;
            for (i=1;i<len;i++){
                    key = arr[i];
                    j=i-1;
                    while((j>=0) && (arr[j]>key)) {
                            arr[j+1] = arr[j];
                            j--;
                    }
                    arr[j+1] = key;
            }
    }
    2. 动图演示

    希尔排序

    希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

1. 算法步骤

  • 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

  • 按增量序列个数 k，对序列进行 k 趟排序；

  • 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

1
2
3
4
5
6
7
8
9
10
11
void shell_sort(int arr[], int len) {
        int gap, i, j;
        int temp;
        for (gap = len >> 1; gap > 0; gap >>= 1)
                for (i = gap; i < len; i++) {
                        temp = arr[i];
                        for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                                arr[j + gap] = arr[j];
                        arr[j + gap] = temp;
                }
}
2. 动图演示

（三）交换排序

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮” 到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
void bubble_sort(int arr[], int len) {
        int i, j, temp;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
}
int main() {
        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
        int len = sizeof(arr) / sizeof(arr[0]);
        bubble_sort(arr, len);
        int i;
        for (i = 0; i < len; i++)
                printf("%d ", arr[i]);
        return 0;
}
2. 动图演示

3. 最快或最慢的时候
  • 当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。
  • 当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

    快速排序

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

1. 算法步骤

  • 从数列中挑出一个元素，称为 “基准”（pivot）;

  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

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
typedef struct _Range {
    int start, end;
} Range;

Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}

void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}

void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負值時引發段錯誤（Segment Fault）
    // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點
        int left = range.start, right = range.end;
        do {
            while (arr[left] < mid) ++left;   // 檢測基準點左側是否符合要求
            while (arr[right] > mid) --right; //檢測基準點右側是否符合要求
            if (left <= right) {
                swap(&arr[left], &arr[right]);
                left++;
                right--;               // 移動指針以繼續
            }
        } while (left <= right);
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}
_________________________________________________________________________

//递归法
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}

void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}
2. 动图演示

（四）归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

1. 算法步骤

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

  • 重复步骤 3 直到某一指针达到序列尾；

  • 将另一序列剩下的所有元素直接复制到合并序列尾。

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
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

2. 动图演示

（五）基数排序

将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

  • MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
  • LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

    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
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
#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10

void print(int *a, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("%d\t", a[i]);
  }
}

void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], exp = 1;

  for (i = 1; i < n; i++) {
    if (a[i] > m) {
      m = a[i];
    }
  }

  while (m / exp > 0) {
    int bucket[BASE] = { 0 };

    for (i = 0; i < n; i++) {
      bucket[(a[i] / exp) % BASE]++;
    }

    for (i = 1; i < BASE; i++) {
      bucket[i] += bucket[i - 1];
    }

    for (i = n - 1; i >= 0; i--) {
      b[--bucket[(a[i] / exp) % BASE]] = a[i];
    }

    for (i = 0; i < n; i++) {
      a[i] = b[i];
    }

    exp *= BASE;

#ifdef SHOWPASS
    printf("\nPASS   : ");
    print(a, n);
#endif
  }
}

int main() {
  int arr[MAX];
  int i, n;

  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX;

  printf("Enter %d Elements : ", n);
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("\nARRAY  : ");
  print(&arr[0], n);

  radixsort(&arr[0], n);

  printf("\nSORTED : ");
  print(&arr[0], n);
  printf("\n");

  return 0;
}

2. LSD 基数排序动图演示

3. 基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；

    计数排序

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

    1. 计数排序的特征

    当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。
算法的步骤如下：

  • （1）找出待排序的数组中最大和最小的元素
  • （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  • （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  • （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去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
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print_arr(int *arr, int n) {
        int i;
        printf("%d", arr[0]);
        for (i = 1; i < n; i++)
                printf(" %d", arr[i]);
        printf("\n");
}

void counting_sort(int *ini_arr, int *sorted_arr, int n) {
        int *count_arr = (int *) malloc(sizeof(int) * 100);
        int i, j, k;
        for (k = 0; k < 100; k++)
                count_arr[k] = 0;
        for (i = 0; i < n; i++)
                count_arr[ini_arr[i]]++;
        for (k = 1; k < 100; k++)
                count_arr[k] += count_arr[k - 1];
        for (j = n; j > 0; j--)
                sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
        free(count_arr);
}

int main(int argc, char **argv) {
        int n = 10;
        int i;
        int *arr = (int *) malloc(sizeof(int) * n);
        int *sorted_arr = (int *) malloc(sizeof(int) * n);
        srand(time(0));
        for (i = 0; i < n; i++)
                arr[i] = rand() % 100;
        printf("ini_array: ");
        print_arr(arr, n);
        counting_sort(arr, sorted_arr, n);
        printf("sorted_array: ");
        print_arr(sorted_arr, n);
        free(arr);
        free(sorted_arr);
        return 0;
}

2. 动图演示

桶排序

假设一种场景，对 {5, 2, 1, 4, 3} 进行升序排序，桶排序算法的实现思路是：

  • 准备 5 个桶，从 1~5 对它们进行编号；
  • 将待排序序列的各个元素放置到相同编号的桶中；
  • 从 1 号桶开始，依次获取桶中放置的元素，得到的就是一个升序序列。
    整个实现思路如下图所示：

桶排序算法中，待排序的数据量和桶的数量并不一定是简单的“一对一”的关系，更多场景中是“多对一”的关系，例如，使用桶排序算法对 {11, 9, 21, 8, 17, 19, 13, 1, 24, 12} 进行升序排序，实现过程如下图所示：

待排序序列中有 10 个元素，但算法中只用了 5 个桶，因此有些桶需要存放多个元素。实际场景中，我们可以自定义各个桶存放元素的区间（范围），比如上图中第一个桶存放 [0,5) 区间内的元素，第二个桶存放[6,10) 之间的元素。

当存在“一个桶中有多个元素”的情况时，要先使用合适的排序算法对各个痛内的元素进行排序，然后再根据桶的次序逐一取出所有元素，最终得到的才是一个有序序列。

总之，桶排序算法的实现思路是：将待排序序列中的元素根据规则分组，每一组采用快排、插入排序等算法进行排序，然后再按照次序将所有元素合并，就可以得到一个有序序列。

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
#include <stdio.h>
#include <stdlib.h>

#define N 7   // 待排序序列中的元素个数
#define NBUCKET 6  // 桶的数量
#define INTERVAL 10  // 每个桶能存放的元素个数
//建立桶
struct Node {
    float data;
    struct Node *next;
};

void BucketSort(float arr[]);
struct Node *InsertionSort(struct Node *list);
void print(float arr[]);

int main() {
    float array[N] = { 0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51 };
    BucketSort(array);
    print(array);
    return 0;
}

// 桶排序，arr 为待排序序列
void BucketSort(float arr[]) {
    int i, j;
    struct Node **buckets;
    // 创建所有桶
    buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
    // 设置每个桶为空桶
    for (i = 0; i < NBUCKET; ++i) {
        buckets[i] = NULL;
    }
    // 根据规定，将 arr 中的每个元素分散存储到各个桶中
    for (i = 0; i < N; ++i) {
        struct Node *current;
        int pos = arr[i] * 10;  //根据规则，确定元素所在的桶
        //创建存储该元素的存储块，并连接到指定的桶中
        current = (struct Node *)malloc(sizeof(struct Node));
        current->data = arr[i];
        current->next = buckets[pos];
        buckets[pos] = current;
    }
    // 调用自定义的排序算法，对各个桶进行排序
    for (i = 0; i < NBUCKET; ++i) {
        buckets[i] = InsertionSort(buckets[i]);
    }
    // 合并所有桶内的元素
    for (j = 0, i = 0; i < NBUCKET; ++i) {
        struct Node *node;
        node = buckets[i];
        while (node) {
            arr[j++] = node->data;
            node = node->next;
        }
    }
}

// 自定义的排序算法，用于对各个桶内元素进行排序
struct Node *InsertionSort(struct Node *list) {
    struct Node *k, *nodeList;
    if (list == NULL || list->next == NULL) {
        return list;
    }
    nodeList = list;
    k = list->next;
    nodeList->next = NULL;
    while (k != NULL) {
        struct Node *ptr;
        if (nodeList->data > k->data) {
            struct Node *tmp;
            tmp = k;
            k = k->next;
            tmp->next = nodeList;
            nodeList = tmp;
            continue;
        }
        for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
            if (ptr->next->data > k->data)
                break;
        }
        if (ptr->next != 0) {
            struct Node *tmp;
            tmp = k;
            k = k->next;
            tmp->next = ptr->next;
            ptr->next = tmp;
            continue;
        }
        else {
            ptr->next = k;
            k = k->next;
            ptr->next->next = 0;
            continue;
        }
    }
    return nodeList;
}

void print(float ar[]) {
    int i;
    for (i = 0; i < N; ++i) {
        printf("%.2f ", ar[i]);
    }
}

外部排序

核心部分

1. 实现外部排序的两个过程：

  • 将整个初始文件分为多个初始归并段;
  • 将初始归并段进行归并，直至得到一个有序的完整文件；

2. 时间组成：

  • 内部排序所需要的时间
  • 外存信息读写所需要的时间 （关键）
    与归并的趟数有关
    k要大 —– 传统方法 会引起内部归并时间增大
    赢者树
    败者树（目的：提高在k个归并串中当前值中找到最小值的效率）
    m要小 —– 置换选择排序
    Huffman（归并的顺序，对外存的I/O次数降到最低）
  • 内部归并所需要的时间　　　　

3. 为了提高整个外部排序的效率，分别从以上两个方面对外部排序进行了优化：

  • 在实现将初始文件分为 m 个初始归并段时，为了尽量减小 m 的值，采用置换-选择排序算法(内部使用败者树实现)，可实现将整个初始文件分为数量较少的长度不等的初始归并段。
  • 同时在将初始归并段归并为有序完整文件的过程中，为了尽量减少读写外存的次数，采用构建最佳归并树的方式（哈夫曼树实现），对初始归并段进行归并（败者树实现），而归并的具体实现方法是采用败者树的方式。

4. 优化递进顺序：

  • 二路归并【因为硬盘的读写速度比内存要慢的多，按照以上这种方法，每个数据都从硬盘读了三次，写了三次，要花很多时间。考虑K路】
  • 多路归并【K不是越大越好，因为K越大，在内部排序需要的时间越长，效率低。考虑减少初始顺串的数量M】
  • 置换选择算法【可以用败者树和堆排序实现，得到多个长度不等的初始归并段，如何设置它们的归并顺序，可以使得对外存的访问次数降到最低? 考虑结合哈夫曼树】
  • 最佳归并树（置换选择算法+哈夫曼树+多路归并+败者树）

5 胜者树 & 败者树 & 堆排序

  • 发展历史
    　　堆：其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。
    　　
    　　胜者树：这时人们想能否简化比较过程，这时就有了胜者树，这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。 而胜者树在节点上升的时候首选需要获得父节点，然后再获得兄弟节点，然后再比较。

败者树：这时人们又想能否再次减少比较次数，于是就有了败者树。在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。
　所以总的来说，减少了访存的时间。 现在程序的主要瓶颈在于访存了，计算倒几乎可以忽略不计了。

  • 相同点
    首先它们三个的相同点就是在于：空间和时间复杂度都是一样的O(N*logN)。调整一次的时间复杂度都是O(logN)的。
    所以这道题用堆来做，跟用败者树来做并没有本质上的算法复杂度量级上的差别。

  • 不同点
    　　堆：所有的节点都是关键字； 每次调整一层需要比较两次（父亲 左孩子| 父亲 右孩子）。
    　　
    　　胜者树：叶子节点是关键字，非叶子节点保存胜者索引；每次调整一层需要比较1次（自己 兄弟），读取两次（父亲| 兄弟）。

败者树：叶子节点是关键字，非叶子节点保存败者索引；每次调整一层需要比较1次（自己 父亲），读取一次（父亲），只需要和路径上的节点比较，不需要和兄弟节点比较，简化了重构的过程。； 新增B[0]记录比赛的胜者【在本例子中是ls[0]】

6. 涉及到的算法：

  • 多路归并算法
  • 败者树选择算法
  • 置换选择算法
  • 哈夫曼树
  • 内部排序算法（堆排序）

（一）定义

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

（二）步骤

外部排序算法由两个阶段构成：预处理和合并排序。

  1. 预处理产生有序的顺串：
    按照内存大小，将外存上含有 n 个纪录的大文件分成若干长度为 t 的子文件（t 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对子文件的 t 个纪录进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间；这样在外存上就得到了m个顺串（m=[n/t]）。
  2. 合并序列：
    对得到的顺段进行合并，直至得到整个有序的文件为止。

（三）k-路平衡归并

1. 2-路平衡归并

例子1
给你一个包含20亿个int类型整数的文件，计算机的内存只有2GB，怎么给它们排序？一个int数占4个字节，20个亿需要80亿字节，大概占用8GB的内存，而计算机只有2GB的内存，数据都装不下！可以把8GB分割成4个2GB的数据来排，然后在把他们拼凑回去。

在2G内存中排序的时候可以选择合适的内部排序，比如快速排序或归并排序等算法。为了方便，我们把排序好的2G有序数据称为有序子串。接着把两个小的有序子串合并成一个大的有序子串。

注意:读取的时候是每次读取一个int数，通过比较之后再输出。按照这个方法来回合并，总共经过三次合并之后就可以得到8G的有序子串。

我们假设需要排序的int数有12个，内存一次只能装下3个int数。接下来把12个数据分成4份，然后排序成有序子串：

然后把子串进行两两合并：输出哪个元素就在那个元素所在的有序子串再次读入一个元素：
继续

重复直到合并成一个包含6个int有序子串：

再把两个包含6个int的有序子串合并成一个包含12个int数据的最终有序子串。

因为硬盘的读写速度比内存要慢的多，按照以上这种方法，每个数据都从硬盘读了三次，写了三次，要花很多时间。

解释下：例如对于数据2，我们把无序的12个数据分成有序的4个子串需要读写各一次，把2份3个有序子串合并成6个有序子串读写各一次；把2份6个有序子串合并从12个有序子串读写各一次，一共需要读写各3次。

在进行有序子串合并的时候，不采取两两合并的方法，而是可以3个子串，或4个子串一起来合并。

例子2
例如，有一个含有 10000 个记录的文件，但是内存的可使用容量仅为 1000 个记录，毫无疑问需要使用外部排序算法，具体分为两步：

  • 将整个文件其等分为 10 个临时文件（每个文件中含有 1000 个记录），然后将这 10 个文件依次进入内存，采取适当的内存排序算法（快排或者归并排序）对其中的记录进行排序，将得到的有序文件（初始归并段）移至外存。
  • 对得到的 10 个初始归并段进行如图 1 的两两归并，直至得到一个完整的有序文件。

注意：此例中采用了将文件进行等分的操作，还有不等分的算法，后面会介绍。


图 1 2-路平衡归并

如图 1 所示有 10 个初始归并段到一个有序文件，共进行了 4 次归并，每次都由 m 个归并段得到 ⌈m/2⌉ 个归并段，这种归并方式被称为 2-路平衡归并。

注意：在实际归并的过程中，由于内存容量的限制不能满足同时将 2 个归并段全部完整的读入内存进行归并，只能不断地取 2 个归并段中的每一小部分进行归并，通过不断地读数据和向外存写数据，直至 2 个归并段完成归并变为 1 个大的有序文件。

对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。

计算机中处理数据的为中央处理器（CPU），如若需要访问外存中的数据，只能通过将数据从外存导入内存，然后从内存中获取。同时由于内存读写速度快，外存读写速度慢的差异，更加影响了外部排序的效率。

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多。

2. 多路归并

对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多。3.1 中图 1 中使用的是 2-路平衡归并的方式，举一反三，还可以使用 3-路归并、4-路归并甚至是 10-路归并的方式。

例子1

我们假设内存一共可以装4个int型数据。

刚才我们是采取两两合并的方式，现在我们可以采取4个有序子串一起合并的方式，这样的话，每个数据从硬盘读写的次数各需要2次就可以了。如图：

4个有序子串的合并，叫4路归并。如果是n个有序子串的合并，就把它称为n路归并。n并非越大越好。N越大，内部排序所需要的时间越多。
例子2

图 2 为 5-路归并的方式：

图 2 5-路平衡归并

对比3.1 中 图 1 和 3.2 中图 2可以看出，对于 k-路平衡归并中 k 值得选择，增加 k 可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的。除此之外，一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：s=⌊logk⁡m ⌋（其中 s 表示归并次数）。

从公式上可以判断出，想要达到减少归并次数从而提高算法效率的目的，可以从两个角度实现：

  • 增加 k-路平衡归并中的 k 值；[但不能影响内部归并的效率]
  • 尽量减少初始归并段的数量 m，即增加每个归并段的容量；

其增加 k 值的想法引申出了一种外部排序算法：多路平衡归并算法；增加数量 m 的想法引申出了另一种外部排序算法：置换-选择排序算法。

（四）多路平衡归并排序（胜者树、败者树）算法

对于外部排序算法来说，其直接影响算法效率的因素为读写外存的次数，即次数越多，算法效率越低。若想提高算法的效率，即减少算法运行过程中读写外存的次数，可以增加 k –路平衡归并中的 k 值。但是经过计算得知，如果毫无限度地增加 k 值，虽然会减少读写外存数据的次数，但会增加内部归并的时间，得不偿失。 （k越大，内部归并排序【比如选出最小值】需要花费更多的时间，所以k不是越大越好）

例如在上节中，对于 10 个临时文件，当采用 2-路平衡归并时，若每次从 2 个文件中想得到一个最小值时只需比较 1 次；而采用 5-路平衡归并时，若每次从 5 个文件中想得到一个最小值就需要比较 4 次。以上仅仅是得到一个最小值记录，如要得到整个临时文件，其耗费的时间就会相差很大。

为了避免在增加 k 值的过程中影响内部归并的效率，在进行 k-路归并时可以使用“败者树”来实现，该方法在增加 k 值时不会影响其内部归并的效率。

胜者树和败者树都是完全二叉树（非叶子节点存储的是索引），他们是树形选择排序的变形（非叶子节点存储的是具体的值）。

1. 胜者树实现内部归并

我们对胜者树进行定义：

  1. 胜者树是一颗完全二叉树
  2. 胜者树的叶子结点保存我们的一个输入缓冲区（一路归并顺序表）； 叶节点L[ 1……n]
  3. 胜者树的非叶子节点保存当前比较的胜者的输入缓冲区的指针；非叶子节点B[1……n-1] //存储的是数组L的索引
  4. 胜者树的根节点保存我们的胜者树当前的的一次比较中的冠军（最优值） B[0]

    　　　　
    当我们将我们的胜者树的最优值输入到我们的输出缓冲区（输出缓冲区从内存中额外开辟出来的一段，我们存储当前的归并的结果，缓冲区满写入磁盘）之后，我们的根节点便出现了空的情况，我们需要从根节点对应的输入缓冲区中在读入一个数据来充当下一次比较的选手，然后从下到上进行维护，我们的每一次的维护都需要比较兄弟的胜者然后选出新一轮的胜者然后一直优化到我们的根的路径上（从低至上，贯穿整个树）之后我们不断地进行上述的操作，指导我们的所有的输入缓冲区已经为空为止。

例子： 胜者树的一个优点是，如果一个选手的值改变了，可以很容易地修改这棵胜者树。只需要沿着从该结点到根结点的路径修改这棵二叉树，而不必改变其他比赛的结果。

我们把胜者树分为两部分：
b[]：用来保存K路数组的首元素，叶节点存放在此处，即底下那七个数组
ls[]：用来保存胜者数组的下标，ls[1]是最终的胜者(即所求的数)。

胜者树的中间结点记录的是胜者的标号
胜者树的示例。规定数值小者胜。

这里写图片描述
b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
b3 PK b0，b3胜b0负，内部结点ls[2]的值为3；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
b3 PK b1，b3胜b1负，内部结点ls[1]的值为3。

叶子结点b3的值变为11时，重构的胜者树如图所示
这里写图片描述

  1. b3 PK b4，b3胜b4负，内部结点ls[4]的值为3；
  2. b3 PK b0，b0胜b3负，内部结点ls[2]的值为0；
  3. b1 PK b2，b1胜b2负，内部结点ls[3]的值为1；
  4. b0 PK b1，b1胜b0负，内部结点ls[1]的值为1。.

2. 败者树实现内部归并

我们的胜者树维护的时候每次都需要去查找我们的根的兄弟节点的位置来进行比较，但是我们的每一次都要多一步查找兄弟的划，无论是对我们的程序的实现过程还是我们的时间效率上来看都还存在改进的余地。这里我们就要引入败者树，败者树与胜者树恰好相反，其双亲结点存储的是左右孩子比较之后的失败者，而胜利者则继续同其它的胜者去比较。

败者树的定义：

  1. 败者树是一颗完全二叉树（败者树是树形选择排序的一种变形）
  2. 败者树的叶子结点保存的是我们的输入缓冲区
  3. 败者树的非叶子结点保存我们的当前的比较中败者的对应的输入缓冲区的指针
  4. 败者树根保存我们的当前比较的亚军，根上面还有一个节点保存我们的冠军

比赛过程

  1. 将新入树的节点与其父亲进行比较
  2. 把败者存放在父亲节点
  3. 把胜者再与上一级的父亲进行比赛
  4. 比赛不断进行
  5. 把败者的索引存放在B[1]
  6. 把胜者的索引放到节点B[0]

例子1：
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。

我们把败者树分为两部分：
b[]：用来保存K路数组的首元素，叶节点存放在此处，即底下那七个数组
ls[]：用来保存败者数组的下标，b[0]是最终的胜者(即所求的数)，败者节点存放在中间节点。
败者树的中间结点记录的败者的标号
败者树示例，规定数大者败。
这里写图片描述

b3 PK b4，b3胜b4负，内部结点ls[4]的值为4；
b3 PK b0，b3胜b0负，内部结点ls[2]的值为0；
b1 PK b2，b1胜b2负，内部结点ls[3]的值为2；
b3 PK b1，b3胜b1负，内部结点ls[1]的值为1；
在根结点ls[1]上又加了一个结点ls[0]=3，记录的最后的胜者。

败者树重构过程如下：将新进入选择树的结点与其父结点进行比赛：将败者存放在父结点中；而胜者再与上一级的父结点比较。比赛沿着到根结点的路径不断进行，直到ls[1]处。把败者存放在结点ls[1]中，胜者存放在ls[0]中。是当b3变为13时，败者树的重构图：
这里写图片描述

注意，败者树的重构跟胜者树是不一样的，败者树的重构只需要与其父结点比较。b3与结点ls[4]的原值比较，ls[4]中存放的原值是结点4，即b3与b4比较，b3负b4胜，则修改ls[4]的值为结点3。同理，以此类推，沿着根结点不断比赛，直至结束。

例子2：
例如还是图 1 中，叶子结点 49 和 38 比较，38 更小，所以 38 是胜利者，49 为失败者，但由于是败者树，所以其双亲结点存储的应该是 49；同样，叶子结点 65 和 97 比较，其双亲结点中存储的是 97 ，而 65 则用来同 38 进行比较，65 会存储到 97 和 49 的双亲结点的位置，38 继续做后续的胜者比较，依次类推。

胜者树和败者树的区别就是：胜者树中的非终端结点中存储的是胜利的一方；而败者树中的非终端结点存储的是失败的一方。而在比较过程中，都是拿胜者去比较。


图 2 败者树

如图 2 所示为一棵 5-路归并的败者树，其中 b0—b4 为树的叶子结点，分别为 5 个归并段中存储的记录的关键字。ls 为一维数组，表示的是非终端结点，其中存储的数值表示第几归并段（例如 b0 为第 0 个归并段）。ls[0] 中存储的为最终的胜者，表示当前第 3 归并段中的关键字最小。

当最终胜者判断完成后，只需要更新叶子结点 b3 的值，即导入关键字 15，然后让该结点不断同其双亲结点所表示的关键字进行比较，败者留在双亲结点中，胜者继续向上比较。

例如，叶子结点 15 先同其双亲结点 ls[4] 中表示的 b4 中的 12 进行比较，12 为胜利者，则 ls[4] 改为失败者 15 所在的归并段即 b3，然后 12 继续同 ls[2] 中表示的 10 做比较，10 为胜者，则 ls[2] 改为失败者 12 所在的归并段即 b4，然后 10 继续同其双亲结点 ls[1] 表示的 b1（关键字 9）作比较，最终 9 为胜者。整个过程如下图所示：

注意：为了防止在归并过程中某个归并段变为空，处理的办法为：可以在每个归并段最后附加一个关键字为最大值的记录。这样当某一时刻选出的冠军为最大值时，表明 5 个归并段已全部归并完成。（因为只要还有记录，最终的胜者就不可能是附加的最大值）

本节介绍了通过使用败者树来实现增加 k-路归并的规模来提高外部排序的整体效率。但是对于 k 值得选择也并不是一味地越大越好，而是需要综合考虑选择一个合适的 k 值。

3. 胜者树 & 败者树 & 堆排序

发展历史
　　堆：其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。
　　胜者树：这时人们想能否简化比较过程，这时就有了胜者树，这样每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。 而胜者树在节点上升的时候首选需要获得父节点，然后再获得兄弟节点，然后再比较。

败者树：这时人们又想能否再次减少比较次数，于是就有了败者树。在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。

　　所以总的来说，减少了访存的时间。 现在程序的主要瓶颈在于访存了，计算倒几乎可以忽略不计了。

相同点
首先它们三个的相同点就是在于：空间和时间复杂度都是一样的O(N*logN)。调整一次的时间复杂度都是O(logN)的。
所以这道题用堆来做，跟用败者树来做并没有本质上的算法复杂度量级上的差别。

不同点
　　堆：所有的节点都是关键字； 每次调整一层需要比较两次（父亲 左孩子| 父亲 右孩子）。
　　胜者树：叶子节点是关键字，非叶子节点保存胜者索引；每次调整一层需要比较1次（自己 兄弟），读取两次（父亲| 兄弟）。

败者树：叶子节点是关键字，非叶子节点保存败者索引；每次调整一层需要比较1次（自己 父亲），读取一次（父亲），只需要和路径上的节点比较，不需要和兄弟节点比较，简化了重构的过程。； 新增B[0]记录比赛的胜者【在本例子中是ls[0]】

（五）置换选择排序算法详解

k 不是越大越好，那么我们可以想办法减少有序子串的总个数 m。这样，也能减少数据从硬盘读写的次数。

上一节介绍了增加 k-路归并排序中的 k 值来提高外部排序效率的方法，而除此之外，还有另外一条路可走，即减少初始归并段的个数，也就是本章第一节中提到的减小 m 的值。

m 的求值方法为：m=⌈n/l⌉（n 表示为外部文件中的记录数，l 表示初始归并段中包含的记录数）

如果要想减小 m 的值，在外部文件总的记录数 n 值一定的情况下，只能增加每个归并段中所包含的记录数 l。而对于初始归并段的形成，就不能再采用上一章所介绍的内部排序的算法，因为所有的内部排序算法正常运行的前提是所有的记录都存在于内存中，而内存的可使用空间是一定的，如果增加 l 的值，内存是盛不下的。所以要另想它法，探索一种新的排序方法：置换—选择排序算法。


例如已知初始文件中总共有 24 个记录，假设内存工作区最多可容纳 6 个记录，按照之前的选择排序算法最少也只能分为 4 个初始归并段。而如果使用置换—选择排序，可以实现将 24 个记录分为 3 个初始归并段，如图 1 所示：

置换—选择排序算法的具体操作过程为：

  1. 首先从初始文件中输入 6 个记录到内存工作区中；
  2. 从内存工作区中选出关键字最小的记录，将其记为 MINIMAX 记录；
  3. 然后将 MINIMAX 记录输出到归并段文件中；
  4. 此时内存工作区中还剩余 5 个记录，若初始文件不为空，则从初始文件中输入下一个记录到内存工作区中；
  5. 从内存工作区中的所有比 MINIMAX 值大的记录中选出值最小的关键字的记录，作为新的 MINIMAX 记录；[使用败者树或者堆排序实现]
  6. 重复过程 3—5，直至在内存工作区中选不出新的 MINIMAX 记录为止，由此就得到了一个初始归并段；
  7. 重复 2—6，直至内存工作为空，由此就可以得到全部的初始归并段。

拿图 1 中的初始文件为例，首先输入前 6 个记录到内存工作区，其中关键字最小的为 29，所以选其为 MINIMAX 记录，同时将其输出到归并段文件中，如下图所示：

此时初始文件不为空，所以从中输入下一个记录 14 到内存工作区中，然后从内存工作区中的比 29 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到 归并段文件中，如下图所示：

初始文件还不为空，所以继续输入 61 到内存工作区中，从内存工作区中的所有关键字比 38 大的记录中，选择一个最小值作为新的 MINIMAX 值输出到归并段文件中，如下图所示：

如此重复性进行，直至选不出 MINIMAX 值为止，如下图所示：

当选不出 MINIMAX 值时，表示一个归并段已经生成，则开始下一个归并段的创建，创建过程同第一个归并段一样，这里不再赘述。

败者树实现

在上述创建初始段文件的过程中，需要不断地在内存工作区中选择新的 MINIMAX 记录，即选择不小于旧的 MINIMAX 记录的最小值，此过程需要利用“败者树”来实现。
　　
同上一节所用到的败者树不同的是，在不断选择新的 MINIMAX 记录时，为了防止新加入的关键字值小的的影响，每个叶子结点附加一个序号位，当进行关键字的比较时，先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。
　　
在初期创建败者树时也可以通过不断调整败者树的方式，其中所有记录的序号均设为 0 ，然后从初始文件中逐个输入记录到内存工作区中，自下而上调整败者树。过程如下：

  1. 首先创建一个空的败者树，如下图所示：

    提示：败者树根结点上方的方框内表示的为最终的胜者所处的位置。
  2. 从初始文件中读入关键字为 51 的记录，自下往上调整败者树，如下图所示：

    提示：序号 1 为败者。 先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。
  3. 从初始文件中读入关键字为 49 的记录，调整败者树如下图所示：
  4. 从初始文件依次读入关键字为 39、46、38、29 的记录，调整败者树如下图所示： 
    ![](http://c.biancheng.net/uploads/allimg/190427/1100444F4-8.png)

由败者树得知，其最终胜者为 29，设为 MINIMAX 值，将其输出到初始归并文件中，同时再读入下一个记录 14，调整败者树，如下图所示：

注意：当读入新的记录时，如果其值比 MINIMAX 大，其序号则仍为 1；反之则为 2 ，比较时先比较序号，序号小的为胜者；序号相同的关键字值小的为胜者。。

通过不断地向败者树中读入记录，会产生多个 MINIMAX，直到最终所有叶子结点中的序号都为 2，此时产生的新的 MINIMAX 值的序号 2，表明此归并段生成完成，而此新的 MINIMAX 值就是下一个归并段中的第一个记录。

通过置换选择排序算法得到的初始归并段，其长度并不会受内存容量的限制，且通过证明得知使用该方法所获得的归并段的平均长度为内存工作区大小的两倍。

通过对初始文件进行置换选择排序能够获得多个长度不等的初始归并段

证明此结论的方法是 E.F.Moore（人名）在 1961 年从置换—选择排序和扫雪机的类比中得出的，有兴趣的可以自己了解一下。

若不计输入输出的时间，通过置换选择排序生成初始归并段的所需时间为O(nlogw)（其中 n 为记录数，w 为内存工作区的大小）。

（六）最佳归并树详解

1. 哈夫曼树

通过上一节对置换-选择排序算法的学习了解到，通过对初始文件进行置换选择排序能够获得多个长度不等的初始归并段，相比于按照内存容量大小对初始文件进行等分，大大减少了初始归并段的数量，从而提高了外部排序的整体效率。

本节带领大家思考一个问题：无论是通过等分还是置换-选择排序得到的归并段，如何设置它们的归并顺序，可以使得对外存的访问次数降到最低？

例如，现有通过置换选择排序算法所得到的 9 个初始归并段，其长度分别为：9，30，12，18，3，17，2，6，24。在对其采用 3-路平衡归并的方式时可能出现如图 1 所示的情况：

图 1 3-路平衡归并

提示：图 1 中的叶子结点表示初始归并段，各自包含记录的长度用结点的权重来表示；非终端结点表示归并后的临时文件。

假设在进行平衡归并时，操作每个记录都需要单独进行一次对外存的读写，那么图 1 中的归并过程需要对外存进行读或者写的次数为：（9+30+12+18+3+17+2+6+24）22=484（图 1 中涉及到了两次归并，对外存的读和写各进行 2 次）从计算结果上看，对于图 1 中的 3 叉树来讲，其操作外存的次数恰好是树的带权路径长度的 2 倍。所以，对于如何减少访问外存的次数的问题，就等同于考虑如何使 k-路归并所构成的 k 叉树的带权路径长度最短。**若想使树的带权路径长度最短，就是构造赫夫曼树。**

在学习赫夫曼树时，只是涉及到了带权路径长度最短的二叉树为赫夫曼树，其实扩展到一般情况，对于 k 叉树，只要其带权路径长度最短，亦可以称为赫夫曼树。

若对上述 9 个初始归并段构造一棵赫夫曼树作为归并树，如图 2 所示：

图 2 赫夫曼树作为3-路归并树

依照图 2 所示，其对外存的读写次数为：(23+33+63+92+122+172+182+242+30)*2=446

通过以构建赫夫曼树的方式构建归并树，使其对读写外存的次数降至最低（k-路平衡归并，需要选取合适的 k 值，构建赫夫曼树作为归并树）。所以称此归并树为最佳归并树。

2. 附加“虚段”的归并树

上述图 2 中所构建的为一颗真正的 3叉树（树中各结点的度不是 3 就是 0），而若 9 个初始归并段改为 8 个，在做 3-路平衡归并的时候就需要有一个结点的度为 2。

对于具体设置哪个结点的度为 2，为了使总的带权路径长度最短，正确的选择方法是：附加一个权值为 0 的结点（称为“虚段”），然后再构建赫夫曼树。例如图 2 中若去掉权值为 30 的结点，其附加虚段的最佳归并树如图 3 所示：


图 3 附加虚段的最佳归并树

注意：虚段的设置只是为了方便构建赫夫曼树，在构建完成后虚段自动去掉即可。

对于如何判断是否需要增加虚段，以及增加多少虚段的问题，有以下结论直接套用即可：在一般情况下，对于 k–路平衡归并来说，若 (m-1) MOD (k-1) = 0，则不需要增加虚段；否则需附加 k - (m-1)MOD(k-1) - 1 个虚段。