数据结构-查找与排序

数据结构再往后就是比较零散的各种操作，查找与排序是其中最常出现的，今天来总结一下常用的查找与排序所用的方法

查找

顺序查找

• 最简单的查找方式，遍历，然后比较

bool search1(int *a,int n,int k){for (int i=1;i<n;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;l=1;//左指针指向一查找的数组范围的左边r=n;//右指针while(l<=r){m=(l+r)/2;if (a[m]==k) return m;//如果相等，返回找到的位置else if(a[m]>k) r=m-1;//在左边进行查找else l=m+1;//在右边查找}return 0;
}

插值查找

• 与二分查找类似的查找方式，不同的是每次更新查找域并不是对半分，而是根据目标值与最小值的估计距离，（如果差值大查找域就更往右，反之往左），m=l+(r-l)*(k-a[l])/(a[r]-a[l])

//插值查找
int intersearch(int* a,int n,int k){int l,r m;l=1;r=n;while(l<=r){m=l+(r-l)*(k-a[l])/(a[r]-a[l]);if (a[m]==k) return m;//如果相等，返回找到的位置else if(a[m]>k) r=m-1;else l=m+1;}return 0;
}

斐波那契查找

• 基于斐波那契数列独有的黄金分割性质进行的查找，原理与二分查找类似，不同点依旧是对二次查找域的分割不是基于一半，而是基于黄金分割

//斐波那契查找
//f[k]为斐波那契数列
int fibosearch(int* a,int n,int k){int l,r,m;l=1;r=n;while(n>f[k]-1){k++;}for (int i=n;i<f[k]-1;i++){//补全a数组，将最大的数补到a数组后面a[i]=a[n];}while(l<=r){m=l+f[k-1]-1;if (a[m]==k) {if (m>n) return n;//m大于n，说明是补全的数字中的值与目标值相等，返回最大值else return m;}else if(a[m]>k){//此时去左边查找，新数列的总长度为f[k-1]-1个r=m-1;k--;}else {//此时去右边查找，新数列的总长度为f[k-2]-1个l=m+1;k-=2;}}return 0;
}

二叉树的查找操作

• 在BST中查找对应值。简单的树状遍历查找

bool search(BinaryTree* T,int key) {if (!T) {return false;  //树为空} else if (key==T->data) {return true;//查找成功} else if (key<T->data) {return search(T->leftchild,key); //继续在左子树中查找} else {return search(T->rightchild,key); //向在右子树中查找}
}

 排序

插入排序

• 插入排序是将数组分为排好序与未排序的部分，在未排序部分取出元素，比较插入到已排序的部分的合适位置，一般看做第一个元素已排序完毕，从第二个元素开始，对已排序部分从前往后扫描，已排序的元素中大于此元素的向后移动，如此反复

void inserSort(int*a,int n) {for (int i=1;i<n;i++) {//从第二个元素开始比较，找合适的位置插入int k=a[i];int j=i-1;// 将a[i]插入到已排序序列数组中while (j>=0&&a[j]>k) {a[j+1]=a[j];j--;}a[j+1]=k;}
}

冒泡排序

• 这个方法几乎是新手村必打的小怪。重复遍历数组，一次比较两个元素，如果顺序不对就交换它们

void bubbleSort(int *a, int n) {for (int i=0; i<n-1; i++) {for (int j=0; j<n-i-1; j++) {if (a[j]>a[j+1]) {//顺序不对则交换int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}
}

希尔排序

• 希尔排序是对插入排序的一种改进，通过比较不相邻的元素进行交换来提高插入排序的效率。基本思想为将数组分为若干子序列，对每个子序列进行插入排序，再对这个数列进行插入排序

void shellSort(int *a, int n) {for (int gap=n/2;gap>0;gap/=2) {//对不同步长进行排序（即不同长度子序列）for (int i=gap; i<n; i++) {int temp=a[i];//记录当前元素int j;for (j=i;j>=gap&&a[j-gap]>temp;j-=gap) {a[j]=a[j-gap];//往后移动元素}a[j]=temp;//插入到正确位置}}
}

快速排序

• 快排采用了分治法的思想，选择一个基准元素，将待排数组分为两个部分，左边都小于它，右边都大于它，然后递归地进行排序
• 具体方法为：选择基准元素（一般为第一个元素），设定左右指针指向数组始末；
• 移动左指针，直到找到小于基准元素的元素，同时移动右指针，找到大于基准元素的元素，交换这两个元素的位置；重复步骤，直到左指针大于右指针
• 将基准元素与右指针的元素互换，此时基准元素左边的都小于等于它，右边的大于等于它；
• 重复以上步骤

int partition(int*nums,int low,int high) {int pivot=nums[low];//选择第一个元素为基准元素while (low<high) {// 从右向左找到小于基准元素的值while (low<high&&nums[high]>=pivot)high--;nums[low]=nums[high];//将找到的小于基准元素的值放到左边// 从左向右找到大于基准元素的值while (low<high&&nums[low]<=pivot)low++;nums[high]=nums[low];//将找到的大于基准元素的值放到右边}nums[low]=pivot;return low;
}
void qsort(int*nums,int low,int high) {if (low<high) {int pos=partition(nums,low,high);//获取基准元素位置qsort(nums,low,pos-1);//对左半进行排序qsort(nums,pos+1,high);//对右半进行排序}
}

堆排序

• 堆排序是一种基于堆形数据结构的排序，利用堆的性质来实现。堆分为最大堆和最小堆，分别是父结点大于子节点、父结点小于子节点的二叉树结构
• 堆排序是先将待排数组构成一个最大堆或最小堆，然后每次取出堆顶元素，对剩下的元素进行调整，再继续取出，直到所有元素被取出

（c++有堆形数据结构的相关函数，使用其排序较为方便）

void print(const vector<int>& a) {//输出排序好的元素for (int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;
}
// 堆排序
void heapSort(vector<int>& a) {make_heap(a.begin(),a.end());//默认构建最大堆，最小堆需要自定义比较函数for (int i=a.size()-1;i>0;i--) { //依次取出堆顶元素，进行排序pop_heap(a.begin(),a.begin()+i+1);//将当前堆顶元素（最大值）与数组末尾元素交换swap(a[0],a[i]);push_heap(a.begin(),a.begin()+i);//调整剩余元素构建最大堆}
}