Quick Sort ( simple verson )

2016-11-29 19:19:52来源:CSDN作者:HackerTom人点击

第七城市

备份一下手打快排的写法。

只能算是备份吧,没有解释快排的思想,以 int 为例。

没有考虑什么特殊情况,比如传入不合法指针等

/* 模仿一波 C++ 的 sort() 的接口 * 只传排序区间的首尾指针 */void quick_sort(int *left, int *right){	/* 枢轴值的备份 */	int pivot;		/* 将[left,right) 变成 [a,b](前闭后闭) */	int *a = left, *b = right - 1;		/* 如果 a>b,区间不合法(不知道有没有这种情况)	 * 如果 a=b,区间长为1,已经有序,不用再排	 */	if(a >= b)		return;		/* 选序列第1个值作枢轴,也可以是其它 */	pivot = *a;		while(a < b)	{		/* 先从后往前找下1个比pivot小的值的位置 */		while(a < b && *b >= pivot)			--b;				/* 如果找到了,直接放到 a 所指位置		 * 该位置的值已经备份		 * 然后让 a++		 */		if(a < b)			*a++ = *b;				/* 再从前往后找下1个比pivot大的值的位置 */		while(a < b && *a <= pivot)			++a;				/* 如果找到,就放在 b 所指位置		 * 并让 b--		 */		if(a < b)			*b-- = *a;	}		/* 循环之后一定是 a == b	 * 所指位置就是枢轴要去的位置	 * 枢轴归位	 */	*a = pivot;		/* 分治地处理枢轴左边的区间	 * 依然是传前闭后开的区间	 */	quick_sort(left, a);		/* 分治地处理枢轴右边区间	 * 因为枢轴已到位,不用再参于排序	 * 所以 a+1 把枢轴位置排除出待排序区间	 */	quick_sort(a+1, right);}
简单测试了一下,是可以的

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台