数据结构-查找与排序

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

查找

顺序查找

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

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);//调整剩余元素构建最大堆
    }
}