C++ 数据结构 (三) 列表 (4) 选择排序

1
2
3
4
5
6
7
8
9
10

// 对列表中起始于位置 p 的连续 n 个元素做选择排序，valid(p) &amp;&amp; rank(p) + n <= size
template <typename T>
void List<T>::selectionSort(Posi(T) p, int n) {
  Posi(T) head = p -> pred; Posi(T) tail = p; // 待排序区间 (head, tail)
  for (int i = 0; i < n; i++) tail = tail -> succ; // head/tail 可能是头/尾哨兵
  while (1 < n) { // 反复从 (非平凡的) 待排序区间内找出最大者，并移至有序区间前端
    insertBefore(tail, remove(selectMax(head -> succ, n)));
    tail = tail -> pred; n--; // 待排序区间、有序区间的范围，均同步更新
  }
}

1
2
3
4
5
6
7
8

template <typename T> // 从起始于位置 p 的 n 个元素中选出最大者，1 < n
Posi(T) List<T>::selectMax(Posi(T) p, int n) { // O(n)
  Posi(T) max = p; // 最大者暂定为 p
  for (Posi(T) cur = p; 1 < n; n--) // 后续节点逐一与 max 比较
    if (!lt((cur = cur -> succ) -> data, max -> data)) // 若 >= max
      max = cur; // 则更新最大元素位置记录
  return max; // 返回最大节点位置
}