欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序的非递归算法

程序员文章站 2022-03-24 13:16:06
...
#include <stdio.h>

typedef struct node
{
	int min;
	int max;
}Node;
#define MaxSize 50

void sort(int a[], int min, int max)
{
	int k = a[min];
	int i = min;
	int j = max;
	int temp;
	Node Stack[MaxSize];
	int top = 0;
	Stack[top].min = min;
	Stack[top].max = max;
	while (top > -1)
	{
		// min max记录当前处理的这个区间的左极限和右极限
		i = min = Stack[top].min;
		j = max = Stack[top].max;
		top--;
		k = a[min];
		while (i<j)
		{
			while (i<j && k <=a[j])
			{
				j--;
			}
			if (i < j)
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				i++;
			}
			while (i<j && k>=a[i])
			{
				i++;
			}
			if (i < j)
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				j--;
			}
			if (min < i - 1)
			{
				top++;
				Stack[top].min = min;
				Stack[top].max = i-1;
			}
			if (max>i + 1)
			{
				top++;
				Stack[top].min = i + 1;
				Stack[top].max = max;
			}
		}
	}

}

void main()
{
	int i;
	int a[10] = { 49, 38, 65, 97, 76, 13, 27, 9, 2, 1 };
	for ( i = 0; i < 10; i++)
	{
		printf("%d\t", a[i]);
	}
	printf("\n");
	sort(a, 0, 9);
	for ( i = 0; i < 10; i++)
	{
		printf("%d\t", a[i]);
	}
	printf("\n");
	getchar();
}