准备-快速排序分析

2013年4月10日 由 Creater 留言 »

排序是很多笔试面试常考的算法,值得加强学习。
快排1.

把数组第一个元素作为区分标准,存入临时变量tmp。 现在数组头部空出一个位。

从右到左扫描到小于标准的数,放入该空位。 现在数组后半部分空出一个位

从左到右扫描到大于标准的数,放入右边的空位, 现在数组左半部分有一空位

。。。。

当left == right时,则将tmp作为标准的数组,划分成两个区间爱你,左边的小于标准,右边的大于等于标准

再递归该两个子区间

void Qsort(int *a, int begin, int end) {
	if(begin >= end)
		return;
	int left = begin;
	int right = end;
	int tmp = a[left];
	while(left < right) {
		while(right > left) {
			if(a[right] >= tmp)
				right --;
			else
				break;
		}
		if(right != left) {
			a[left] = a[right];
		}

		while(left<right) {
			if(a[left] < tmp)
				left++;
			else
				break;
		}
		if(left != right) {
			a[right] = a[left];
		}
	}
	a[left] = tmp;
	Qsort(a, begin, left -1);
	Qsort(a, left+1, end);

}

快排2:把数组尾部元素作为标准,小于该标准的数依次从头交换,最后得到小于该标准的数都交换到数组头部。
最后把这个标准与前边被判断出小于标准的序列的尾部。再递归该两个子区间

void vswap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
void QSort(int a[], int begin, int end) {
	if(begin >= end)
		return;
	int i,j;
	int tmp = a[end];
	int next = begin;
	for(i = begin; i< end; i++) {
		if(a[i] < tmp){
			vswap(a[i], a[next++]);
		}
	}
	vswap(a[next], a[end]);
	QSort(a, begin, next-1);
	QSort(a, next+1, end);
}
广告位

发表评论

你必须 登陆 方可发表评论.