july-class-03（查找与排序）

折半查找

int BinarySearch(int *a,int n,int key){
	int low=1,high=n,mid;
	while(low<=high){
		mid=(low+high)/2;
		if(key<a[mid]){
			high=mid-1;
		}else if(key>a[mid]){
			low=mid+1;
		}else{
			return mid;
		}
	}
	return 0;
}

冒泡排序

void BubbleSort(int *a,int n){
	int i,j,flag;
	for(i=1;i<n;i++){
		flag=0;
		for(j=0;j<n-i;j++){
			if(a[j]>a[j+1]){
				a[j]=a[j]^a[j+1];
				a[j+1]=a[j]^a[j+1];
				a[j]=a[j]^a[j+1];
				flag=1;
			}
		}
		if(flag==0) break;
	}
}

快速排序

void QuickSort(int *a,int low,int high){
	if(low<high){
		int pivotloc=Partition(a,low,high);
		QuickSort(a,low,pivotloc-1);
		QuickSort(a,pivotloc+1,high);
	}
}

int Partition(int *a,int low,int high){
	int pivotkey=a[low];
	while(low<high){
		while(low<high && a[high]>=pivotkey) --high;
		a[low]=a[high];
		while(low<high && a[low]<=pivotkey) ++low;
		a[high]=a[low];
	}
	a[low]=pivotkey;
	return low;
}

直接插入排序

void InsertSort(int *a,int n){
	int i,j;
	for(i=2;i<=n;i++){
		if(a[i]<a[i-1]){
			a[0]=a[i];
			for(j=i-1;a[0]<a[j];j--){
				a[j+1]=a[j];
			}
			a[j+1]=a[0];
		}
	}
}

希尔排序

void ShellSort(int *a,int n){
	int i,j;
	int dk=n/2;
	while(dk>=1){
		for(i=dk+1;i<=n;i++){
			if(a[i]<a[i-dk]){
				a[0]=a[i];
				for(j=i-dk;j>0 && a[0]<a[j];j-=dk){
					a[j+dk]=a[j];
				}
				a[j+dk]=a[0];
			}
		}
		dk=dk/2;
	}
}

堆排序

void HeapAdjust(int *a,int s,int m){
	int rc=a[s];
	for(int j=2*s;j<=m;j*=2){
		if(j<m && a[j]<a[j+1]) j++;
		if(rc>=a[j]) break;
		a[s]=a[j];
		s=j;
	}
	a[s]=rc;
}

void HeapSort(int *a,int n){
	int i;
	for(i=n/2;i>0;i--){
		HeapAdjust(a,i,n);
	}
	for(i=n;i>1;i--){
		a[1]=a[1]^a[i];
		a[i]=a[1]^a[i];
		a[1]=a[1]^a[i];
		HeapAdjust(a,1,i-1);
	}
}