quitsort.cpp

/* 
 * File:   main.cpp
 * Author: jawinton
 *
 * Created on 2010年9月2日, 下午7:55
 */

#include <cstdlib>

using namespace std;

#include <stdio.h>

static void qsort_swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void qsort(int *base, int nmemb)
{
	int *begin_stack[10];
	int *end_stack[10];
	int *begin;
	int *end;
	int *seg1;
	int *seg2;
	int *seg2p;
	int loop;
	unsigned int offset;

	/* 使用栈而不是常见的递归实现 */
	begin_stack[0] = base;	//	开始元素位置栈，入栈
	end_stack[0]   = base + (nmemb - 1) ;	//	结束位置栈，入栈

	for (loop = 0; loop >= 0; --loop) {
		begin = begin_stack[loop];	//	开始位置出栈
		end   = end_stack[loop];	//	结束位置出栈

		while (begin < end) {//两者位置大小比较
			offset = (end - begin) >> 1;	//	取中间位置

			qsort_swap(begin, begin + offset);	//	交换开始和中间的位置的数值

			seg1 = begin;
			seg2 = end;

			while (1) {
                                //当两边的数值

				for (; seg1 < seg2 && *begin < *seg1 ; seg1 += 1);

				for (; seg2 >= seg1 && *seg2 > *begin; seg2 -= 1);

				if (seg1 >= seg2)
					break;

				qsort_swap(seg1, seg2);
			}

			qsort_swap(begin, seg2);

			seg2p = seg2;

			if ((seg2p - begin) <= (end - seg2p)) {
				if (seg2p < end) {	//	右侧入栈
					begin_stack[loop] = seg2p + 1;
					end_stack[loop++] = end;
				}
				end = seg2p;
			} else {
				if (seg2p > begin) {	// 左侧入栈
					begin_stack[loop] = begin;
					end_stack[loop++] = seg2p - 1;
				}	//	end if
				begin = seg2p;
			}	//	end if
		}	//	end while
	}	//	end for

}
//int main(int argc, char *argv[])
//{
//    int m = 3,n=5;
//    qsort_swap(&m,&n);
//    printf("%d %d",m,n);
//	int a[10] = {14, 5, 7, 8, 2, 4, 55, 3};
//	int i;
//	qsort(a, 8);
//	for (i = 0; i < 8;i++)
//	{
//		printf("%d ", a[i]);
//	}
//	return 0;
//}