查找及排序

Hokori2018-06-052024-10-31

数据结构还真是有点难....
emmmm....
这次是查找以及排序的数据结构，其中，排序的函数如下，该排序是<b>快速排序</b>
基本思路是:利用递归，遍历数组，并将其分为枢轴的左右两边，然后再将左右两边也分开，所以该递归函数需要传递两个参数，low和high，
至于枢轴，枢轴是进行一次排序后，返回的值。
<blockquote>
int partition(int low,int high) { 
       //不能取地址，否则会将原来的值覆盖而导致low,high循环一次到相同位置之后无法再循环
	int key;
	key = a[low];//将子表的第一个记录作为枢轴
	while (low< high) { 
		while (low<high&&a[high]>key) high--;
		swap(a[low], a[high]);//将枢轴右边比枢轴小的交换到低端
        //谁与谁交换？？high指针所指的比数轴小的数与low指针所指的数交换
		while (low < high&&a[low] < key) low++;
		swap(a[low], a[high]);//将枢轴左边比枢轴大的交换到高端
	}
	return low;//此时的low==high，前面的while循环遍历了一遍数组
}//一次快速排序的算法,扫描一遍，并返回下一次排序枢轴的位置
void Qsort(int low,int high) {
	if (low < high) {
		int key = partition(low, high);//枢轴
		Qsort(low, key);//枢轴左边进行排序
		Qsort(key+1, high);//枢轴右边进行排序
	}
}//快速排序
</blockquote>
<b>查找</b>本次实验用的是二分查找，主要是遍历数组，判断key与middle的大小，并不断调整区间，查找较为简单，以下是二分查找的代码
<blockquote>
int Search(int key,int n) {
	int low = 0,high = n;
	while(low <= high) { //等号需存在，因为可能两个指针都指向同一个数，且该数就是需要查找的数的情况
		int mid = (low + high) / 2;
		if (a[mid] < key) low = mid+1;
		if (a[mid] > key) high = mid-1;
		if (a[mid] == key) return mid;
	}
	return -1;
}//二分查找
</blockquote>