目錄
- 1.5 排序
- 1.5.1 直接插入排序
- 1.5.2 折半插入排序（順序結構）
- 1.5.3 2—路插入排序（順序結構）
- 1.5.4 折半插入排序（鍊式結構）
- 1.5.5 2—路插入排序（鍊式結構）
- 1.5.6 希爾排序
- 1.5.7 冒泡排序
- 1.5.8 一趟快速排序
- 1.5.9 一趟快速排序的改進算法
- 1.5.10 簡單選擇排序
- 1.5.11 箱子排序
- 1.5.12 樹型選擇排序
- 1.5.13 堆排序
- 1.5.14 歸并排序
- 1.5.15 多路平衡歸并排序
- 1.5.16 置換—選擇排序
- 1.5.17 檔案的歸并
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
#define LT(a, b) ((a)<(b))
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
void InsertSort(SqList *L) { /* 對順序表L作直接插入排序。*/
int i, j;
for (i = 2; i <= (*L).length; ++i)
if LT((*L).r[i].key, (*L).r[i - 1].key) /* "<",需将L.r[i]插入有序子表 */
{
(*L).r[0] = (*L).r[i]; /* 複制為哨兵 */
for (j = i - 1; LT((*L).r[0].key, (*L).r[j].key); --j)
(*L).r[j + 1] = (*L).r[j]; /* 記錄後移 */
(*L).r[j + 1] = (*L).r[0]; /* 插入到正确位置 */
}
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l1;
int i;
for (i = 0; i < N; i++) /* 給l1.r指派 */
l1.r[i + 1] = d[i];
l1.length = N;
printf("排序前:\n");
print(l1);
InsertSort(&l1);
printf("直接插入排序後:\n");
print(l1);
return 0;
}
運作結果
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
#define LT(a, b) ((a)<(b))
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
void BInsertSort(SqList *L) { /* 對順序表L作折半插入排序。*/
int i, j, m, low, high;
for (i = 2; i <= (*L).length; ++i) {
(*L).r[0] = (*L).r[i]; /* 将L.r[i]暫存到L.r[0] */
low = 1;
high = i - 1;
while (low <= high) { /* 在r[low..high]中折半查找有序插入的位置 */
m = (low + high) / 2; /* 折半 */
if LT((*L).r[0].key, (*L).r[m].key)
high = m - 1; /* 插入點在低半區 */
else
low = m + 1; /* 插入點在高半區 */
}
for (j = i - 1; j >= high + 1; --j)
(*L).r[j + 1] = (*L).r[j]; /* 記錄後移 */
(*L).r[high + 1] = (*L).r[0]; /* 插入 */
}
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l1;
int i;
for (i = 0; i < N; i++) /* 給l1.r指派 */
l1.r[i + 1] = d[i];
l1.length = N;
printf("排序前:\n");
print(l1);
BInsertSort(&l1);
printf("折半插入排序後:\n");
print(l1);
return 0;
}
#include <stdio.h> /* EOF(=^Z或F6),NULL */
#include <stdlib.h>
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
#define LT(a, b) ((a)<(b))
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
void P2_InsertSort(SqList *L) { /* 2_路插入排序 */
int i, j, first, final;
RedType *d;
d = (RedType *) malloc((*L).length * sizeof(RedType)); /* 生成L.length個記錄的臨時空間 */
d[0] = (*L).r[1]; /* 設L的第1個記錄為d中排好序的記錄(在位置[0]) */
first = final = 0; /* first、final分别訓示d中排好序的記錄的第1個和最後1個記錄的位置 */
for (i = 2; i <= (*L).length; ++i) { /* 依次将L的第2個～最後1個記錄插入d中 */
if ((*L).r[i].key < d[first].key) { /* 待插記錄小于d中最小值，插到d[first]之前(不需移動d數組的元素) */
first = (first - 1 + (*L).length) % (*L).length; /* 設d為循環向量 */
d[first] = (*L).r[i];
} else if ((*L).r[i].key > d[final].key) { /* 待插記錄大于d中最大值，插到d[final]之後(不需移動d數組的元素) */
final = final + 1;
d[final] = (*L).r[i];
} else { /* 待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動d數組的元素) */
j = final++; /* 移動d的尾部元素以便按序插入記錄 */
while ((*L).r[i].key < d[j].key) {
d[(j + 1) % (*L).length] = d[j];
j = (j - 1 + (*L).length) % (*L).length;
}
d[j + 1] = (*L).r[i];
}
}
for (i = 1; i <= (*L).length; i++) /* 把d賦給L.r */
(*L).r[i] = d[(i + first - 1) % (*L).length]; /* 線性關系 */
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l1;
int i;
for (i = 0; i < N; i++) /* 給l1.r指派 */
l1.r[i + 1] = d[i];
l1.length = N;
printf("排序前:\n");
print(l1);
P2_InsertSort(&l1);
printf("2_路插入排序後:\n");
print(l1);
}
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#define N 8
#define SIZE 100 /* 靜态連結清單容量 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType rc; /* 記錄項 */
int next; /* 指針項 */
} SLNode; /* 表結點類型 */
typedef struct {
SLNode r[SIZE]; /* 0号單元為表頭結點 */
int length; /* 連結清單目前長度 */
} SLinkListType; /* 靜态連結清單類型 */
void TableInsert(SLinkListType *SL, RedType D[], int n) { /* 由數組D建立n個元素的表插入排序的靜态連結清單SL */
int i, p, q;
(*SL).r[0].rc.key = INT_MAX; /* 表頭結點記錄的關鍵字取最大整數(非降序連結清單的表尾) */
(*SL).r[0].next = 0; /* next域為0表示表尾(現為空表，初始化) */
for (i = 0; i < n; i++) {
(*SL).r[i + 1].rc = D[i]; /* 将數組D的值賦給靜态連結清單SL */
q = 0;
p = (*SL).r[0].next;
while ((*SL).r[p].rc.key <= (*SL).r[i + 1].rc.key) { /* 靜态連結清單向後移 */
q = p;
p = (*SL).r[p].next;
}
(*SL).r[i + 1].next = p; /* 将目前記錄插入靜态連結清單 */
(*SL).r[q].next = i + 1;
}
(*SL).length = n;
}
void Arrange(SLinkListType *SL) { /* 根據靜态連結清單SL中各結點的指針值調整記錄位置，使得SL中記錄按關鍵字 */
/* 非遞減有序順序排列*/
int i, p, q;
SLNode t;
p = (*SL).r[0].next; /* p訓示第一個記錄的目前位置 */
for (i = 1; i < (*SL).length; ++i) { /* (*SL).r[1..i-1]中記錄已按關鍵字有序排列,第i個記錄在SL中的目前位置應不小于i */
while (p < i)
p = (*SL).r[p].next; /* 找到第i個記錄，并用p訓示其在SL中目前位置 */
q = (*SL).r[p].next; /* q訓示尚未調整的表尾 */
if (p != i) {
t = (*SL).r[p]; /* 交換記錄，使第i個記錄到位 */
(*SL).r[p] = (*SL).r[i];
(*SL).r[i] = t;
(*SL).r[i].next = p; /* 指向被移走的記錄，使得以後可由while循環找回 */
}
p = q; /* p訓示尚未調整的表尾，為找第i+1個記錄作準備 */
}
}
void Sort(SLinkListType L, int adr[]) { /* 求得adr[1..L.length]，adr[i]為靜态連結清單L的第i個最小記錄的序号 */
int i = 1, p = L.r[0].next;
while (p) {
adr[i++] = p;
p = L.r[p].next;
}
}
void print(SLinkListType L) {
int i;
for (i = 1; i <= L.length; i++)
printf("key=%d ord=%d next=%d\n", L.r[i].rc.key, L.r[i].rc.otherinfo, L.r[i].next);
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SLinkListType l1;
int *adr, i;
TableInsert(&l1, d, N);
printf("排序前:\n");
print(l1);
Arrange(&l1);
printf("l1排序後:\n");
print(l1);
return 0;
}
#include <limits.h> /* INT_MAX等 */
#include <stdio.h> /* EOF(=^Z或F6),NULL */
#include <stdlib.h>
#define N 8
#define SIZE 100 /* 靜态連結清單容量 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType rc; /* 記錄項 */
int next; /* 指針項 */
} SLNode; /* 表結點類型 */
typedef struct {
SLNode r[SIZE]; /* 0号單元為表頭結點 */
int length; /* 連結清單目前長度 */
} SLinkListType; /* 靜态連結清單類型 */
void TableInsert(SLinkListType *SL, RedType D[], int n) { /* 由數組D建立n個元素的表插入排序的靜态連結清單SL */
int i, p, q;
(*SL).r[0].rc.key = INT_MAX; /* 表頭結點記錄的關鍵字取最大整數(非降序連結清單的表尾) */
(*SL).r[0].next = 0; /* next域為0表示表尾(現為空表，初始化) */
for (i = 0; i < n; i++) {
(*SL).r[i + 1].rc = D[i]; /* 将數組D的值賦給靜态連結清單SL */
q = 0;
p = (*SL).r[0].next;
while ((*SL).r[p].rc.key <= (*SL).r[i + 1].rc.key) { /* 靜态連結清單向後移 */
q = p;
p = (*SL).r[p].next;
}
(*SL).r[i + 1].next = p; /* 将目前記錄插入靜态連結清單 */
(*SL).r[q].next = i + 1;
}
(*SL).length = n;
}
void Sort(SLinkListType L, int adr[]) { /* 求得adr[1..L.length]，adr[i]為靜态連結清單L的第i個最小記錄的序号 */
int i = 1, p = L.r[0].next;
while (p) {
adr[i++] = p;
p = L.r[p].next;
}
}
void Rearrange(SLinkListType *L, int adr[]) { /* adr給出靜态連結清單L的有序次序，即L.r[adr[i]]是第i小的記錄。 */
int i, j, k;
for (i = 1; i < (*L).length; ++i)
if (adr[i] != i) {
j = i;
(*L).r[0] = (*L).r[i]; /* 暫存記錄(*L).r[i] */
while (adr[j] != i) { /* 調整(*L).r[adr[j]]的記錄到位直到adr[j]=i為止 */
k = adr[j];
(*L).r[j] = (*L).r[k];
adr[j] = j;
j = k; /* 記錄按序到位 */
}
(*L).r[j] = (*L).r[0];
adr[j] = j;
}
}
void print(SLinkListType L) {
int i;
for (i = 1; i <= L.length; i++)
printf("key=%d ord=%d next=%d\n", L.r[i].rc.key, L.r[i].rc.otherinfo, L.r[i].next);
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SLinkListType l1;
int *adr, i;
TableInsert(&l1, d, N);
printf("排序前:\n");
print(l1);
adr = (int *) malloc((l1.length + 1) * sizeof(int));
Sort(l1, adr);
for (i = 1; i <= l1.length; i++)
printf("adr[%d]=%d ", i, adr[i]);
printf("\n");
Rearrange(&l1, adr);
printf("l1排序後:\n");
print(l1);
return 0;
}
#include<stdio.h>
#define N 10
#define T 3
#define LT(a, b) ((a)<(b))
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
void ShellInsert(SqList *L, int dk) { /* 對順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序相比， */
/* 作了以下修改： */
/* 1.前後記錄位置的增量是dk,而不是1; */
/* 2.r[0]隻是暫存單元,不是哨兵。當j<=0時,插入位置已找到。*/
int i, j;
for (i = dk + 1; i <= (*L).length; ++i)
if LT((*L).r[i].key, (*L).r[i - dk].key) { /* 需将(*L).r[i]插入有序增量子表 */
(*L).r[0] = (*L).r[i]; /* 暫存在(*L).r[0] */
for (j = i - dk; j > 0 && LT((*L).r[0].key, (*L).r[j].key); j -= dk)
(*L).r[j + dk] = (*L).r[j]; /* 記錄後移，查找插入位置 */
(*L).r[j + dk] = (*L).r[0]; /* 插入 */
}
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("%d ", L.r[i].key);
printf("\n");
}
void print1(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
void ShellSort(SqList *L, int dlta[], int t) { /* 按增量序列dlta[0..t-1]對順序表L作希爾排序。*/
int k;
for (k = 0; k < t; ++k) {
ShellInsert(L, dlta[k]); /* 一趟增量為dlta[k]的插入排序 */
printf("第%d趟排序結果: ", k + 1);
print(*L);
}
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8},
{55, 9},
{4, 10}};
SqList l;
int i, dt[T] = {5, 3, 1}; /* 增量序列數組 */
for (i = 0; i < N; i++)
l.r[i + 1] = d[i];
l.length = N;
printf("排序前: ");
print(l);
ShellSort(&l, dt, T);
printf("排序後: ");
print1(l);
return 0;
}
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#define TRUE 1
#define FALSE 0
typedef int Status; /* Status是函數的類型,其值是函數結果狀态代碼，如OK等 */
#define N 8
void bubble_sort(int a[], int n) { /* 将a中整數序列重新排列成自小至大有序的整數序列(起泡排序) */
int i, j, t;
Status change;
for (i = n - 1, change = TRUE; i > 1 && change; --i) {
change = FALSE;
for (j = 0; j < i; ++j)
if (a[j] > a[j + 1]) {
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
change = TRUE;
}
}
}
void print(int r[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", r[i]);
printf("\n");
}
int main() {
int d[N] = {49, 38, 65, 97, 76, 13, 27, 49};
printf("排序前:\n");
print(d, N);
bubble_sort(d, N);
printf("排序後:\n");
print(d, N);
return 0;
}
#include<stdio.h>
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef int InfoType;
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
int Partition(SqList *L, int low, int high) { /* 交換順序表L中子表r[low..high]的記錄，樞軸記錄到位，并傳回其 */
/* 所在位置，此時在它之前（後）的記錄均不大（小）于它。*/
KeyType pivotkey;
(*L).r[0] = (*L).r[low]; /* 用子表的第一個記錄作樞軸記錄 */
pivotkey = (*L).r[low].key; /* 樞軸記錄關鍵字 */
while (low < high) { /* 從表的兩端交替地向中間掃描 */
while (low < high && (*L).r[high].key >= pivotkey)
--high;
(*L).r[low] = (*L).r[high]; /* 将比樞軸記錄小的記錄移到低端 */
while (low < high && (*L).r[low].key <= pivotkey)
++low;
(*L).r[high] = (*L).r[low]; /* 将比樞軸記錄大的記錄移到高端 */
}
(*L).r[low] = (*L).r[0]; /* 樞軸記錄到位 */
return low; /* 傳回樞軸位置 */
}
void QSort(SqList *L, int low, int high) { /* 對順序表L中的子序列L.r[low..high]作快速排序。*/
int pivotloc;
if (low < high) { /* 長度大于1 */
pivotloc = Partition(L, low, high); /* 将L.r[low..high]一分為二 */
QSort(L, low, pivotloc - 1); /* 對低子表遞歸排序，pivotloc是樞軸位置 */
QSort(L, pivotloc + 1, high); /* 對高子表遞歸排序 */
}
}
void QuickSort(SqList *L) { /* 對順序表L作快速排序。*/
QSort(L, 1, (*L).length);
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l;
int i;
for (i = 0; i < N; i++)
l.r[i + 1] = d[i];
l.length = N;
printf("排序前:\n");
print(l);
QuickSort(&l);
printf("排序後:\n");
print(l);
return 0;
}
#include<stdio.h>
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef int InfoType;
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
int Partition(SqList *L, int low, int high) { /* 交換順序表L中子表r[low..high]的記錄，樞軸記錄到位，并傳回其 */
/* 所在位置，此時在它之前（後）的記錄均不大（小）于它。*/
KeyType pivotkey;
(*L).r[0] = (*L).r[low]; /* 用子表的第一個記錄作樞軸記錄 */
pivotkey = (*L).r[low].key; /* 樞軸記錄關鍵字 */
while (low < high) { /* 從表的兩端交替地向中間掃描 */
while (low < high && (*L).r[high].key >= pivotkey)
--high;
(*L).r[low] = (*L).r[high]; /* 将比樞軸記錄小的記錄移到低端 */
while (low < high && (*L).r[low].key <= pivotkey)
++low;
(*L).r[high] = (*L).r[low]; /* 将比樞軸記錄大的記錄移到高端 */
}
(*L).r[low] = (*L).r[0]; /* 樞軸記錄到位 */
return low; /* 傳回樞軸位置 */
}
void QSort(SqList *L, int low, int high) { /* 對順序表L中的子序列L.r[low..high]作快速排序。*/
int pivotloc;
if (low < high) { /* 長度大于1 */
pivotloc = Partition(L, low, high); /* 将L.r[low..high]一分為二 */
QSort(L, low, pivotloc - 1); /* 對低子表遞歸排序，pivotloc是樞軸位置 */
QSort(L, pivotloc + 1, high); /* 對高子表遞歸排序 */
}
}
void QuickSort(SqList *L) { /* 對順序表L作快速排序。*/
QSort(L, 1, (*L).length);
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l;
int i;
for (i = 0; i < N; i++)
l.r[i + 1] = d[i];
l.length = N;
printf("排序前:\n");
print(l);
QuickSort(&l);
printf("排序後:\n");
print(l);
return 0;
}
#include<stdio.h>
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
int SelectMinKey(SqList L, int i) { /* 傳回在L.r[i..L.length]中key最小的記錄的序号 */
KeyType min;
int j, k;
k = i; /* 設第i個為最小 */
min = L.r[i].key;
for (j = i + 1; j <= L.length; j++)
if (L.r[j].key < min) /* 找到更小的 */
{
k = j;
min = L.r[j].key;
}
return k;
}
void SelectSort(SqList *L) { /* 對順序表L作簡單選擇排序。*/
int i, j;
RedType t;
for (i = 1; i < (*L).length; ++i) { /* 選擇第i小的記錄，并交換到位 */
j = SelectMinKey(*L, i); /* 在L.r[i..L.length]中選擇key最小的記錄 */
if (i != j) { /* 與第i個記錄交換 */
t = (*L).r[i];
(*L).r[i] = (*L).r[j];
(*L).r[j] = t;
}
}
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l;
int i;
for (i = 0; i < N; i++)
l.r[i + 1] = d[i];
l.length = N;
printf("排序前:\n");
print(l);
SelectSort(&l);
printf("排序後:\n");
print(l);
return 0;
}
#include "stdio.h"
#define num_arr 5
typedef struct attr {
int key;
char name[10];
} ArrType;
void sort(ArrType A[]) {
int i;
ArrType B[num_arr];
for (i = 0; i < num_arr; i++)
B[A[i].key] = A[i];
for (i = 0; i < num_arr; i++)
printf("%s\n", B[i].name);
}
int main() {
ArrType c[num_arr] = {{4, "John"},
{1, "Jane"},
{0, "Alice"},
{2, "Peter"},
{3, "Tom"}};
sort(c);
return 0;
}
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<math.h> /* floor(),ceil(),abs() */
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
void TreeSort(SqList *L) { /* 樹形選擇排序 */
int i, j, j1, k, k1, l, n = (*L).length;
RedType *t;
l = (int) ceil(log(n) / log(2)) + 1; /* 完全二叉樹的層數 */
k = (int) pow(2, l) - 1; /* l層完全二叉樹的結點總數 */
k1 = (int) pow(2, l - 1) - 1; /* l-1層完全二叉樹的結點總數 */
t = (RedType *) malloc(k * sizeof(RedType)); /* 二叉樹采用順序存儲結構 */
for (i = 1; i <= n; i++) /* 将L.r賦給葉子結點 */
t[k1 + i - 1] = (*L).r[i];
for (i = k1 + n; i < k; i++) /* 給多餘的葉子的關鍵字賦無窮大 */
t[i].key = INT_MAX;
j1 = k1;
j = k;
while (j1) { /* 給非葉子結點指派 */
for (i = j1; i < j; i += 2)
t[i].key < t[i + 1].key ? (t[(i + 1) / 2 - 1] = t[i]) : (t[(i + 1) / 2 - 1] = t[i + 1]);
j = j1;
j1 = (j1 - 1) / 2;
}
for (i = 0; i < n; i++) {
(*L).r[i + 1] = t[0]; /* 将目前最小值賦給L.r[i] */
j1 = 0;
for (j = 1; j < l; j++) /* 沿樹根找結點t[0]在葉子中的序号j1 */
t[2 * j1 + 1].key == t[j1].key ? (j1 = 2 * j1 + 1) : (j1 = 2 * j1 + 2);
t[j1].key = INT_MAX;
while (j1) {
j1 = (j1 + 1) / 2 - 1; /* 序号為j1的結點的雙親結點序号 */
t[2 * j1 + 1].key <= t[2 * j1 + 2].key ? (t[j1] = t[2 * j1 + 1]) : (t[j1] = t[2 * j1 + 2]);
}
}
free(t);
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
SqList l;
int i;
for (i = 0; i < N; i++)
l.r[i + 1] = d[i];
l.length = N;
printf("排序前:\n");
print(l);
TreeSort(&l);
printf("排序後:\n");
print(l);
return 0;
}
#include<stdio.h>
#define N 8
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
#define LT(a, b) ((a)<(b))
typedef SqList HeapType; /* 堆采用順序表存儲表示 */
void HeapAdjust(HeapType *H, int s, int m) { /* 已知H.r[s..m]中記錄的關鍵字除H.r[s].key之外均滿足堆的定義，本函數 */
/* 調整H.r[s]的關鍵字,使H.r[s..m]成為一個大頂堆(對其中記錄的關鍵字而言) */
RedType rc;
int j;
rc = (*H).r[s];
for (j = 2 * s; j <= m; j *= 2) { /* 沿key較大的孩子結點向下篩選 */
if (j < m && LT((*H).r[j].key, (*H).r[j + 1].key))
++j; /* j為key較大的記錄的下标 */
if (!LT(rc.key, (*H).r[j].key))
break; /* rc應插入在位置s上 */
(*H).r[s] = (*H).r[j];
s = j;
}
(*H).r[s] = rc; /* 插入 */
}
void HeapSort(HeapType *H) { /* 對順序表H進行堆排序。*/
RedType t;
int i;
for (i = (*H).length / 2; i > 0; --i) /* 把H.r[1..H.length]建成大頂堆 */
HeapAdjust(H, i, (*H).length);
for (i = (*H).length; i > 1; --i) { /* 将堆頂記錄和目前未經排序子序列H.r[1..i]中最後一個記錄互相交換 */
t = (*H).r[1];
(*H).r[1] = (*H).r[i];
(*H).r[i] = t;
HeapAdjust(H, 1, i - 1); /* 将H.r[1..i-1]重新調整為大頂堆 */
}
}
void print(HeapType H) {
int i;
for (i = 1; i <= H.length; i++)
printf("(%d,%d)", H.r[i].key, H.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7},
{49, 8}};
HeapType h;
int i;
for (i = 0; i < N; i++)
h.r[i + 1] = d[i];
h.length = N;
printf("排序前:\n");
print(h);
HeapSort(&h);
printf("排序後:\n");
print(h);
return 0;
}
#include<stdio.h>
#define N 7
#define LQ(a, b) ((a)<=(b))
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef int InfoType; /* 定義其它資料項的類型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
void Merge(RedType SR[], RedType TR[], int i, int m, int n) { /* 将有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n] */
int j, k, l;
for (j = m + 1, k = i; i <= m && j <= n; ++k) /* 将SR中記錄由小到大地并入TR */
if LQ(SR[i].key, SR[j].key)
TR[k] = SR[i++];
else
TR[k] = SR[j++];
if (i <= m)
for (l = 0; l <= m - i; l++)
TR[k + l] = SR[i + l]; /* 将剩餘的SR[i..m]複制到TR */
if (j <= n)
for (l = 0; l <= n - j; l++)
TR[k + l] = SR[j + l]; /* 将剩餘的SR[j..n]複制到TR */
}
void MSort(RedType SR[], RedType TR1[], int s, int t) { /* 将SR[s..t]歸并排序為TR1[s..t]。*/
int m;
RedType TR2[MAXSIZE + 1];
if (s == t)
TR1[s] = SR[s];
else {
m = (s + t) / 2; /* 将SR[s..t]平分為SR[s..m]和SR[m+1..t] */
MSort(SR, TR2, s, m); /* 遞歸地将SR[s..m]歸并為有序的TR2[s..m] */
MSort(SR, TR2, m + 1, t); /* 遞歸地将SR[m+1..t]歸并為有序的TR2[m+1..t] */
Merge(TR2, TR1, s, m, t); /* 将TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t] */
}
}
void MergeSort(SqList *L) { /* 對順序表L作歸并排序。*/
MSort((*L).r, (*L).r, 1, (*L).length);
}
void print(SqList L) {
int i;
for (i = 1; i <= L.length; i++)
printf("(%d,%d)", L.r[i].key, L.r[i].otherinfo);
printf("\n");
}
int main() {
RedType d[N] = {{49, 1},
{38, 2},
{65, 3},
{97, 4},
{76, 5},
{13, 6},
{27, 7}};
SqList l;
int i;
for (i = 0; i < N; i++)
l.r[i + 1] = d[i];
l.length = N;
printf("排序前:\n");
print(l);
MergeSort(&l);
printf("排序後:\n");
print(l);
return 0;
}
#include <random>
#include <time.h>
#include <vector>
#include <array>
#include <algorithm>
#include <fstream>
#include <string>
#include <iostream>
using namespace std;
//建立待排序檔案 包含10萬個随機生成的整數
void CreateFile() {
ofstream out("test.txt");
default_random_engine e(time(0));
uniform_int_distribution<int> u(0, 100000);
for (int i = 0; i < 100000; i++) {
out << u(e) << endl;
}
out.close();
}
//多路平衡歸并，用來排序整數
const int BuffSize = 10000;//假設最大緩存空間為10000
const int merge_K = 4;//歸并的路數
//一開始使用的内排序算法，對10萬條資料進行排序，生成10個各自包含10000條有序資料的檔案
int InnerSort(string filepath) {
ifstream in(filepath);
ofstream out;
vector<int> list;
int filenum = 0;
string temp;
while (true) {
while (list.size() < BuffSize) {
if (in >> temp) {
list.push_back(stoi(temp));
} else break;
}
if (list.size() == 0)break;
sort(list.begin(), list.end());
out.open("subsection_0_" + to_string(filenum) + ".txt");
for (auto val : list)out << to_string(val) << endl;//寫入資料
out.close();
list.clear();
filenum++;
}
in.close();
return filenum;
}
//敗者樹相關
int Adjust(array<int, merge_K - 1> &lossertree, array<vector<int>::iterator, merge_K + 1> inputbfIterators, int index) {
int winner = index;
index = index + merge_K - 1;
while (index > 0) {
if (*(inputbfIterators[winner]) > *(inputbfIterators[lossertree[(index - 1) / 2]])) {
int temp = winner;
winner = lossertree[(index - 1) / 2];
lossertree[(index - 1) / 2] = temp;
}
index = (index - 1) / 2;
}
return winner;
}
int CreateLosserTree(array<int, merge_K - 1> &lossertree, array<vector<int>::iterator, merge_K + 1> inputbfIterators) {
int winner = 0;
for (int i = lossertree.size() - 1; i >= 0; i--) lossertree[i] = merge_K;
for (int i = 0; i < merge_K; i++) winner = Adjust(lossertree, inputbfIterators, i);
return winner;
}
//K路平衡歸并
void K_Merge_Sort(string filepath) {
int filenum = InnerSort(filepath);
const int buffersSize = BuffSize / (merge_K + 1);//merge_K個讀入資料的buffer，1個寫出資料的buffer
array<vector<int>, merge_K> inputBuffer;
vector<int> minval;
minval.push_back(-1);
array<vector<int>::iterator, merge_K + 1> inputbfIterators;
inputbfIterators[merge_K] = minval.begin();
vector<int> outputBuffer;
int mergenum = 0;
string temp;
while (filenum > 1) {
cout << "第" << mergenum + 1 << "輪歸并" << endl;
for (int i = 0; i < (filenum + merge_K - 1) / merge_K; i++) {
array<ifstream, merge_K> reader;
const int num_in_merge = ((i + 1) * merge_K < filenum) ? merge_K : (filenum % merge_K);//目前同時進行歸并的段數
for (int j = 0; j < merge_K; j++) {
if (j < num_in_merge) {
reader[j].open("subsection_" + to_string(mergenum) + "_" + to_string(i * merge_K + j) + ".txt");
inputBuffer[j].clear();
for (int k = 0; k < buffersSize; k++) {
if (reader[j] >> temp)inputBuffer[j].push_back(stoi(temp));
else break;
}
} else {
inputBuffer[j].push_back(0x3f3f3f3f);
}
inputbfIterators[j] = inputBuffer[j].begin();
}
ofstream writer("subsection_" + to_string(mergenum + 1) + "_" + to_string(i) + ".txt");
outputBuffer.clear();
array<int, merge_K - 1> lossertree;
int winner = CreateLosserTree(lossertree, inputbfIterators);
int value = 0;
while (true) {
for (int j = 0; j < num_in_merge; j++) {
if (inputbfIterators[j] == inputBuffer[j].end()) {
inputBuffer[j].clear();
for (int k = 0; k < buffersSize; k++) {
if (reader[j] >> temp)inputBuffer[j].push_back(stoi(temp));
else {
inputBuffer[j].push_back(0x3f3f3f3f);
break;
}
}
inputbfIterators[j] = inputBuffer[j].begin();
}
}
if (outputBuffer.size() >= buffersSize) {
for (auto item : outputBuffer)writer << to_string(item) << endl;
value += outputBuffer.size();
outputBuffer.clear();
}
winner = Adjust(lossertree, inputbfIterators, winner);
if (*(inputbfIterators[winner]) != 0x3f3f3f3f)outputBuffer.push_back(*(inputbfIterators[winner]++));
else break;
}
if (outputBuffer.size() > 0) {
for (auto item : outputBuffer)writer << to_string(item);
value += outputBuffer.size();
}
cout << "檔案 " << "subsection_" + to_string(mergenum + 1) + "_" + to_string(i) + ".txt 歸并完畢 " << "資料數量"
<< value << endl;
}
filenum = (filenum + merge_K - 1) / merge_K;
mergenum++;
}
}
int main() {
CreateFile();
K_Merge_Sort("test.txt");
}
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include <cstring>
#include <iostream>
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
#define MAXKEY INT_MAX
#define RUNEND_SYMBOL INT_MAX
#define w 6 /* 記憶體工作區可容納的記錄個數 */
#define M 10 /* 設輸出M個資料換行 */
#define N 24 /* 設大檔案有N個資料 */
using namespace std;
typedef int InfoType; /* 定義其它資料項的類型 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
typedef int LoserTree[w]; /* 敗者樹是完全二叉樹且不含葉子，可采用順序存儲結構 */
typedef struct {
RedType rec; /* 記錄 */
KeyType key; /* 從記錄中抽取的關鍵字 */
int rnum; /* 所屬歸并段的段号 */
} RedNode, WorkArea[w]; /* 記憶體工作區，容量為w */
void Select_MiniMax(LoserTree ls, WorkArea wa, int q) { /* 從wa[q]起到敗者樹的根比較選擇MINIMAX記錄，并由q訓示它所在的歸并段 */
int p, s, t;
for (t = (w + q) / 2, p = ls[t]; t > 0; t = t / 2, p = ls[t])
if (wa[p].rnum < wa[q].rnum || wa[p].rnum == wa[q].rnum && wa[p].key < wa[q].key) {
s = q;
q = ls[t]; /* q訓示新的勝利者 */
ls[t] = s;
}
ls[0] = q;
}
void Construct_Loser(LoserTree ls, WorkArea wa, FILE *fi) { /* 輸入w個記錄到記憶體工作區wa,建得敗者樹ls,選出關鍵字最小的記錄并由s訓示 */
/* 其在wa中的位置。*/
int i;
for (i = 0; i < w; ++i)
wa[i].rnum = wa[i].key = ls[i] = 0; /* 工作區初始化 */
for (i = w - 1; i >= 0; --i) {
fread(&wa[i].rec, sizeof(RedType), 1, fi); /* 輸入一個記錄 */
wa[i].key = wa[i].rec.key; /* 提取關鍵字 */
wa[i].rnum = 1; /* 其段号為＂1＂ */
Select_MiniMax(ls, wa, i); /* 調整敗者 */
}
}
void get_run(LoserTree ls, WorkArea wa, int rc, int *rmax, FILE *fi, FILE *fo) { /* 求得一個初始歸并段，fi為輸入檔案指針，fo為輸出檔案指針。*/
int q;
KeyType minimax;
while (wa[ls[0]].rnum == rc) /* 選得的MINIMAX記錄屬目前段時 */
{
q = ls[0]; /* q訓示MINIMAX記錄在wa中的位置 */
minimax = wa[q].key;
fwrite(&wa[q].rec, sizeof(RedType), 1, fo); /* 将剛選得的MINIMAX記錄寫入輸出檔案 */
fread(&wa[q].rec, sizeof(RedType), 1, fi); /* 從輸入檔案讀入下一記錄(改) */
if (feof(fi)) { /* 輸入檔案結束，虛設記錄（屬＂rmax+1＂段） */
wa[q].rnum = *rmax + 1;
wa[q].key = MAXKEY;
} else { /* 輸入檔案非空時 */
wa[q].key = wa[q].rec.key; /* 提取關鍵字 */
if (wa[q].key < minimax) { /* 新讀入的記錄屬下一段 */
*rmax = rc + 1;
wa[q].rnum = *rmax;
} else /* 新讀入的記錄屬目前段 */
wa[q].rnum = rc;
}
Select_MiniMax(ls, wa, q); /* 選擇新的MINIMAX記錄 */
}
}
void Replace_Selection(LoserTree ls, WorkArea wa, FILE *fi, FILE *fo) { /* 在敗者樹ls和記憶體工作區wa上用置換－選擇排序求初始歸并段，fi為輸入檔案 */
/* (隻讀檔案)指針,fo為輸出檔案(隻寫檔案)指針,兩個檔案均已打開。*/
int rc, rmax;
RedType j;
j.key = RUNEND_SYMBOL;
Construct_Loser(ls, wa, fi); /* 初建敗者樹 */
rc = rmax = 1; /* rc訓示目前生成的初始歸并段的段号，rmax訓示wa中關鍵字所屬初始歸并段的最大段号 */
while (rc <= rmax) /* ＂rc=rmax+1＂标志輸入檔案的置換－選擇排序已完成 */
{
get_run(ls, wa, rc, &rmax, fi, fo); /* 求得一個初始歸并段 */
j.otherinfo = rc;
fwrite(&j, sizeof(RedType), 1, fo); /* 将段結束标志寫入輸出檔案 */
rc = wa[ls[0]].rnum; /* 設定下一段的段号 */
}
}
void print(RedType t) {
printf("(%d,%d)", t.key, t.otherinfo);
}
int atoi(char s[]) {
int i, n, sign;
for (i = 0; isspace(s[i]); i++)//跳過空白符;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == ' -')//跳過符号
i++;
for (n = 0; isdigit(s[i]); i++)
n = 10 * n + (s[i] - '0');//将數字字元轉換成整形數字
return sign * n;
}
void itoa(int n, char s[]) {
int i, j, sign;
if ((sign = n) < 0)//記錄符号
n = -n;//使n成為正數
i = 0;
do {
s[i++] = n % 10 + '0';//取下一個數字
} while ((n /= 10) > 0);//删除該數字
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
for (j = i; j >= 0; j--)//生成的數字是逆序的，是以要逆序輸出
printf("%c", s[j]);
}
int main() {
RedType b, a[N] = {{51, 1},
{49, 2},
{39, 3},
{46, 4},
{38, 5},
{29, 6},
{14, 7},
{61, 8},
{15, 9},
{30, 10},
{1, 11},
{48, 12},
{52, 13},
{3, 14},
{63, 15},
{27, 16},
{4, 17},
{13, 18},
{89, 19},
{24, 20},
{46, 21},
{58, 22},
{33, 23},
{76, 24}};
FILE *fi, *fo;
LoserTree ls;
WorkArea wa;
int i, k, j = RUNEND_SYMBOL;
char s[3], fname[4];
fo = fopen("ori", "wb"); /* 以寫的方式打開大檔案ori */
fwrite(a, sizeof(RedType), N, fo); /* 将數組a寫入大檔案ori */
fclose(fo);
fi = fopen("ori", "rb"); /* 以讀的方式重新打開大檔案ori */
printf("大檔案的記錄為:\n");
for (i = 1; i <= N; i++) {
fread(&b, sizeof(RedType), 1, fi); /* 依次将大檔案ori的資料讀入b */
print(b); /* 輸出b的内容 */
if (i % M == 0)
printf("\n");
}
printf("\n");
rewind(fi); /* 使fi的指針重新傳回大檔案ori的起始位置，以便重新讀入記憶體，産生有序的子檔案 */
fo = fopen("out", "wb"); /* 以寫的方式打開初始歸并段檔案out */
Replace_Selection(ls, wa, fi, fo); /* 用置換－選擇排序求初始歸并段 */
fclose(fo);
fclose(fi);
fi = fopen("out", "rb"); /* 以讀的方式重新打開初始歸并段檔案out */
printf("初始歸并段檔案的記錄為:\n");
i = 1;
do {
k = fread(&b, sizeof(RedType), 1, fi); /* 依次将大檔案out的資料讀入b */
if (k == 1) {
print(b); /* 輸出b的内容 */
if (i++ % M == 0)
printf("\n");
}
} while (k == 1);
printf("\n");
rewind(fi); /* 使fi的指針重新傳回大檔案ori的起始位置，以便重新讀入記憶體，産生有序的子檔案 */
k = 0;
while (!feof(fi)) /* 按段輸出初始歸并段檔案out */
{
itoa(k, s); /* 依次生成檔案名f0,f1,… */
strcpy(fname, "f");
strcat(fname, s);
fo = fopen(fname, "wb"); /* 依次以寫的方式打開檔案f0,f1,… */
do {
i = fread(&b, sizeof(RedType), 1, fi);
if (i == 1) /* fread()調用成功 */
{
fwrite(&b, sizeof(RedType), 1, fo); /* 将b寫入檔案f0,f1,… */
if (b.key == j) /* 1個歸并段結束 */
{
k++;
fclose(fo);
break;
}
}
} while (i == 1);
};
fclose(fi);
printf("共産生%d個初始歸并段檔案\n", k);
}
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include <cstring>
typedef int InfoType; /* 定義其它資料項的類型 */
#define MAXSIZE 20 /* 一個用作示例的小順序表的最大長度 */
#define MINKEY INT_MIN
#define MAXKEY INT_MAX
#define k 3 /* k路歸并 */
#define M 10 /* 設輸出M個資料換行 */
typedef int KeyType; /* 定義關鍵字類型為整型 */
typedef struct {
KeyType key; /* 關鍵字項 */
InfoType otherinfo; /* 其它資料項，具體類型在主程中定義 */
} RedType; /* 記錄類型 */
typedef struct {
RedType r[MAXSIZE + 1]; /* r[0]閑置或用作哨兵單元 */
int length; /* 順序表長度 */
} SqList; /* 順序表類型 */
FILE *fp[k + 1]; /* k+1個檔案指針(fp[k]為大檔案指針)，全局變量 */
typedef int LoserTree[k]; /* 敗者樹是完全二叉樹且不含葉子，可采用順序存儲結構 */
typedef RedType ExNode, External[k + 1]; /* 外結點,有改變 */
External b; /* 全局變量 */
void input(int i, KeyType *a) { /* 從第i個檔案(第i個歸并段)讀入該段目前第1個記錄的關鍵字到外結點 */
fread(a, sizeof(KeyType), 1, fp[i]);
}
void output(int i) { /* 将第i個檔案(第i個歸并段)中目前的記錄寫至輸出歸并段 */
ExNode a;
a.key = b[i].key; /* 目前記錄的關鍵字已讀到b[i].key中 */
fread(&a.otherinfo, sizeof(InfoType), 1, fp[i]);
fwrite(&a, sizeof(ExNode), 1, fp[k]);
}
void Adjust(LoserTree ls, int s) { /* 沿從葉子結點b[s]到根結點ls[0]的路徑調整敗者樹。算法11.2 */
int i, t;
t = (s + k) / 2; /* ls[t]是b[s]的雙親結點 */
while (t > 0) {
if (b[s].key > b[ls[t]].key) {
i = s;
s = ls[t]; /* s訓示新的勝者 */
ls[t] = i;
}
t = t / 2;
}
ls[0] = s;
}
void CreateLoserTree(LoserTree ls) { /* 已知b[0]到b[k-1]為完全二叉樹ls的葉子結點，存有k個關鍵字，沿從葉子 */
/* 到根的k條路徑将ls調整成為敗者樹。算法11.3 */
int i;
b[k].key = MINKEY;
for (i = 0; i < k; ++i)
ls[i] = k; /* 設定ls中"敗者"的初值 */
for (i = k - 1; i >= 0; --i) /* 依次從b[k-1]，b[k-2]，…，b[0]出發調整敗者 */
Adjust(ls, i);
}
void K_Merge(LoserTree ls, External b) { /* 利用敗者樹ls将編号從0到k-1的k個輸入歸并段中的記錄歸并到輸出歸并段。 */
/* b[0]至b[k-1]為敗者樹上的k個葉子結點，分别存放k個輸入歸并段中目前 */
/* 記錄的關鍵字。算法11.1 */
int i, q;
for (i = 0; i < k; ++i) /* 分别從k個輸入歸并段讀人該段目前第一個記錄的關鍵字到外結點 */
input(i, &b[i].key);
CreateLoserTree(ls); /* 建敗者樹ls，選得最小關鍵字為b[ls[0]].key */
while (b[ls[0]].key != MAXKEY) {
q = ls[0]; /* q訓示目前最小關鍵字所在歸并段 */
output(q); /* 将編号為q的歸并段中目前（關鍵字為b[q].key）的記錄寫至輸出歸并段 */
input(q, &b[q].key); /* 從編号為q的輸入歸并段中讀人下一個記錄的關鍵字 */
Adjust(ls, q); /* 調整敗者樹，選擇新的最小關鍵字 */
}
output(ls[0]); /* 将含最大關鍵字MAXKEY的記錄寫至輸出歸并段 */
}
void print(RedType t) {
printf("(%d,%d)", t.key, t.otherinfo);
}
void itoa(int n, char s[]) {
int i, j, sign;
if ((sign = n) < 0)//記錄符号
n = -n;//使n成為正數
i = 0;
do {
s[i++] = n % 10 + '0';//取下一個數字
} while ((n /= 10) > 0);//删除該數字
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
for (j = i; j >= 0; j--)//生成的數字是逆序的，是以要逆序輸出
printf("%c", s[j]);
}
int main() {
RedType r;
int i, j;
char fname[k][4], fout[5] = "out", s[3];
LoserTree ls;
for (i = 0; i < k; i++) { /* 依次打開f0,f1,f2,…,k個檔案 */
itoa(i, s); /* 生成k個檔案名f0,f1,f2,… */
strcpy(fname[i], "f");
strcat(fname[i], s);
fp[i] = fopen(fname[i], "rb"); /* 以讀的方式打開檔案f0,f1,… */
printf("有序子檔案f%d的記錄為:\n", i);
do {
j = fread(&r, sizeof(RedType), 1, fp[i]); /* 依次将f0,f1,…的資料讀入r */
if (j == 1)
print(r); /* 輸出r的内容 */
} while (j == 1);
printf("\n");
rewind(fp[i]); /* 使fp[i]的指針重新傳回f0,f1,…的起始位置，以便重新讀入記憶體 */
}
fp[k] = fopen(fout, "wb"); /* 以寫的方式打開大檔案fout */
K_Merge(ls, b); /* 利用敗者樹ls将k個輸入歸并段中的記錄歸并到輸出歸并段，即大檔案fout */
for (i = 0; i <= k; i++)
fclose(fp[i]); /* 關閉檔案f0,f1,…和檔案fout */
fp[k] = fopen(fout, "rb"); /* 以讀的方式重新打開大檔案fout驗證排序 */
printf("排序後的大檔案的記錄為:\n");
i = 1;
do {
j = fread(&r, sizeof(RedType), 1, fp[k]); /* 将fout的資料讀入r */
if (j == 1)
print(r); /* 輸出r的内容 */
if (i++ % M == 0)
printf("\n"); /* 換行 */
} while (j == 1);
printf("\n");
fclose(fp[k]); /* 關閉大檔案fout */
return 0;
}
Talk is cheap. Show me the code