网站网页策略,wordpress动态二维码,长春做网络优化的公司,艺术类 网站建设方案数据结构再往后就是比较零散的各种操作#xff0c;查找与排序是其中最常出现的#xff0c;今天来总结一下常用的查找与排序所用的方法
查找
顺序查找
最简单的查找方式#xff0c;遍历#xff0c;然后比较
bool search1(int *a,int n,int k){for (int i1;in;i){//遍…数据结构再往后就是比较零散的各种操作查找与排序是其中最常出现的今天来总结一下常用的查找与排序所用的方法
查找
顺序查找
最简单的查找方式遍历然后比较
bool search1(int *a,int n,int k){for (int i1;in;i){//遍历if (a[i]k) {//比较return true;break;}}return false;
}
遍历时对数据i是否越界的判断可以使用哨兵优化掉
int search1(int *a,int n,int k){a[0]key;//哨兵while(a[n]!key){n--;}return n;//找到返回位置找不到返回0
}
二分查找
又称为折半查找是对顺序表进行的一种查找方式每次查找过后如果目标值小于中间值则肯定小于中间向右的所有值只需要在左边数据里查找再对中间值进行比较如此反复
//二分查找
int binarysearch(int *a,int n,int k){int l,r,m;l1;//左指针指向一查找的数组范围的左边rn;//右指针while(lr){m(lr)/2;if (a[m]k) return m;//如果相等返回找到的位置else if(a[m]k) rm-1;//在左边进行查找else lm1;//在右边查找}return 0;
}
插值查找
与二分查找类似的查找方式不同的是每次更新查找域并不是对半分而是根据目标值与最小值的估计距离如果差值大查找域就更往右反之往左ml(r-l)*(k-a[l])/(a[r]-a[l])
//插值查找
int intersearch(int* a,int n,int k){int l,r m;l1;rn;while(lr){ml(r-l)*(k-a[l])/(a[r]-a[l]);if (a[m]k) return m;//如果相等返回找到的位置else if(a[m]k) rm-1;else lm1;}return 0;
}
斐波那契查找
基于斐波那契数列独有的黄金分割性质进行的查找原理与二分查找类似不同点依旧是对二次查找域的分割不是基于一半而是基于黄金分割 //斐波那契查找
//f[k]为斐波那契数列
int fibosearch(int* a,int n,int k){int l,r,m;l1;rn;while(nf[k]-1){k;}for (int in;if[k]-1;i){//补全a数组将最大的数补到a数组后面a[i]a[n];}while(lr){mlf[k-1]-1;if (a[m]k) {if (mn) return n;//m大于n说明是补全的数字中的值与目标值相等返回最大值else return m;}else if(a[m]k){//此时去左边查找新数列的总长度为f[k-1]-1个rm-1;k--;}else {//此时去右边查找新数列的总长度为f[k-2]-1个lm1;k-2;}}return 0;
}
二叉树的查找操作
在BST中查找对应值。简单的树状遍历查找
bool search(BinaryTree* T,int key) {if (!T) {return false; //树为空} else if (keyT-data) {return true;//查找成功} else if (keyT-data) {return search(T-leftchild,key); //继续在左子树中查找} else {return search(T-rightchild,key); //向在右子树中查找}
} 排序
插入排序
插入排序是将数组分为排好序与未排序的部分在未排序部分取出元素比较插入到已排序的部分的合适位置一般看做第一个元素已排序完毕从第二个元素开始对已排序部分从前往后扫描已排序的元素中大于此元素的向后移动如此反复
void inserSort(int*a,int n) {for (int i1;in;i) {//从第二个元素开始比较找合适的位置插入int ka[i];int ji-1;// 将a[i]插入到已排序序列数组中while (j0a[j]k) {a[j1]a[j];j--;}a[j1]k;}
}
冒泡排序
这个方法几乎是新手村必打的小怪。重复遍历数组一次比较两个元素如果顺序不对就交换它们
void bubbleSort(int *a, int n) {for (int i0; in-1; i) {for (int j0; jn-i-1; j) {if (a[j]a[j1]) {//顺序不对则交换int tempa[j];a[j]a[j1];a[j1]temp;}}}
}
希尔排序
希尔排序是对插入排序的一种改进通过比较不相邻的元素进行交换来提高插入排序的效率。基本思想为将数组分为若干子序列对每个子序列进行插入排序再对这个数列进行插入排序
void shellSort(int *a, int n) {for (int gapn/2;gap0;gap/2) {//对不同步长进行排序即不同长度子序列for (int igap; in; i) {int tempa[i];//记录当前元素int j;for (ji;jgapa[j-gap]temp;j-gap) {a[j]a[j-gap];//往后移动元素}a[j]temp;//插入到正确位置}}
}
快速排序
快排采用了分治法的思想选择一个基准元素将待排数组分为两个部分左边都小于它右边都大于它然后递归地进行排序具体方法为选择基准元素一般为第一个元素设定左右指针指向数组始末移动左指针直到找到小于基准元素的元素同时移动右指针找到大于基准元素的元素交换这两个元素的位置重复步骤直到左指针大于右指针将基准元素与右指针的元素互换此时基准元素左边的都小于等于它右边的大于等于它重复以上步骤
int partition(int*nums,int low,int high) {int pivotnums[low];//选择第一个元素为基准元素while (lowhigh) {// 从右向左找到小于基准元素的值while (lowhighnums[high]pivot)high--;nums[low]nums[high];//将找到的小于基准元素的值放到左边// 从左向右找到大于基准元素的值while (lowhighnums[low]pivot)low;nums[high]nums[low];//将找到的大于基准元素的值放到右边}nums[low]pivot;return low;
}
void qsort(int*nums,int low,int high) {if (lowhigh) {int pospartition(nums,low,high);//获取基准元素位置qsort(nums,low,pos-1);//对左半进行排序qsort(nums,pos1,high);//对右半进行排序}
}
堆排序
堆排序是一种基于堆形数据结构的排序利用堆的性质来实现。堆分为最大堆和最小堆分别是父结点大于子节点、父结点小于子节点的二叉树结构堆排序是先将待排数组构成一个最大堆或最小堆然后每次取出堆顶元素对剩下的元素进行调整再继续取出直到所有元素被取出
c有堆形数据结构的相关函数使用其排序较为方便
void print(const vectorint a) {//输出排序好的元素for (int i0;ia.size();i)couta[i] ;coutendl;
}
// 堆排序
void heapSort(vectorint a) {make_heap(a.begin(),a.end());//默认构建最大堆最小堆需要自定义比较函数for (int ia.size()-1;i0;i--) { //依次取出堆顶元素进行排序pop_heap(a.begin(),a.begin()i1);//将当前堆顶元素最大值与数组末尾元素交换swap(a[0],a[i]);push_heap(a.begin(),a.begin()i);//调整剩余元素构建最大堆}
}
