C++ 常用排序查找算法 1
2021/5/13 22:55:45
本文主要是介绍C++ 常用排序查找算法 1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C++ 实现常用算法
排序、二分查找、树(高度、前中后层序遍历)、图的遍历、最短路径、最小生成树、求最大公约数、数制转换、水仙花数、
分治算法、贪心算法、动态规划算法、回溯算法、朴素贝叶斯分类算法、斐波那契数列、N皇后、快速幂、汉诺塔问题、
回文检查、判质数
#include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; //快排 //void Fastsort(vector<int> &nums,int l,int r) { // if (l >= r) return; // // int x = l, y = r, base = nums[l]; // // while(x < y){ // while (x < y && nums[y] >= base) y--; //后 向 前找比base小的 // if (x < y) nums[x++] = nums[y]; // // while (x < y && nums[x] <= base) x++; //从前面找比 base 大的 // if (x < y) nums[y--] = nums[x]; // } // nums[x] = base; // Fastsort(nums, l, x - 1); // Fastsort(nums, x + 1, r); //} //冒泡 //void Bubblesort(vector<int> &nums,int len) { // for (int i = 0; i < len;i++) { // for (int j = len - 1; j >= i;j--) { //第二层循环每次找一个最小的 // if (nums[i] > nums[j]) { // int temp = 0; // temp = nums[i]; // nums[i] = nums[j]; // nums[j] = temp; // } // } // }//for // return; //} //插入排序 --O(n^2) 稳定,当n比较小时,效率较高 /* 首先初始化第一个元素有序,然后逐渐把后面的元素插入到已经排好的序列中 */ //void Insertsort(vector<int> &nums,int len) { // for (int j = 1; j < len;j++) { // int key = nums[j]; // int i = j - 1; // while (i >= 0 && nums[i] > key) { // nums[i + 1] = nums[i]; //往后移动 // i--; // } // nums[i + 1] = key; //退出循环,找到了比key小的元素 // }//for // return ; //} //归并排序 -- O(nlgn) 稳定的排序 //假设初始序列是有n个记录,则可以看成是n个长度1有序的子序列,然后两两合并,得到n/2个长度为2或者1的子序列, //再两两合并,如此重复,直到得到一个长度为n的序列 //void Merge(vector<int> &nums, int start, int mid, int end) { // int n = end - start + 1;//临时数组存储合并后的有序序列 // int* temp = new int[n]; //动态的申请内存 // int i = 0; // int left = start; // int right = mid + 1; // while (left <= mid && right <= end) //原来的两个区间是按照mid分开的,所以每次按照mid为基准合并 // temp[i++] = nums[left] <= nums[right] ? nums[left++] : nums[right++]; // while (left <= mid) // temp[i++] = nums[left++]; // while (right <= end) // temp[i++] = nums[right++]; // for (int j = 0; j<n; ++j) // nums[start + j] = temp[j]; // delete[] temp;//删掉堆区的内 //} //void Mergesort(vector<int> &nums,int start,int end) { // if (start == end) return; // int mid = start + (end - start) / 2; // Mergesort(nums, start, mid); // Mergesort(nums, mid + 1, end); // Merge(nums, start, mid, end); //合并区间函数 //} /* 堆排序 -- O(nlogn) -- 不稳定的排序 */ //堆排序分为:小顶堆和大顶堆;小顶堆:每个节点的值都小于或等于其子节点的值;大顶堆:每个节点的值都大于或等于其子节点的值 //void swap(vector<int> &nums,int i,int j) { // int temp = nums[i]; // nums[i] = nums[j]; // nums[j] = temp; //} // 2、调整树结构 -- 每次调整的是三个节点的子结构 //void heapify(vector<int> &nums,int n,int i) { //n代表元素个数,i代表从第i个节点开始调整 // if (i >= n) return; // int c1 = i * 2 + 1;//当前节点左节点在数组中的位置 // int c2 = i * 2 + 2;//右节点 // int max = i; //max记录的是最大值的下标 // if (c1 < n && nums[c1] > nums[max]) max = c1; // if (c2 < n && nums[c2] > nums[max]) max = c2; // // if (max != i) { //最大值下标发生变化 // swap(nums, max, i); //让最大值在根节点 // heapify(nums, n, max); //因为树的结构改变,需要继续从max的位置修改,使得符合堆结构 // } //} // // 1、建堆 //void build_heap(vector<int> &nums, int n) { // int last_node = n - 1; //最后一个节点再数组中的位置 // int parents = (last_node - 1) / 2; // int i; // for (i = parents; i >= 0;i--) { //从倒数第二层开始调整树结构 // //2、调整树结构,使得满足堆的性质 // heapify(nums, n, i); //对所有节点做heapify // } //} // //void Heap_sort(vector<int> &nums,int n) { // //1、建堆 // build_heap(nums,n); // // int i; // for (int i = n - 1; i >= 0;i--) { // swap(nums, i, 0);//堆排序思想:将 最后一个节点和根节点交换,然后砍断最后一个叶子节点 // // heapify(nums, i, 0); //通过传入的参数i来达到砍断节点的效果,i代表 "树结构" 剩下的节点数量 // } //} //希尔排序 --shell /* 1、首先,从数组的首元素开始每隔 步长 个元素就挑选一个元素出来作为子数组元素; 2、然后每个子数组各自进行比较,比较好后,每个子数组都有顺序,进入下一轮,步长减少 再根据步长分组进行比较 3、重复以上操作,直到步长为1 */ //void Shellsort(vector<int> &nums,int n) { // int i, j, step; // for (step = n / 2; step > 0; step = step / 2) { // for (i = 0; i < step;i++) { //i是子数组的编号 // for (j = i + step; j < n;j = j + step) { //数组下标j,数组步长下标j+step // if (nums[j] < nums[j - step]) { // int temp = nums[j]; // int k = j - step; // // while (k >= 0 && temp < nums[k]) { // nums[k + step] = nums[k]; //把大的往后插入 // k = k - step; // } // nums[k + step] = temp; //小的往前插入 // } //if // } //for j // } //for i // }// for step //} //二分查找排序数组 找到返回下标,找不到返回-1 int binarysearch(vector<int> &nums,int target) { sort(nums.begin(), nums.end()); int left = 0, right = nums.size()-1, mid; while (left <= right) { mid = left + (right - left) / 2; if (target == nums[mid]) { return mid; } if (target > nums[mid]) left = mid + 1; if (target < nums[mid]) right = mid - 1; } return -1; } int main() { //给定数组实现排序算法 vector<int> nums = {2,1,4,3,5,6}; //快排 //Fastsort(nums,0,nums.size()-1); //冒泡 //Bubblesort(nums,nums.size()); //插入排序 //Insertsort(nums,nums.size()); //归并排序 //Mergesort(nums,0,nums.size()-1); //堆:是一个完全二叉树 /* 堆排序: 1、首先应该有个堆,利用bulid_heap创建堆(实质可以看作是创建一颗完全二叉树) 2、对上面创建的堆的结构进行调整,使之符合堆的特点 heapify 3、对调整好的堆进行堆排序(就是输出一个有序的排列) Heap_sort */ //Heap_sort(nums,nums.size()); //希尔排序 //Shellsort(nums,nums.size()); //二分查找 O(logN) int target = 2; int index = binarysearch(nums,target); cout << index << endl; system("pause"); return 0; }
这篇关于C++ 常用排序查找算法 1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享