C++数据结构-实验4-查找和排序算法实现_数据结构实验查找与排序--排序算法的实现

实验四 查找和排序算法实现

1、各种排序算法的实现

用随机函数生成 16 个 2 位正整数(10~99)，实现插入排序、希尔排序、冒泡排序、
快速排序、选择排序、堆排序、二路归并排序等多种排序算法，输出排序中间过程、统
计关键字的比较次数和记录的移动次数。
比较次数和移动次数，其实我也不懂的，经供参考

#include<iostream>
#include<iomanip>
#include<cstdio>
using namespace std;
//插入排序，从数组下标1开始
void swap(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}
void show(int* a, int n) {
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << endl;
}
//插入排序
void insertion_sort(int* a, int n) {
    int compare = 0, move = 0;
    for (int i = 2; i <= n; i++) {
        int key = a[i], j = i - 1;
        while (j > 0 && a[j] > key) {
            a[j + 1] = a[j];
            compare++;
            --j;
        }
        a[j + 1] = key;
        compare++;
        move++;
        cout << "第" << move << "次移动的中间过程:";
        show(a, n);
    }
    cout << "关键字的比较次数:" << compare << endl;
    cout << "记录的移动次数:" << 3 * move << endl;
}
//希尔排序，将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
//对这些子序列进行插入排序；减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。
void shell_sort(int* a, int n) {
    int compare = 0, move = 0, cnt = 0, h = 1;
    while (h < n / 3) h = 3 * h + 1;
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                compare++;
                swap(a[j], a[j - h]);
                move++;
            }
            cnt++;
            cout << "第" << cnt << "次移动的中间过程:";
            for (int i = 0; i < n; i++)cout << a[i] << " ";
            cout << endl;
        }
        h = h / 3;
    }
    cout << "关键字的比较次数:" << compare << endl;
    cout << "记录的移动次数:" << 3 * move << endl;
}
//冒泡排序，从数组下标1开始
//每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换
void bubble_sort(int* a, int n) {
    int compare = 0, move = 0, flag = 1;
    while (flag) {
        flag = 0;
        for (int i = 1; i <= n - 1; i++) {
            if (a[i] > a[i + 1]) {
                flag = 1;
                swap(a[i], a[i + 1]);
                move++;
                cout << "第" << move << "次移动的中间过程:";
                show(a, n);
            }
            compare++;
        }
    }
    cout << "关键字的比较次数:" << compare << endl;
    cout << "记录的移动次数:" << 3 * move << endl;
}
//双向冒泡
void debubble_sort(int* a, int n) {
    int compare = 0, move = 0, cnt = 0;
    int left = 1, right = n,shift=1;
    while (left < right) {
        for (int i = left; i < right; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                move++;
                shift = i;
            }
            compare++;
        }
        right = shift;
        for (int i = right - 1; i >= left; i--) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                move++;
                shift = i + 1;
            }
            compare++;
        }
        left = shift;
        cout << "第" << ++cnt << "次移动的中间过程:";
        show(a, 16);    
    }
    cout << "关键字的比较次数:" << compare << endl;
    cout << "记录的移动次数:" << 3 * move << endl;
}
//快速排序
//要把数列分成两个部分，可选择一个特殊下标的值为基准，然后保证前一个子数列中的数都小于后一个子数列中的数，即是可交换
//后再分成前后两个序列，而是在分的过程中要保证相对大小关系，分别进行快速排序，且不用合并，因为此时数列已经完全有序
int quick_sort_compare = 0, quick_sort_move = 0, quick_sort_cnt = 0;
void quick_sort(int* &a, int left, int right) {
    if (left >= right)return;
    int i = left, j = right, base = a[left];
    while (i < j) {
        while (a[j] >= base && i < j)j--, quick_sort_compare++;
        while (a[i] <= base && i < j)i++, quick_sort_compare++;
        if (i < j) {
            swap(a[i], a[j]);
            quick_sort_move++;
        }
    }
    a[left] = a[i];
    a[i] = base;
    cout << "第" << ++quick_sort_cnt << "次中间过程输出:";
    show(a, 16);
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}
//选择排序，从数组下标1开始，每次找出第 i小的元素然后将这个元素与数组第 i个位置上的元素交换。
void selection_sort(int* a, int n) {
    int compare = 0, move = 0;
    for (int i = 1; i <= n - 1; i++) {
        int k = i;
        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[k]) {
                k = j;
            }
            compare++;
        }
        if (i != k) {
            swap(a[i], a[k]);
            move++;
            cout << "第" << move << "次移动的中间过程:";
            show(a, n);
        }
    }
    cout << "关键字的比较次数:" << compare << endl;
    cout << "记录的移动次数:" << 3 * move << endl;
}
//堆排序,从上往下把左右孩子和邻接根节点交换的成当前子树的根节点
int heap_sort_compare = 0, heap_sort_move = 0;
void max_heapmodify(int* a, int l, int r) {
    int fa = l, son = 2 * fa + 1, temp = a[l];
    while (son < r) {
        heap_sort_compare++;
        if (son + 1 < r && a[son] < a[son + 1])son++;
        heap_sort_compare++;
        if (a[son] < a[fa])return;   //子树中较大的节点都小于当前子树的根节点
        else {
            swap(a[son], a[fa]);  //子树中最大的节点与当前子树的根节点进行交换
            fa = son;             //转移根节点的下标到下一层
            son = fa * 2 + 1;
            cout << "第" << heap_sort_move++ << "次移动的中间过程:";
            for (int i = 0; i < 16; i++)cout << a[i] << " ";
            cout << endl;
        }
    }
}
//堆排序，利用 "堆" 这种数据结构所设计的一种排序算法
void heap_sort(int* a, int n) {
    //对原数列建大根堆
    for (int i = n / 2 - 1; i >= 0; i--)max_heapmodify(a, i, n);
    //逆序递减下标，交换堆顶元素下标为0和当前未再次调整堆最底的元素，再次重新向上调整
    for (int i = n - 1; i >= 1; i--) {
        swap(a[0], a[i]);
        max_heapmodify(a, 0, i);
    }
    //for (int i = 0; i < n; i++)cout << a[i] << " ";
    cout << "关键字的比较次数:" << heap_sort_compare << endl;
    cout << "记录的移动次数:" << 3 * heap_sort_move << endl;
}
//二路归并排序
//把数列分划为两部分，直到数列长度为1；递归地分别对两个子序列进行交换排序；再把当前已经排好序的数列合并成一个子序列
int merge_compare = 0, merge_move = 0, merge_cnt = 0, merge_ans = 0, t[17];
void merge(int*&a,int left, int right) {
    if (right - left <= 1) return;
    int mid = (left + right) / 2;
    //把数列分划为两部分
    merge(a,left, mid);
    merge(a,mid, right);
    cout << "第" << ++merge_cnt << "次中间过程输出:";
    show(a, 16);
    //递归地分别对两个子序列进行交换排序
    int p = left, q = mid, s = left;
    while (s < right) {
        if (p >= mid || (q < right && a[p] > a[q])) {
            t[s++] = a[q++];
            merge_ans += mid - p;
            merge_move++;
        }
        else t[s++] = a[p++];
        merge_compare++;
    }
    //再把当前已经排好序的数列合并成一个子序列
    for (int i = left; i < right; ++i) a[i] = t[i];
}

int main() {
    int* a = new int[18],*b=new int[18];
    for (int i = 1; i <= 16; i++) {
        a[i] = rand() % 90 + 10;
        b[i] = a[i];
    }
    cout << "插入排序：" << endl;
    insertion_sort(b, 16);
    cout << endl;
    
    for (int i = 0; i < 16; i++) b[i] = a[i+1];
    cout << "希尔排序：" << endl;
    shell_sort(b, 16);
    cout << endl;
    cout << "冒泡排序：" << endl;
    for (int i = 1; i <= 16; i++) b[i] = a[i];
    bubble_sort(b, 16);
    cout << endl;
    cout << "双向冒泡排序：" << endl;
    for (int i = 1; i <= 16; i++) b[i] = a[i];
    debubble_sort(b, 16);
    cout << endl;
    cout << "快速排序：" << endl;
    for (int i = 1; i <= 16; i++) b[i] = a[i];
    quick_sort(b,1,16);
    cout << "关键字的比较次数:" << quick_sort_compare << endl;
    cout << "记录的移动次数:" << 3 * quick_sort_move << endl;
    cout << endl;
    for (int i = 1; i <= 16; i++) b[i] = a[i];
    cout << "选择排序：" << endl;
    selection_sort(b, 16);
    cout << endl;
    cout << "堆排序：" << endl;
    for (int i = 0; i < 16; i++) b[i] = a[i + 1]; b[16] = 0;
    heap_sort(b, 16);
    cout << endl;
    cout << "二路归并排序：" << endl;
    for (int i = 1; i <= 16; i++) b[i] = a[i];
    merge(b, 1, 16);
    cout << "关键字的比较次数:" << merge_compare << endl;
    cout << "记录的移动次数:" << 3 * merge_move << endl;
    cout << "记录的逆序对的个数:" << merge_ans << endl;
	return 0;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250

2、各种查找算法实现

(1) 顺序查找：使用数组或链表结构。用随机函数生成 16 个不重复的字母(’a’~’z’)，
键盘输入待查找的字母，返回查找成功与否，若成功则返回该字母所在的位置(序号)，
并计算比较次数。
(2) 折半查找：用数组实现，查找前元素先排序。计算比较次数。分别用查找成功、
不成功进行测试。
(3) 二叉查找树：手工输入 10 个字母，生成一棵二叉查找树，用递归算法打印树结
构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次
数，并删除该字母。分别用查找成功、不成功进行测试。

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//顺序链表
struct List {
    char c;
    List* next;
}*head;
int compare = 0;
//判断数据tc是否在顺序链表中
bool inexistence(List*& head, char tc) {
    bool flag = true;
    List* list = head->next;
    while (list != NULL) {
        if (list->c == tc) {
            flag = false; break;
        }
        list = list->next;
    }
    return flag;
}
//顺序表初始化
void sequence_init(List*& head) {
    List* list = head;
    int cnt = 0;
    while (1) {
        char tc = 'a' + rand() % 26;
        if (inexistence(head, tc)) {
            List* node = new List();
            node->c = tc;
            list->next = node;
            list = node;
            cout << tc << " ";
            cnt++;
        }
        if (cnt >= 16) {
            break;
        }
    }
    list->next = NULL;
    cout << endl;
}
//顺序查找
bool sequence_search(List*& head, char tc) {
    List* list = head->next;
    bool flag = false;
    while (list != NULL) {
        compare++;
        if (list->c == tc) {
            flag = true; break;
        }
        list = list->next;
    }
    return flag;
}
//折半查找初始化
void binary_seacher_init(int*& a, int n) {
    for (int i = 1; i <= n; i++) {
        a[i] = rand() % 100 + 1;
        cout << a[i] << " ";
    }
    cout << endl;
}
//折半查找前需排序
void binary_seacher_sort(int*& a, int n) {
    for (int i = 1; i <= n - 1; i++) {
        int k = i;
        for (int j = i + 1; j <= n; j++)
            if (a[j] < a[k]) k = j;
        int temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
    for (int i = 1; i <= n; i++)cout << a[i] << " ";
    cout << endl;
}
//折半查找
bool binary_search(int*& a, int n, int ta) {
    bool flag = false;
    int left = 1, right = n;
    while (left < right) {
        compare++;
        int mid = (left + right) >> 1;
        if (a[mid] == ta) {
            flag = true; break;
        }
        else if (a[mid] > ta) {
            right = mid - 1;
        }
        else if (a[mid] < ta) {
            left = mid + 1;
        }
    }
    return flag;
}

//二叉查找树
struct TreeNode {
    unsigned char c;
    TreeNode* left, * right;
    TreeNode() {
        left = NULL; right = NULL;
    }
    char getc() { return c; }
};
//二叉查找树插入数据
TreeNode* InsertTree(TreeNode*& T, unsigned char tc) {
    if (T == NULL) {
        TreeNode* tmpNode = new TreeNode();
        tmpNode->c = tc;
        T = tmpNode;
        return T;
    }
    else if (tc < T->c)
        T->left = InsertTree(T->left, tc);
    else if (tc > T->c)
        T->right = InsertTree(T->right, tc);
    return T;
}
//二叉查找树先序遍历
void PreOrder(TreeNode* T) {
    if (T != NULL) {
        cout << T->getc() << " ";
        PreOrder(T->left);
        PreOrder(T->right);
    }
}
//二叉查找树中序遍历
void InOrder(TreeNode* T) {
    if (T != NULL) {
        InOrder(T->left);
        cout << T->c << " ";
        InOrder(T->right);
    }
}
//二叉查找树后序遍历
void PostOrder(TreeNode* T) {
    if (T != NULL) {
        PostOrder(T->left);
        PostOrder(T->right);
        cout << T->c << " ";
    }
}
//二叉查找树查找某结点
TreeNode* binaryTree_search(TreeNode* T, unsigned char key) {
    compare++;
    if (T == NULL || T->c == key)return T;
    else if (T->c > key) return binaryTree_search(T->left, key);
    else return binaryTree_search(T->right, key);
    return T;
}
//二叉查找树查找某结点的父节点
TreeNode* binaryTree_search_father(TreeNode* T, TreeNode* fa, unsigned char key) {
    if (T == NULL || T->c == key)return fa;
    else if (T->c > key) return binaryTree_search_father(T->left, T, key);
    else return binaryTree_search_father(T->right, T, key);
}
//二叉查找树删除某结点(数据)
void binaryTree_remove(TreeNode*& T, unsigned char key) {
    TreeNode* p = binaryTree_search(T, key); //找到需要删除的当前节点
    TreeNode* fa = binaryTree_search_father(T, T, key); //找到需要删除当前节点的父节点
    if (p == NULL) {
        cout << "删除失败";
        return;
    }
    //左右子树都空
    if (p->left == NULL && p->right == NULL) {
        if (fa->left->c == p->c)fa->left = NULL;
        else fa->right = NULL;
        delete p;
    }
    //左子树空
    else if (p->left == NULL) {
        p->c = p->right->c;
        p->right = p->right->right;
    }
    //右子树空
    else if (p->right == NULL) {
        p->c = p->left->c;
        p->left = p->left->left;
    }
    //左右子树都不空
    else {
        TreeNode* pre = p, * node = p->left;
        //找到左子树中最右的节点
        while (node->right) {
            pre = node;
            node = node->right;
        }
        if (pre == p) {
            p->c = node->c;
            p->left = node->left;
        }
        else {
            pre->right = node->left;
            p->c = node->c;
        }
        delete node;
    }
    cout << "删除成功";
}
int main() {
    //链式顺序查找
    head = new List();
    head->next = NULL;
    cout << "顺序查询的原数组：";
    sequence_init(head);
    char tc = 'a';
    compare = 0;
    cout << "顺序查询\"" << tc << "\":";
    if (sequence_search(head, tc))
        cout << "存在，序号为：" << compare - 1 << "比较次数：" << compare;
    else cout << "不存在";
    cout << endl;
    tc = 'z';
    compare = 0;
    cout << "顺序查询\"" << tc << "\":";
    if (sequence_search(head, tc))
        cout << "存在，序号为：" << compare - 1 << "比较次数：" << compare;
    else cout << "不存在";
    cout << endl;
    cout << endl;

    //折半查找
    int* a = new int[11];
    cout << "折半查找的原数组：";
    binary_seacher_init(a, 10);
    cout << "折半查找排序后的数组：";
    binary_seacher_sort(a, 10);
    int ta = 22;
    compare = 0;
    cout << "折半查找\"" << ta << "\":";
    if (binary_search(a, 10, ta))
        cout << "存在，比较次数：" << compare;
    else cout << "不存在";
    cout << endl;
    ta = 24;
    compare = 0;
    cout << "折半查找\"" << ta << "\":";
    if (binary_search(a, 10, ta))
        cout << "存在";
    else cout << "不存在";
    cout << endl;
    cout << endl;

    //二叉查找树
    //tree = new TreeNode();
    TreeNode* tree = NULL;
    cout << "输出原始字符数据：";
    //初始化二叉查找树
    for (int i = 0; i < 10; i++) {
        char c = char('a' + rand() % 26);
        cout << c << " ";
        InsertTree(tree, c);
    }
    cout << endl;
    cout << "二叉查找树先序遍历：";
    PreOrder(tree);
    cout << endl;
    cout << "二叉查找树中序遍历：";
    InOrder(tree);
    cout << endl;
    cout << "二叉查找树后序遍历：";
    PostOrder(tree);
    cout << endl;
    char key = 'b';    compare = 0;
    cout << "待查找的字符" << key << "：";
    if (binaryTree_search(tree, key))
        cout << "存在，比较次数：" << compare;
    else cout << "不存在";
    cout << endl;
    key = 'd';     compare = 0;
    cout << "待查找的字符" << key << "：";
    if (binaryTree_search(tree, key))
        cout << "存在，比较次数：" << compare;
    else cout << "不存在";
    cout << endl;
    key = 'n';
    cout << "待删除的字符" << key << "：";
    binaryTree_remove(tree, key);
    cout << endl;
    cout << "二叉查找树删除后的先序遍历：";
    PreOrder(tree);
    cout << endl;
    key = 'a';
    cout << "待删除的字符" << key << "：";
    binaryTree_remove(tree, key);
    cout << endl;
    cout << "二叉查找树删除后的先序遍历：";
    PreOrder(tree);
    cout << endl;
    return 0;
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297