跳转至

錦標賽排序

本頁面將簡要介紹錦標賽排序。

定義

錦標賽排序（英文：Tournament sort），又被稱為樹形選擇排序，是 選擇排序 的優化版本，堆排序 的一種變體（均採用完全二叉樹）。它在選擇排序的基礎上使用優先隊列查找下一個該選擇的元素。

引入

錦標賽排序的名字來源於單敗淘汰制的競賽形式。在這種賽制中有許多選手參與比賽，他們兩兩比較，勝者進入下一輪比賽。這種淘汰方式能夠決定最好的選手，但是在最後一輪比賽中被淘汰的選手不一定是第二好的——他可能不如先前被淘汰的選手。

過程

以 最小錦標賽排序樹 為例：

tournament-sort1

待排序元素是葉子節點顯示的元素。紅色邊顯示的是每一輪比較中較小的元素的勝出路徑。顯然，完成一次＂錦標賽＂可以選出一組元素中最小的那一個。

每一輪對 \(n\) 個元素進行比較後可以得到 \(\frac{n}{2}\) 個「優勝者」，每一對中較小的元素進入下一輪比較。如果無法湊齊一對元素，那麼這個元素直接進入下一輪的比較。

tournament-sort2

完成一次「錦標賽」後需要將被選出的元素去除。直接將其設置為 \(\infty\)（這個操作類似 堆排序），然後再次舉行「錦標賽」選出次小的元素。

之後一直重複這個操作，直至所有元素有序。

性質

穩定性

錦標賽排序是一種不穩定的排序算法。

時間複雜度

錦標賽排序的最優時間複雜度、平均時間複雜度和最壞時間複雜度均為 \(O(n\log n)\)。它用 \(O(n)\) 的時間初始化「錦標賽」，然後用 \(O(\log n)\) 的時間從 \(n\) 個元素中選取一個元素。

空間複雜度

錦標賽排序的空間複雜度為 \(O(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
int n, a[maxn], tmp[maxn << 1];

int winner(int pos1, int pos2) {
  int u = pos1 >= n ? pos1 : tmp[pos1];
  int v = pos2 >= n ? pos2 : tmp[pos2];
  if (tmp[u] <= tmp[v]) return u;
  return v;
}

void creat_tree(int &value) {
  for (int i = 0; i < n; i++) tmp[n + i] = a[i];
  for (int i = 2 * n - 1; i > 1; i -= 2) {
    int k = i / 2;
    int j = i - 1;
    tmp[k] = winner(i, j);
  }
  value = tmp[tmp[1]];
  tmp[tmp[1]] = INF;
}

void recreat(int &value) {
  int i = tmp[1];
  while (i > 1) {
    int j, k = i / 2;
    if (i % 2 == 0 && i < 2 * n - 1)
      j = i + 1;
    else
      j = i - 1;
    tmp[k] = winner(i, j);
    i = k;
  }
  value = tmp[tmp[1]];
  tmp[tmp[1]] = INF;
}

void tournament_sort() {
  int value;
  creat_tree(value);
  for (int i = 0; i < n; i++) {
    a[i] = value;
    recreat(value);
  }
}

 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
n = 0
a = [0] * maxn
tmp = [0] * maxn * 2

def winner(pos1, pos2):
    u = pos1 if pos1 >= n else tmp[pos1]
    v = pos2 if pos2 >= n else tmp[pos2]
    if tmp[u] <= tmp[v]:
        return u
    return v

def creat_tree():
    for i in range(0, n):
        tmp[n + i] = a[i]
    for i in range(2 * n -1, 1, -2):
        k = int(i / 2)
        j = i - 1
        tmp[k] = winner(i, j)
    value = tmp[tmp[1]]
    tmp[tmp[1]] = INF
    return value

def recreat():
    i = tmp[1]
    while i > 1:
        j = k = int(i / 2)
        if i % 2 == 0 and i < 2 * n - 1:
            j = i + 1
        else:
            j = i - 1
        tmp[k] = winner(i, j)
        i = k
    value = tmp[tmp[1]]
    tmp[tmp[1]] = INF
    return value

def tournament_sort():
    value = creat_tree()
    for i in range(0, n):
        a[i] = value
        value = recreat()

外部鏈接

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用