十大排序和搜索算法的代码示例

大二学习十大排序和搜索时完成的代码#include iostream #includestring #include algorithm #include random #include ctime #include cmath #include vector #include queue #include list #include iomanip using namespace std; // 辅助函数打印数组内容 templatetypename T void printVector(vectorT vec) { for (T weight : vec) { cout weight ; } cout endl; } // 插入排序 void insertionSort(vectorint arr, int comparisons, int movements) { comparisons movements 0; for (int i 1; i arr.size(); i) { // arr[0]-arr[i - 1]是有序的将arr[i]插入有序序列 // 寻找插入位置找第一个大于arr[i]的数的位置如果不存在就插入到arr[i] int key arr[i]; // 临时存储待插数据 int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; --j; comparisons; movements; } arr[j 1] key; //覆盖回来 movements; //1次移动操作 } } //折半插入排序 void BinaryInsertionSort(vectorint arr, int comparisons, int movements) { for (int i 1; i arr.size(); i) { int key arr[i]; int left 0, right i - 1; // 折半查找合适的插入位置 while (left right) { int mid left (right - left) / 2; comparisons; if (arr[mid] key) { right mid - 1; } else { left mid 1; } } for (int j i - 1; j left; --j) { arr[j 1] arr[j]; } // 插入元素 arr[left] key; movements; //1次移动操作 } } // 冒泡排序 void bubbleSort(vectorint arr, int comparisons, int movements) { int n arr.size(); comparisons movements 0; // 初始化比较次数和移动次数为0 for (int i 0; i n - 1; i) // 外层循环控制排序轮数 { for (int j 0; j n - i - 1; j) // 内层循环进行相邻元素的比较和交换 { comparisons; // 每次比较计数加1 if (arr[j] arr[j 1]) { cout 交换 arr[j] 和 arr[j 1] endl; swap(arr[j], arr[j 1]); //交换两个元素 movements 3; //每次交换视为3次移动操作 } } // 输出当前轮次排序后的数组状态 cout 一轮结束当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30,-) endl; } } // 选择排序 void selectionSort(vectorint arr, int comparisons, int movements) { int n arr.size(); comparisons movements 0; // 初始化比较次数和移动次数为0 for (int i 0; i n - 1; i) // 外层循环选择每轮的最小值 { int minIdx i; // 假设当前元素为最小值 for (int j i 1; j n; j) // 遍历未排序部分 { comparisons; // 每次比较计数加1 if (arr[j] arr[minIdx]) // 如果找到更小的值更新最小值索引 { minIdx j; cout 最小值下标更新为 j endl; } } if (minIdx ! i) // 如果最小值索引发生变化交换元素 { cout 交换 arr[i] 和 arr[minIdx] endl; swap(arr[i], arr[minIdx]); movements 3; // 每次交换视为3次移动操作 } // 输出当前轮次排序后的数组状态 cout 一轮结束当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30,-) endl; } } // 快速排序 void quickSort(vectorint arr, int low, int high, int comparisons, int movements) { if (low high) return; int i low, j high;// 接受传入的数据a为左边界b为右边界 // int mid c[(a b) / 2];// 取中间位置上的值作为基准数 int mid low rand() % (high - low 1); // mid是分块的阈值而不是对应下标的值但是对mid赋值时mid的数据范围仍然是n以内 // 这就导致如果分块的时候数组里面的数据过大就会永远大于mid然后就无限递归了,因此在判断时需要将mid改为arr[mid] int pivot arr[mid]; // 存储基准值 cout low: low high: high endl; cout 索引为 mid 基准值为 arr[mid] endl; while (i j) { while (arr[i] pivot) i, comparisons; //左范围找一个不小于mid的数 while (arr[j] pivot) j--, comparisons; //右范围找一个不大于mid的数 if (i j) { swap(arr[i], arr[j]); cout 交换了 i 中的 arr[i] 和 j 中的 arr[j] endl; i, j--; movements 3; } } cout 分区结束当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30, -) endl; if (low j) quickSort(arr, low, j, comparisons, movements); //在[low,j]的区间左区间里面进行排序 if (i high) quickSort(arr, i, high, comparisons, movements); //在[i,high]的区间右区间里面进行排序 } // 希尔排序 void shellSort(vectorint arr, int comparisons, int movements) { int n arr.size(); comparisons movements 0; // 初始化比较次数和移动次数为0 for (int gap n / 2; gap 0; gap / 2) // 动态设置步长逐步缩小 { cout 此时步长为 gap endl; for (int i gap; i n; i) // 从步长开始对每组进行插入排序 { int temp arr[i]; // 暂存待插入元素 cout 待插数值为 temp endl; int j; for (j i; j gap arr[j - gap] temp; j - gap) { cout 交换位置为 j - gap 和 j endl; arr[j] arr[j - gap]; comparisons; // 比较计数加1 movements; // 移动计数加1 } arr[j] temp; // 插入元素 movements; // 插入操作计为一次移动 cout 一次比较结束 endl; } // 输出当前步长排序后的数组状态 cout 当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30, -) endl; } } // 堆排序 void heapify(vectorint arr, int n, int i, int comparisons, int movements) { int largest i; // 假设当前节点为最大值 int left 2 * i 1; // 左子节点索引 int right 2 * i 2; // 右子节点索引 cout 父结点为 i endl; if (left n arr[left] arr[largest]) // 如果左子节点更大 { largest left; comparisons; } if (right n arr[right] arr[largest]) // 如果右子节点更大 { largest right; comparisons; } if (largest left) cout 左孩子比父结点大 endl; else if (largest right) cout 右孩子比父结点大 endl; else cout 父结点大 endl; if (largest ! i) // 如果最大值发生变化交换并递归调整 { cout 交换 arr[i] 和 arr[largest] endl; swap(arr[i], arr[largest]); movements 3; heapify(arr, n, largest, comparisons, movements); } } void heapSort(vectorint arr, int comparisons, int movements) { int n arr.size(); comparisons movements 0; // 初始化比较次数和移动次数为0 // 构建大根堆 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i, comparisons, movements); cout 当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30, -) endl; } cout 大根堆创建完毕接下来从叶子结点开始逐个化成有序序列 endl; cout string(30, -) endl; // 逐步将最大值移到数组末尾并重新调整堆 for (int i n - 1; i 0; i--) { cout 交换 arr[0] 和 arr[i] endl; swap(arr[0], arr[i]); movements 3; heapify(arr, i, 0, comparisons, movements); cout 当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30, -) endl; } } // 归并排序 void merge(vectorint arr, int l, int m, int r, int comparisons, int movements) { int n1 m - l 1; // 左区间长度 int n2 r - m; // 右区间长度 vectorint L(n1), R(n2); // 创建临时数组存储左右区间 cout 此时左区间为 [ l , m ], 右区间为 [ (m 1) , r ] endl; // 复制数据到临时数组 for (int i 0; i n1; i) L[i] arr[l i]; for (int i 0; i n2; i) R[i] arr[m 1 i]; int i 0, j 0, k l; // 初始化指针 while (i n1 j n2) // 比较左右区间元素将较小者插入数组 { comparisons; // 比较次数加1 if (L[i] R[j]) // 左区间元素较小 { arr[k] L[i]; } else // 右区间元素较小 { arr[k] R[j]; } movements; // 移动次数加1 } // 将剩余的左区间元素复制回数组 while (i n1) { arr[k] L[i]; movements; } // 将剩余的右区间元素复制回数组 while (j n2) { arr[k] R[j]; movements; } // 输出当前合并结果 cout 排序结束当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30, -) endl; } void mergeSort(vectorint arr, int l, int r, int comparisons, int movements) { if (l r) return; // 区间只有一个元素时返回 int m l (r - l) / 2; // 计算中点防止溢出 mergeSort(arr, l, m, comparisons, movements); // 递归排序左半部分 mergeSort(arr, m 1, r, comparisons, movements); // 递归排序右半部分 merge(arr, l, m, r, comparisons, movements); // 合并左右区间 } // 基数排序 void countingSort(vectorint arr, int exp, int comparisons, int movements) { int n arr.size(); vectorint output(n); // 存储排序结果 vectorint count(10, 0); // 计数数组大小为10十进制 for (int i 0; i n; i) // 根据当前位数对元素计数 { count[(arr[i] / exp) % 10]; cout ((arr[i] / exp) % 10) 号桶放入一个元素 endl; } for (int i 1; i 10; i) // 计算前缀和得到每个桶的起始位置 { count[i] count[i - 1]; } for (int num : count) cout num ; // 输出计数数组状态 cout endl; cout string(30, -) endl; for (int i n - 1; i 0; i--) // 倒序遍历原数组将元素放入对应桶中 { output[count[(arr[i] / exp) % 10] - 1] arr[i]; count[(arr[i] / exp) % 10]--; movements; } for (int i 0; i n; i) // 将排序结果复制回原数组 { arr[i] output[i]; movements; } cout 一轮结束当前状态 endl; for (int num : arr) cout num ; cout endl; cout string(30, -) endl; } void radixSort(vectorint arr, int comparisons, int movements) { comparisons movements 0; // 初始化计数 int maxVal *max_element(arr.begin(), arr.end()); // 找到最大值 for (int exp 1; maxVal / exp 0; exp * 10) // 对每个位数进行排序 countingSort(arr, exp, comparisons, movements); } // 顺序查找链表实现 void sequentialSearchWithList(listchar letterList, char target, int comparisons, int movements) { bool found false; // 是否找到目标值 int position 0; // 记录目标值位置 for (auto it : letterList) { comparisons; // 比较次数加1 if (it target) // 如果找到目标值 { found true; break; } position; } if (found) // 输出查找结果 cout 查找成功字母位于编号 position 1 endl; else { cout 查找失败。 endl; } cout 比较次数 comparisons endl; } // 顺序查找数组实现 void sequentialSearchWithArray(vectorchar arr, char target, int comparisons, int movements) { int n arr.size(); // 添加哨兵 arr.push_back(target); int i 0; for (auto it : arr) { comparisons; // 比较次数加1 if (it target) // 如果找到目标值 { break; } i; } if (i n) // 输出查找结果 cout 查找成功字母位于编号 i 1 endl; else { cout 查找失败。 endl; } cout 比较次数 comparisons endl; arr.pop_back(); // 删除哨兵 } // 二分查找 int binarySearch(const vectorchar arr, char key, int comparisons) { int left 0, right arr.size() - 1; comparisons 0; // 采用左闭右闭区间[left,right]进行搜索 while (left right) { int mid left (right - left) / 2; comparisons; if (arr[mid] key) { return mid; } if (arr[mid] key) { left mid 1; } else { right mid - 1; } } return -1; } // 二叉搜索树 // 定义二叉树节点的结构体 struct TreeNode { char val; // 节点存储的值 TreeNode* left; // 指向左子节点的指针 TreeNode* right; // 指向右子节点的指针 // 构造函数初始化节点值并将左右子节点设为NULL TreeNode(char x) : val(x), left(NULL), right(NULL) {} }; // 二叉搜索树类 class BinarySearchTree { private: TreeNode* root; // 树的根节点 // 插入函数递归将值插入到二叉搜索树中 TreeNode* insert(TreeNode* node, char val) { if (!node) return new TreeNode(val); // 如果当前节点为空创建新节点返回 if (val node-val) // 如果值小于当前节点递归插入到左子树 node-left insert(node-left, val); else if (val node-val) // 如果值大于当前节点递归插入到右子树 node-right insert(node-right, val); return node; // 返回更新后的节点 } // 中序遍历递归输出节点值从小到大排序 void inorder(TreeNode* node) { if (node) { inorder(node-left); // 遍历左子树 cout node-val ; // 输出当前节点值 inorder(node-right); // 遍历右子树 } } // 先序遍历递归输出节点值从小到大排序 void preorder(TreeNode* node) { if (node) { cout node-val ; // 输出当前节点值 preorder(node-left); // 遍历左子树 preorder(node-right); // 遍历右子树 } } // 删除节点函数递归删除指定值的节点同时统计比较次数 TreeNode* deleteNode(TreeNode* node, char key, int comparisons) { comparisons; // 比较次数加1 if (!node) return node; // 如果节点为空直接返回 if (key node-val) // 如果值小于当前节点递归到左子树删除 node-left deleteNode(node-left, key, comparisons); else if (key node-val) // 如果值大于当前节点递归到右子树删除 node-right deleteNode(node-right, key, comparisons); else // 找到要删除的节点 { if (!node-left) return node-right; // 如果没有左子节点返回右子节点 if (!node-right) return node-left; // 如果没有右子节点返回左子节点 // 如果左右子节点都存在找到右子树的最小值替代当前节点 TreeNode* temp node-right; while (temp-left) temp temp-left; // 找到右子树的最小值 node-val temp-val; // 用最小值替代当前节点值 node-right deleteNode(node-right, temp-val, comparisons); // 删除最小值节点 } return node; // 返回更新后的节点 } public: // 构造函数初始化树为空 BinarySearchTree() : root(nullptr) {} // 插入函数向树中插入一个值 void insert(char val) { root insert(root, val); } // 中序遍历输出树的中序遍历结果 void inorder() { inorder(root); cout endl; } // 先序遍历输出树的先序遍历结果 void preorder() { preorder(root); cout endl; } // 删除键值函数从树中删除指定值的节点同时统计比较次数 void deleteKey(char key, int comparisons) { root deleteNode(root, key, comparisons); } }; const int TABLE_SIZE 20; // 哈希表大小 const int divisor 19; // 选择比哈希表表长小的最大素数 // 哈希查找 class HashTable { // 哈希表的节点结构 struct HashNode { int key; // 节点存储的键值 bool isOccupied; // 标记节点是否被占用 // 构造函数初始化节点为空 HashNode() : key(0), isOccupied(false) {} }; HashNode table[TABLE_SIZE]; // 哈希表的数组 // 哈希函数除留余数法 int hashFunction(int key) { return key % divisor; // 取键值对divisor的余数作为索引 } public: // 构造函数初始化哈希表 HashTable() {} // 插入函数将键值插入到哈希表中 void insert(int key) { int index hashFunction(key); // 计算键值的哈希索引 while (table[index].isOccupied) // 如果当前位置被占用寻找下一个位置 index (index 1) % divisor; // 开放地址法 - 线性探测法 table[index].key key; // 在找到的位置插入键值 table[index].isOccupied true; // 标记位置已被占用 } // 查找函数在哈希表中查找键值 void search(int key) { int index hashFunction(key); // 计算键值的哈希索引 int comparisons 0; // 统计比较次数 while (table[index].isOccupied comparisons TABLE_SIZE) // 遍历哈希表 { comparisons; // 比较次数加1 if (table[index].key key) // 如果找到键值 { cout 查找成功数据位于哈希表索引 index endl; cout 比较次数 comparisons endl; return; } index (index 1) % divisor; // 开放地址法 - 线性探测法 } cout 查找失败数据不在哈希表中。 endl; cout 比较次数 comparisons endl; } // 打印函数输出哈希表的内容 void printHashTable() { cout 哈希表内容 endl; for (int i 0; i TABLE_SIZE; i) { if (table[i].isOccupied) { // 如果当前位置被占用输出键值 cout 索引 i - 数据 table[i].key endl; } else { // 如果当前位置为空 cout 索引 i - 空 endl; } } } }; int main() { // 初始化随机数生成器 vectorint numbers(16); mt19937 rng((unsigned int)time(0)); uniform_int_distributionint dist(10, 99); for (int num : numbers) { num dist(rng); } cout 原始数据: ; printVector(numbers); system(pause); vectorint sortedNumbers numbers; int comparisons, movements; //直接插入排序 system(cls); cout 直接插入排序 endl; cout 原始数据: ; printVector(numbers); insertionSort(sortedNumbers, comparisons, movements); cout 直接插入排序后: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); //折半插入排序 system(cls); cout 折半插入排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; BinaryInsertionSort(sortedNumbers, comparisons, movements); cout 折半插入排序后: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 冒泡排序 system(cls); cout 冒泡排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; bubbleSort(sortedNumbers, comparisons, movements); cout 冒泡排序后: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 选择排序 system(cls); cout 选择排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; selectionSort(sortedNumbers, comparisons, movements); cout 选择排序后: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 快速排序 system(cls); cout 快速排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; comparisons movements 0; quickSort(sortedNumbers, 0, sortedNumbers.size() - 1, comparisons, movements); cout 快速排序后: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 希尔排序 system(cls); cout 希尔排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; shellSort(sortedNumbers, comparisons, movements); cout 希尔排序结果: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 堆排序 system(cls); cout 堆排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; heapSort(sortedNumbers, comparisons, movements); cout 堆排序结果: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 归并排序 system(cls); cout 归并排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; comparisons movements 0; mergeSort(sortedNumbers, 0, sortedNumbers.size() - 1, comparisons, movements); cout 归并排序结果: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); // 基数排序 system(cls); cout 基数排序 endl; cout 原始数据: ; printVector(numbers); sortedNumbers numbers; radixSort(sortedNumbers, comparisons, movements); cout 基数排序结果: ; printVector(sortedNumbers); cout 比较次数: comparisons , 移动次数: movements endl; system(pause); //查找 system(cls); vectorchar str; srand(unsigned int(time(0))); while (str.size() 16) { char letter a rand() % 26; if (find(str.begin(), str.end(), letter) str.end()) str.push_back(letter); } cout 原始数据: ; printVector(str); // 顺序查找 cout 顺序查找 endl; char target; cout 请输入要查找的字母; cin target; // 使用链表查找 comparisons 0; listchar letterList(str.begin(), str.end()); cout 使用链表 endl; sequentialSearchWithList(letterList, target, comparisons, movements); // 使用数组查找 comparisons 0; cout 使用数组 endl; sequentialSearchWithArray(str, target, comparisons, movements); system(pause); // 二分查找 system(cls); sort(str.begin(), str.end()); cout 二分查找 endl; cout 排序后的数组: ; printVector(str); char key; cout 输入一个查找字符: ; cin key; comparisons 0; int position binarySearch(str, key, comparisons); if (position ! -1) { cout 找到下标为 position 比较次数为 comparisons endl; } else { cout 没找到比较次数为 comparisons endl; } system(pause); // 二叉搜索树 system(cls); cout 二叉搜索 endl; BinarySearchTree bst; cout 输入10个字母: ; for (int i 0; i 10; i) { char letter; cin letter; bst.insert(letter); } cout 二叉搜索树为: ; bst.inorder(); cout 先序遍历为; bst.preorder(); char delKey; comparisons 0; cout 输入要从二叉搜索树中删除的字母: ; cin delKey; bst.deleteKey(delKey, comparisons); cout 删除后二叉搜索树为: ; bst.inorder(); cout 先序遍历为; bst.preorder(); cout 比较次数为: comparisons endl; system(pause); // 哈希查找 system(cls); cout 哈希查找 endl; HashTable hashTable; cout 原始数据: endl; for (int num : numbers) { cout num ; hashTable.insert(num); } cout endl; hashTable.printHashTable(); int targer_number; cout 请输入要查找的数字; cin targer_number; hashTable.search(targer_number); system(pause); return 0; }