秋叶依剑

Appearance

排序 ​

内部排序 ​

对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。绝大部分内部排序只适用于顺序存储，有的虽然可以使用链式存储，但代码实现稍微复杂。

元素移动次数、排序趟数与原始状态关系、每趟是否能确定一个元素位置。

插入排序 ​

插入排序有时默认指的是直接插入排序。

直接插入排序 ​

插入排序原理是通过构建有序序列，对于未排序数据，在已排序数据中从后向前扫描，找到相应的位置并插入。

直接插入排序的排序趟数固定为n-1，变化的是元素比较和移动次数。直接插入排序更适用与基本有序和数据量不大的排序表。

cpp
// 插入排序
void insertSort(int* arr, int len) {
  for (int i = 1; i < len; ++i) {
    int temp = arr[i], j = i;

    // 向后移动
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      --j;
    }
    // 插入数据
    arr[j] = temp;
  }
}
时间复杂度空间复杂度稳定性
$O(n^2)$$O(1)$稳定

空间效率：仅使用了常数个辅助单元，因而空间复杂度为$O(1)$

时间效率：

  • 最好的情况下，待排序序列为有序序列，此时仅需要比较$n-1$次，时间复杂度$O(n)$。

  • 最坏的情况下，待排序序列为逆序，此时需要比较$\frac {n(n-1)} 2$，时间复杂度$O(n^2)$。

  • 平均时间复杂度为$O(n^2)$

稳定性：稳定。每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变换情况。

适用性：适用于链式和顺序存储。元素基本有序且数据量不大。

直接插入排序每趟会得到有序子序列，但不能确定元素最终位置。

折半插入排序 ​

cpp
// 数组前面的有序部分进行二分（折半）查找定位，减少比较次数
void binaryInsertSort(int* arr, int len) {
  int i, j, left, right, mid, temp;
  for (int i = 1; i < len; ++i) {
    temp = arr[i];
    left = 0;
    right = i - 1;

    // arr[i]之前的有序序列进行二分查找定位
    // 最后left指向待插入位置
    while (left <= right) {
      mid = (left + right) / 2;
      if (arr[mid] > temp) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    // 将arr[left...i-1]元素统一向后移动
    for (int j = i; j > left; --j) {
      arr[j] = arr[j - 1];
    }

    // 插入元素
    arr[left] = temp;
  }
}

相对于直接插入排序，仅减少比较次数。相当于直接插入排序和二分查找相结合，使用二分查找优化直接插入排序中元素定位问题

希尔排序 ​

因为每趟排序的间隔逐渐缩小，希尔排序也称为“缩小增量排序”。

cpp
// 希尔排序
void shellSort(int* arr, int len) {
  int temp, j;
  // 第一次间隔为长度的一半，以后每次减半，最后一次为1
  for (int gap = len / 2; gap > 0; gap /= 2) {
    // 为了减少代码复杂度，不是每次处理一组，而是多组交替处理
    for (int i = gap; i < len; i++) {
      temp = arr[i];
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

空间效率：仅使用了常数个辅助单元，因而空间复杂度为$O(1)$

时间效率：希尔排序的时间复杂度依赖于增量序列函数，这涉及到数学难题。当n在某个特定的范围内时

  • 最好的情况下，时间复杂度$O(n^{1.3})$。

  • 最坏的情况下，时间复杂度$O(n^2)$。

  • 平均时间复杂度为O(n logn)~O(n^2)

稳定性：不稳定。例如：${2,1,1'}$，第一趟取增量为2，排序后为${1',1,2}$

适用性：算法依赖数组随机存取特性，仅适用于顺序存储。

交换排序 ​

冒泡排序 ​

cpp
// 冒泡排序
void bubbleSort(int* arr, int len) {
  // 从后向前冒泡，从小到大排序
  for (int i = 0; i < len; ++i) {
    for (int j = len - 1; j > i; --j) {
      if (arr[j - 1] > arr[j]) {
        swap(arr[j - 1], arr[j]);
      }
    }
  }

  // 从前向后冒泡，从小到大排序
  /* for (int i = len - 1; i > 0; --i) {
    for (int j = 0; j < i; ++j) {
      if (arr[j + 1] < arr[j]) {
        swap(arr[j + 1], arr[j]);
      }
    }
  } */
}

// 冒泡排序优化
void bubbleSortPro(int* arr, int len) {
  // 从后向前冒泡
  for (int i = 0; i < len - 1; ++i) {
    bool flag = 0;
    for (int j = len - 1; j > i; j--) {
      if (arr[j - 1] > arr[j]) {
        swap(arr[j - 1], arr[j]);
        flag = true;
      }
    }

    if (!flag) {  // 如果本趟没有发生交换说明线性表有序
      break;
    }
  }
}

空间效率：仅使用了常数个辅助单元，因而空间复杂度为$O(1)$

时间效率：

  • 最好的情况下，待排序序列为有序序列，此时仅需要比较$n-1$次，时间复杂度$O(n)$。

  • 最坏的情况下，待排序序列为逆序，此时需要比较$\frac {n(n-1)} 2$，时间复杂度$O(n^2)$。

  • 平均时间复杂度为$O(n^2)$

稳定性：稳定。从后向前冒泡，相等的两个元素不会发生交换。

冒泡排序每趟排序会产生有序子序列，确定一个元素的最终位置。

快速排序 ​

平均时间复杂度为$O(nlogn)$

  1. 调整序列中的元素，使当前序列最左端的元素在调整后满足左侧所有元素均不超过该元素、右侧元素均大于该元素。
  2. 对该元素的左侧和右侧分别进行递归进行第一步的调整，直到当前调整区间的长度不超过1。

选择一个pivot中心轴，一般选择左边第一个数，交替移动left 和 right 指针，二者重合之后，将pivot放到相遇的下标位置。

cpp
// 将[left, right]按照arr[left]分成两部分
// 左边都比arr[left]小，右边都比arr[left]大
// 返回中心下标
int partition(int arr[], int left, int right) {
  int pivot = arr[left];  // 将arr[left] 作为主元
  while (left < right) {  // 只要left和right不相遇
    // 反复左移right直到找到一个元素比pivot小
    while (left < right && arr[right] > pivot) right--;
    // 将找到的元素移到左边
    arr[left] = arr[right];
    // 再反复右移left直到找到一个元素比pivot大
    while (left < right && arr[left] <= pivot) left++;
    // 将该元素移动到右边
    arr[right] = arr[left];
  }

  // left 和 right相遇，则将pivot元素放到该位置下，一轮快排结束
  arr[left] = pivot;
  return left;  // left和right相遇的地方就是中心下标
}

// 快读排序， left和right初始值为序列的首尾下标
void quickSort(int arr[], int left, int right) {
  // 递归边界，left>=right说明此时区间不能再分了
  if (left >= right) {
    return;
  }

  // 将[left, right]按照arr[left]分成两部分
  // 左边都比arr[left]小，右边都比arr[left]大
  // 然后对这两部分递归再次划分，每划分一次都能确定一个元素的最终位置
  int pos = partition(arr, left, right);
  // 对左边区间进行递归快速排序
  quickSort(arr, left, pos - 1);
  // 对右边区间进行递归快速排序
  quickSort(arr, pos + 1, right);
}
cpp
//  
void quickSort(vector<int>& arr, int left, int right) {
  // 递归中断条件
  if (left >= right) {
    return;
  }

  // 选取最后一位作为主元值
  int pivot = arr[right];
  int index = left;

  // 遍历[left, right-1]区间，将比pivot小的元素移动到左边
  for (int i = left; i < right; ++i) {
    if (arr[i] < pivot) {
      swap(arr[index++], arr[i]);
    }
  }
  // index左边的元素都比pivot小，arr[index]>=pivot
  // 将pivot移动到index位置，这也是pivot最终位置
  swap(arr[index], arr[right]);

  quickSort(arr, left, index - 1);
  quickSort(arr, index + 1, right);
}
cpp
// 快速排序的简单实现，但是不满足一趟排序定位一个元素的最终位置
void quickSort(vector<int>& arr, int left, int right) {
  if (left >= right) return;

  // pivot可以选择数组内的任意元素
  int l = left - 1, r = right + 1, pivot = arr[left + right >> 1];

  while (l < r) {
    while (arr[++l] < pivot);
    while (arr[--r] > pivot);
    if (l < r) swap(arr[l], arr[r]);
  }

  // r和r左边的元素都比pivot小，所以选择r为分界点
  // 对于l来说，不一定
  quickSort(arr, left, r);
  quickSort(arr, r + 1, right);
}

空间效率：由于快速排序是递归的，需要借助一个递归工作站保存每层递归调用的必要信息，其容量与递归调用的最大深度一致。最好的情况下为$O(log_2n)$，最坏的情况下，因为要进行n-1次递归调用，所以栈的深度为$O(n)$，平均情况下栈的深度为$O(log_2n)$。

时间效率：

  • 最好的情况下，每次都能平衡划分，即pivot元素在序列的中间部分。此时时间复杂度$O(nlogn)$。

  • 最坏的情况下，待排序序列基本有序或者逆序，此时每次划分都是极不平衡的，栈需要递归n-1次，时间复杂度$O(n^2)$。

  • 平均时间复杂度为$O(nlogn)$

稳定性：不稳定。例如$3,2',2$，选取左边第一个元素为pivot，则第一趟排序后为$2,2',3$，最终排序也为$2,2',3$。

**快速排序是所有内部排序算法中平均性能最优的排序算法。**其他排序算法如堆排序，归并排序时间复杂度虽然也为$O(nlogn)$，但是面对数据量比较大，排序趟数比较多时，$nlogn$前面的系数往往比快速排序大。

**快速排序每一趟不产生有序子序列，但是每一趟排序后会将枢纽（pivot）元素放到其最终位置上，即每一趟均会确定一个元素的最终位置。**这是个很重要的命题点。

选择排序 ​

简单选择排序 ​

cpp
// 选择排序
void selectSort(int arr[], int len) {
  // for (int i = 0; i < len - 1; ++i) {
  //   for (int j = i + 1; j < len; ++j) {
  //     if (arr[i] > arr[j]) {
  //       int temp = arr[j];
  //       arr[j] = arr[i];
  //       arr[i] = temp;
  //     }
  //   }
  // }
    
  // 下面的实现可以比上面减少交换次数
  int min;
  for (int i = 0; i < len - 1; ++i) {
    min = i;  // 默认当前元素为最小
    for (int j = i + 1; j < len - 1; ++j) {
      // 只要遇到比arr[min]小的元素，就更新min的值
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    // 如果min值发生和改变，就交换两元素的值
    // 这个思想在堆排序也有应用
    if (min != i) {
      swap(arr[i], arr[min]);
    }
  }
}

空间效率：仅使用了常数个辅助单元，因而空间复杂度为$O(1)$

时间效率：

简单选择排序在序列基本有序的情况下元素移动的次数较少，但是比较次数和序列的初始状态无关，因此时间复杂度始终是$O(n^2)$。

稳定性：不稳定。如$2,2',1$，第一趟排序时为$1,2',2$，最终排序结果也为$1,2',2$。

简单选择排序每趟会产生有序子序列，确定一个元素的最终位置。

堆排序 ​

https://www.bilibili.com/video/BV1fp4y1D7cj

堆具有以下特点：

  • 完全二叉树
  • 大顶堆：每个结点的值都大于或等于其左右子树结点的值
  • 小顶堆：每个结点的值都小于或等于其左右孩子结点的值

由于堆本质是一棵完全二叉树，则可以用数组arr[n]存储。对于第i个元素，有以下性质：

  • arr[i]的左孩子arr[i*2 + 1]
  • arr[i]的右孩子arr[i*2 + 2]
  • arr[i]的父结点arr[(i-1)/2]

堆排序有两个关键点，第一是建堆，第二是堆排序，这两个过程都需要heapify()函数调整堆。

cpp
// 维护堆
/**
 * @param arr 存储堆的数组
 * @param len 数组长度
 * @param pos 待维护结点位置下标
 * swap()是c++ 
 */
void heapify(int* arr, int len, int pos) {
  int largest = pos;
  int lson = pos * 2 + 1;
  int rson = pos * 2 + 2;

  // 找到左右孩子中比父结点大的结点下标，并存储在largest中
  if (lson < len && arr[largest] < arr[lson]) {
    largest = lson;
  }
  if (rson < len && arr[largest] < arr[rson]) {
    largest = rson;
  }

  // 如果largest的值没有发生了变化，说明不需要维护堆
  // 否则交换父结点与arr[largest]的值，并递归继续维护堆
  if (largest != pos) {
    // 交换两个元素
    swap(arr[largest], arr[pos]);
    // 继续向下维护堆
    heapify(arr, len, largest);
  }
}

// 堆排序
void heapSort(int* arr, int len) {
  int i;
  // 建堆，时间复杂度O(n)
  // 找到堆最后一个元素的父结点，向前逐个调整堆
  // len/2-1 是由最后一个元素父结点公式 ((len-1)-1)/2 得到的
  for (i = len / 2 - 1; i >= 0; --i) {
    heapify(arr, len, i);
  }

  // 排序
  // 每一趟均会确定一个元素的最终位置，堆的大小减1
  for (i = len - 1; i > 0; --i) {
    // 将根结点和堆最后一个元素交换位置
    swap(arr[i], arr[0]);
    // 维护根结点，注意此时数组长度为i
    // 也就是每确定一个元素最终位置，数组长度减1
    heapify(arr, i, 0);
  }
}

空间效率：仅使用了常数个辅助单元，因而空间复杂度为$O(1)$

时间效率：

  1. 在建立含有n个元素的堆时，关键字的比较次数不超过4n（证明用到了级数），时间复杂度为$O(n)$

  2. 堆排序时，以大顶堆为例，根结点一定是最大的元素。将根结点元素和最后一个元素交换，重新调整堆，需要进行进行n-1次。每次调整时间复杂度为$O(logn)$，则总的时间复杂度为$O(nlogn)$。

稳定性：不稳定。

堆排序每趟会产生有序子序列，确定一个元素的最终位置。

插入法建堆过程和筛选法不太一样，插入法在插入一个新元素是，只和父结点比较，无需和兄弟结点比较，如果大于父结点则上调一层，比较一次。一般题目给出一个已经建好的堆，插入一个新元素时，求比较次数用的是插入法。

归并排序 ​

https://segmentfault.com/a/1190000021734148

归并排序时间复杂度为$O(nlogn)$

cpp
void mergeSort(vector<int>& arr, int left, int right) {
  if (left >= right) {
    return;
  }

  // 获取中间位置
  int mid = (left + right) >> 1;

  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);

  // 定义临时辅助数组
  vector<int> tmp(right - left + 1, 0);
  int i = left, j = mid + 1, index = 0;

  while (i <= mid && j <= right) {
    tmp[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
  }

  // 如果有剩余元素，直接拷贝
  while (i <= mid) tmp[index++] = arr[i++];
  while (j <= right) tmp[index++] = arr[j++];

  // 将合并后的序列拷贝回arr
  std::copy(tmp.begin(), tmp.end(), arr.begin() + left);
}

空间效率：仅使用了和序列等长的辅助数组，因而空间复杂度为$O(n)$

时间效率：每趟归并的时间复杂度为$O(n)$，共需要$\lceil log_2n \rceil$趟归并，所以时间复杂度$O(nlogn)$

稳定性：稳定。

此处可联想到外排序中的多路平衡归并，做m路平衡归并时，如果有r个初始归并段，则需要归并的趟数为$\lceil log_m r \rceil$。

非比较排序 ​

计数排序 ​

计数排序（Counting Sort）核心思想是将待排序数组元素的值转化为计数数组的索引值，从而间接地使得待排序序列有序。

桶排序 ​

桶排序（Bucket Sort），也称为箱排序。桶排序体现了分治法的思想，其基本思想是将待排序数组分配到若干个桶内，然后在每个桶内各自进行排序，桶内的排序可以使用不同的算法，比如直接插入排序或快速排序。每个桶执行完成后，依次将桶内有序序列取出来，即可得到完整的排序结果。

基数排序 ​

基数排序（Radix Sort）将整数或字符串切分成多个数字或字符，然后对对应位置的数字或字符分别进行比较。

基数排序可以基于计数排序的方式也可以基于桶的方式实现。基于计数排序的实现方式比较巧妙，基于桶的实现方式比较常见。

MSD：首先根据关键字权重划分各个子序列（称为桶），对各个桶递归使用MSD

LSD：采用分配-收集模式，一般对整数排序使用的就是这种模式。

对于基数排序而言，很重要的一点就是按位排序时必须是稳定的，这也保证了基数排序的稳定性。

内排序算法的各种指标比较 ​

排序方法时间复杂度（平均）时间复杂度（最好）时间复杂度（最坏）空间复杂度稳定性每一趟是否会确定一个元素位置排序趟数与原始状态
冒泡排序$$ O(n^{2})$$$$ O(n)$$$$O(n^{2})$$O(1)稳定会有关
简单选择排序$$ O(n^{2})$$$$O(n^{2})$$$$O(n^{2})$$O(1)稳定会无关
直接插入排序$$O(n^{2})$$$$ O(n)$$$$O(n^{2})$$O(1)稳定会生成有序子序列，但不会确定最终位置无关，n-1趟
希尔排序O(n logn)~O(n^2)O(n^1.3)$$O(n^{2})$$O(1)不稳定不会无关
堆排序O(n logn)O(n logn)O(n logn)O(1)不稳定会无关
归并排序O(n logn)O(n logn)O(n logn)O(n)稳定会生成有序子序列，但不会确定最终位置无关
快速排序O(n logn)O(n logn)$$O(n^{2})$$O(logn)~O(n)不稳定会
下面是非比较排序
计数排序$O(n+k)$$O(n+k)$$O(n+k)$$O(n+k)$稳定
桶排序$O(n+k)$$O(n)$$O(n^2)$$O(n+k)$稳定
基数排序$O(n*k)$$O(n*k)$$O(n*k)$$O(n+k)$稳定无关

不稳定算法：简希快，堆成堆（捡锡块，堆成堆）

在待排序序列基本有序的前提下，直接插入排序和冒泡排序效率最高，可达到$O(n)$，在待排序序列基本逆序的情况下，直接插入排序效率最低。

在待排序序列基本有序或逆序的前提下，快速排序效率都降低到$O(n^2)$，快速排序适用于元素基本无序的情况。

image-20191221200801123

为什么快速排序优于堆排序 ​

**堆排序数据访问的方式没有快速排序友好。**对于快速排序来说，数据是顺序访问的。对于堆排序来说，数据是跳着访问的。

比如堆排序的堆化过程中，对堆顶进行堆化会依次访问数组下标是 1，2，4，8 的元素，而不是像快速排序那样，局部顺序访问，所以，这样对 CPU 缓存是不友好的。

**对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。**排序有有序度和逆序度的概念。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。

快速排序数据交换的次数不会比逆序度多。而堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

外部排序 ​

存储器与缓冲区 ​

存储器按照存取方式分为：随机存储器（RAM）、只读存储器（ROM）、顺序存取存储器（磁带）、直接存取存储器（磁盘、光盘）。RAM和ROM主要用于内存，磁盘和磁带主要用于外存，接下来主要讨论外存的磁盘排序。

随机存取就是直接存取，可以通过下标直接访问的那种数据结构，与存储位置无关，例如数组。非随机存取

使用文件进行数据处理的基本单位叫做逻辑记录（简称记录）。而在磁带或者磁盘进行物理存储的记录叫做物理记录，它是操作系统一次可读写的存储单位。

对磁盘存来说，从大到小的存储单位是盘片组、柱面、磁道和扇区。 $$ 盘片组的容量 = 等于该盘片的柱面数 \times 每个柱面磁道数 \times 每个磁道字节数 $$ 一个磁道可以划分若干扇区，一个扇区就是一次读写的最小数据量，每个扇区中包含相同的数据量。磁盘一次读写操作访问一个扇区，称为访问"一页"或"一块"，又称为"一次访外"。

为了实现磁盘的读写操作，在内存中需要开辟一些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域成为缓冲区，存入缓冲区的信息称为缓冲信息。

一个缓冲区的大小应与操作系统一次读写的块的大小相适应。如果不匹配就会造成空间浪费。

每个缓冲区的构造是一个先进先出的队列。对于输入缓冲区，如果队满就需要停止输入，处理存放于缓冲区中的数据，待数据处理完之后清空缓冲区，重新开始向该缓冲区存入数据。

基于磁盘的外排序 ​

对于以文件形式存放于磁盘存储器上的数据进行外排序是，一般使用归并排序的方法。它的特点是对所有待排序的数据元素顺序存取，顺序比较，其他排序方法没有这个特点。

外排序主要分为两个阶段：

  1. 生成初始归并段：建立为内存缓冲区，根据缓冲区大小将输入文件划分为若干段， 分段读入内存。用某种内排序方法，如堆排序，对各段进行排序。这些经过排序的段叫做初始归并段（又称初始顺串，runs）。将这些初始归并段写到外存文件上。
  2. 多趟归并排序：对第一阶段产生的初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，至此完成了对这个文件的外排序。

归纳起来，影响磁盘排序时间性能的主要有两个原因：

  1. 读写记录次数
  2. 关键字比较次数

不同于内排序，磁盘排序中元素的移动次数相对于上述两个因素可以忽略，，所以一般不考虑元素移动的开销。

所以接下来要介绍的三个算法均是为了减少上述两个因素的影响而设计的。

  • 败者树：减少关键字的比较次数
  • 置换选择排序：减少初始归并段的个数
  • 多路平衡归并：降低归并趟数
  • 最佳归并树：给出最佳归并方案，减少读磁盘次数

败者树 ​

败者树（tree of loser）是一棵完全二叉树，其中叶子结点存储参与归并的记录，分支结点存放关键字对应的段号。

败者树是两两比较，败者所在段号记录父结点，胜者继续向上层比较。一般可以设置$\infty$作为段结束标志，这样如果某段提前比较完毕，那么$\infty$该段可继续参与比较，但是$\infty$始终停留在叶结点。直到所有叶结点都为$\infty$，则所有元素都比较完毕。这样可以保证败者树的结构。

描述m路归并的败者树的高度为$ \lceil log_2 m \rceil$ （不计入叶结点），在每次调整时，找到下一个具有最小排序码记录时，最多做$\lceil log_2 m \rceil $次比较。

如果多路平衡归并和置换选择排序基于败者树实现，可以减少关键字比较次数，从而提高算法身效率。

多路平衡归并 ​

多路平衡归并，又称为m路平衡归并：每一趟从r个归并段中得到$\lceil \frac r m \rceil$个归并段。如果说r不能被m整除，则多余的归并段参与下趟归并。

做m路平衡归并时，如果有r个初始归并段，则需要归并的趟数为$\lceil log_m r \rceil$。

可以看到，当初时归并段一定时，m路归并的好处在于减少归并趟数，从而减少访问外存次数。

做内归并时，在m个记录中选择最小者，需要顺序比较m-1次。每趟归并n个记录需要做$(n-1) \times (m-1) $次比较，S趟归并总共需要的比较次数为 $$ S\times(n-1)\times(m-1) = \lceil log_mr\rceil \times (n-1)\times(m-1) $$ 利用换底公式$log_m r = \frac {log_2 r} {log_2 m} $，可得S趟归并总共需要比较次数大约为 $$ log_2 r \times (n-1) \times (m-1) / (log_2 m) $$ 其中的$log_2 r \times (n-1)$在初始归并段个数r与记录数n一定时是一个常数，而$(m-1)/log_2 m$ 在m增大时趋于无穷大。因此增大归并路数m，会使得内部归并时间增大，当m增大到一定程度，就可能抵消由于读写磁盘次数减少而带来的好处。

基于败者树 ​

利用败者树，在m个记录选择最小者，只需要$O(log_2 m)$次比较，每趟归并n个记录需要做$(n-1) \times \lceil log_2m \rceil $次比较，S趟归并总共需要的比较次数为 $$ \begin{aligned} S \times (n-1) \times \lceil log_2 m \rceil & = \lceil log_mr\rceil \times (n-1)\times\lceil log_2 m\rceil \ & \approx \lceil log_2 r \rceil \times (n-1) \times \frac {log_2 m} {log_2 m} \ & = \lceil log_2 r \rceil \times (n-1) \end{aligned} $$ 这样，排序码的比较次数与m无关，总的内部归并时间不会随着m的增大而增大。因此，如果基于败者树，只要内存空间允许，增大归并路数m，将有效减少归并趟数，从而减少读写磁盘次数，提高外排序的速度。

置换-选择排序 ​

为了减少读写磁盘次数，除了增加归并路数m外，还可以减少初始归并段的个数r。在总记录数一定时，要想减少r，必须增加初始归并段的长度。为此可采用置换-选择排序算法。**在使用同样大小的内存工作区的情况下，生成的初始归并段长度平均是原来的2倍。**从而减少初始归并段个数，降低归并趟数。

设内存工作区可容纳w个记录，则采用置换-选择排序可生成平均长度为2w的初始归并段。

若输入文件有n个记录，基于败者树，每次选择当前最小记录，需要时间为$O(log_2w)$，对所有n个记录都处理一次，所需时间为$O(nlog_2w)$ 。

执行过程 ​

反复执行下面三步：

  1. 输出：选择当前内存区域最小的元素输出，然后补充相应位置元素。
  2. 冻结：如果当前内存区域元素比上次输出元素小则冻结该元素，选择次小元素输出。
  3. 解冻：如果内存所有元素均冻结，则表明一个初始归并段已经生成。解冻所有元素，开始下一个归并段的生成。

最佳归并树 ​

一般地，设参加归并排序的初始归并段的个数为r，做m路平衡归并排序，归并树是描述归并过程且结点只有度为0和度为m的严格m叉树。

最佳归并树是哈弗曼树的扩展，是带权路径最小的扩充m叉树。

外结点（叶结点）：参加归并的各初始归并段。

内结点（非叶结点）：每次做m路归并得到的中间结点。

结点权重：归并段的长度（所包含物理记录数）。

设WPL是归并树的带权路径长度，则归并过程中的I/O次数为 $$ I/O次数 = 2 \times WPL $$

设度为0的结点有$r_0$个，度为m的结点有$r_m$个，则根据数的基本性质：结点数等于所有结点度之和加1 $$ r_0 + r_m = r + r_m = 0 \times r_0 + m \times r_m + 1 \ 化简得：r_m = (r - 1) / (m - 1) $$ 令$u = (r-1) % (m - 1)$

  • 若$u = 0$，这说明正好可以构造严格m叉树，不需要补充虚段数
  • 若$u \neq 0$，说明多出了u个结点，不能被$(m-1)$整除，则需要补充$(m - u - 1)$个虚段数

刷题小知识 ​

多路平衡树 ​

多路平衡归并的两个阶段，每个阶段的工作

  • 第一阶段，生成初始归并段：根据内存工作区的大小，将有n个记录的磁盘文件分批读入内存，采用有效的内排序方法进行排序，生成若干有序子文件，即初始归并段。
  • 第二阶段，多趟归并排序：采用多路归并的方法将这些归并段逐趟归并，最后归并成一个有序文件。

对n个记录做m路平衡归并排序，在内存工作区可容纳k个记录的情况下，可以生成归并段的个数为$r = \lceil n/k \rceil$

每个初始归并段的大小与内存工作区的容量相等，它是在内存中采用某种内排序方法进行排序得到的。

已知输入文件中有n个记录，放在p个物理块中，设初始归并段r，做m路平衡归并排序，总的I/O次数是多少？

一共需要$s = \lceil log_m r \rceil$趟归并。

  • 第一阶段，生成初始归并段：需要将所有记录都处理一遍，读写2p块。
  • 第二阶段，多趟归并排序：每趟都需要将所有记录处理一遍，读写2p块。

则总的读写次数为：$2p + 2p \times \rceil log_m r \rceil$。

置换-选择排序 ​

当输入文件中所有记录已经按排序码大小递减排列，即$k_1 \geq k_2 \geq ··· \geq k_{n-1} \geq k_n$，且可用呢村缓冲区空间大小为w，这时使用置换-选择排序产生的输出是什么？

除了最后一个初始归并段外，其他初始归并段长度都是w。全部初始归并段个数为$\lceil n / w \rceil$，最后一个初始归并段的长度为$n - \lceil n / w \rceil$。（我们要求初始归并段中元素从小到大排序）所以这是最坏的情况。

当输入文件中所有记录已经按排序码大小递增排列，即$k_1 \leq k_2 \leq ··· \leq k_{n-1} \leq k_n$，且可用呢村缓冲区空间大小为w，这时使用置换-选择排序产生的输出是什么？

只产生一个初始归并段，其长度与输入记录个数n相同。

并行操作的缓冲区处理 ​

如果采用m路并对m个归并段进行归并，至少需要m个输入缓冲区，和1个输出缓冲区。每个缓冲区存放一个块的信息。

如果同时进行输入、内部归并、和输出操作，则必须设置2m个输入缓冲区和2个输出缓冲区。

做m路归并。需要有m个输入缓冲区和1个输出缓冲区参与，每个输入缓冲区存放对应归并段当前参加归并的一个物理块。

为了使得输入与内部归并并行执行，需要再设置m个输入缓冲区，在对那m个输入缓冲区的记录做归并的同时，把对应归并段下个物理块输入内存空闲的m个输入缓冲区中。

此外为了使得内部归并与输出并行执行，需要再设置一个输出缓冲区，在一个输出缓冲区已满向外输出的同时，可以向另外一个输出缓冲区存放归并记录。

缓冲区的分配应该是动态的，可以根据需要位某一归并段分配缓冲区。但不论如何，每个归并段至少需要一个输入缓冲区，用以存放该归并段记录。

image-20210710211250597

Released under the MIT License.

Copyright © 2022 秋叶依剑