C++ 数据结构 (二) 向量 (7) 起泡排序

1
2
3
4
5
6
7
8
9

void Vector<T>::sort(Rank lo, Rank hi) { // 区间 [lo, hi)
  switch (rand() % 5) { // 视具体问题的特点灵活选取或扩充
    case 1: bubbleSort(lo, hi); break;    // 起泡排序
    case 2: selectionSort(lo, hi); break; // 选择排序 (习题)
    case 3: mergeSort(lo, hi); break;     // 归并排序
    case 4: heapSort(lo, hi); break;      // 堆排序 (第10章)
    default: quickSort(lo, hi); break;    // 快速排序 (第12章)
  }
} // 在此统一接口下, 具体算法的不同实现, 将在后续各章节陆续讲解

1
2
3
4
5
6
7
8
9

void bubbleSort(int A[], int n)
{
  for (bool sorted = false; sorted = !sorted; n--) // 逐趟扫描交换, 直至安全有序
    for (int i = 1; i < n; i++) // 自左向右, 逐对检查 A[0, n) 内各相邻元素
      if (A[i-1] > A[i]) {      // 若逆序, 则
        swap(A[i-1], A[i]);     // 令其交换, 同时
        sorted = false;         // 清除 (全局) 有序标志
      }
}

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

template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi) {
  while (!bubble(lo, hi--)); // 逐趟做扫描交换, 直至全序
}

template <typename T>
bool Vector<T>::bubbleSort(Rank lo, Rank hi) {
  bool sorted = true; // 整体有序标志
  while (++lo < hi)                   // 自左向右, 逐一检查各对相邻元素
    if (_elem[lo - 1] > _elem[lo]) {  // 若逆序, 则
      sorted = false;                 // 意味着尚未整体有序, 并需要
      swap(_elem[lo - 1], _elem[lo]); // 交换
    }
  return sorted; // 返回有序标志
} // 乱序限于 [0, √n) 时, 仍需 O(n^{3/2}) 时间 — 按理,  O(n) 应已足矣

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

template <typename T>
void Vector<T>::bubbleSort(Rank lo, Rank hi) {
  while (lo < (hi = bubble(lo, hi))); // 逐趟扫描交换, 直至全序
}

template <typename T>
Rank Vector<T>::bubble(Rank lo, Rank hi) {
  Rank last = lo;   // 最右侧的逆序对初始化为 [lo - 1, lo]
  while (++lo < hi) // 自左向右, 逐一检查各对相邻元素
    if (_elem[lo - 1] > _elem[lo]) {  // 若逆序, 则
      last = lo;                      // 更新最右侧逆序对位置记录, 并
      swap(_elem[lo - 1], _elem[lo]); // 交换
    }
  return last; // 返回最右侧的逆序对位置
} // 前一版本中的逻辑型标志 sorted, 改为秩 last