查找与排序

目录

 顺序查找

折半查找

直接插入排序 

 优化——折半插入排序

希尔排序

冒泡排序

---

 顺序查找

//顺序查找的实现
typedef struct{
	ElemType *elem;
	int TableLen;
}SSTable;
//顺序查找
//方法一
int Search_Seq(SSTable ST,ElemType key){
	int i;
	for(i=0;i
	//查找成功，则返回元素下标；查找失败，则返回-1
	return i==ST.TableLen?-1:i;
}
//方法二
int Search_Seq(SSTable ST,ElemType key){
	ST.elem[0]=key; //哨兵
	int i;
	for(i=ST.TableLen;ST.elem[i]!=key;--i);
	return i;
}

折半查找

又称二分查找。仅适用于有序的顺序表。

int Binary_Search(SSTable L,ElemType key){
	int low=0,high=L.TableLen-1,mid;
	while(low<=high){
		mod=(low+high)/2;//取中间位置
		if(L.elem[mid]==key)
			return mid;
		else if(L.elem[mid]>key)
			high=mid-1;
		else
			low=mid+1;
	}
	return -1;
}

直接插入排序 

//直接插入排序
void InsertSort(int A[],int n){
	int i,j,temp;
	for(i=1;i
		if(A[i]-1]){
			temp=A[i];
			for(j=i-1;j>=0&&A[j]>temp;--j)
				A[j+1]=A[j];
			A[j+1]=temp;
		}
	}
}

 优化——折半插入排序

//优化——折半插入排序
void InsertSort(int A[],int n){
	int i,j,low,high,mid;
	for(i=2;i<=n;i++)//依次将A[2]~A[n]插入前面的已排序序列
	{
		A[0]=A[i];
		low=1;high=i-1;//设置折半查找的范围
		while(low<=high){
			mid=(low+high)/2;
			if(A[mid]>A[0])
				high=mid-1;
			else
				low=mid+1;
		}
		for(j=i-1;j>=high+1;--j)
			A[j+1]=A[j];
		A[high+1]=A[0];
	}
}

希尔排序

void ShelloSort(int A[],int n){
	int d,i,j;
	//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
	for(d=n/2;d>=1;d=d/2)//步长变化
		for(i=d+1;i<=n;++i)
			if(A[i]
				A[0]=A[i];
				for(j=i-d;j>0&&A[0]
					A[j+d]=A[j];
				A[j+d]=A[0];
			}
}

冒泡排序

void swap(int &a,int &b){
	int temp=a;
	a=b;
	b=temp;
}
void BubbleSort(int A[],int n){
	for(int i=0;i-1;i++){
		bool flag=flase;
		for(int j=n-1;j>i;j--){
			swap(A[j-1]>A[j]);
			flag=ture;
		}
		if(flag==false)
			return;
	}
}