快速排序（迭代）——ANSI C实现

女爷i 2022-05-18 06:40 239阅读 0赞

typedef int ElementType;

/*
     * 分区信息结点（组成单链表）
     *
     * */
    typedef struct PartitionNode PartitionNode;
    struct PartitionNode {
    	int low;
    	int high;
    	PartitionNode *next;
    };
    
    /*
     * 由存放分区信息的单链表
     *
     * */
    typedef struct PartitionStack PartitionStack;
    struct PartitionStack {
    	PartitionNode *top;
    	int size;
    };

/**
     * 创建分区信息堆栈
     *
     */
    PartitionStack *CreatePartitionStack() {
    	// 建立一个空栈
    	PartitionStack *stack = (PartitionStack *) malloc(sizeof(PartitionStack));
    	stack->size = 0;
    	stack->top = NULL;
    
    	return stack;
    }
    
    /**
     * 销毁分区信息堆栈
     *
     */
    void DestroyPartitionStack(PartitionStack *stack) {
    	if (stack == NULL)
    		return;
    
    	while (stack->size != 0)
    		PopPartitionStack(stack);
    	free(stack);
    }
    
    /**
     * 将分区信息压栈
     *
     */
    void PushPartitionStack(PartitionStack *stack, int low, int high) {
    	// check stack
    	if (stack == NULL) {
    		return;
    	}
    
    	PartitionNode *node = (PartitionNode *) malloc(sizeof(PartitionNode));
    	node->low = low;
    	node->high = high;
    	node->next = stack->top;
    	stack->top = node;
    	stack->size = stack->size + 1;
    }
    
    /**
     * 将分区信息弹栈
     *
     */
    PartitionNode *PopPartitionStack(PartitionStack *stack) {
    	// check stack
    	if (stack == NULL || stack->size == 0 || stack->top == NULL) {
    		return NULL;
    	}
    
    	PartitionNode *node = stack->top;
    	stack->top = node->next;
    	stack->size = stack->size - 1;
    
    	// 用完后要释放这个弹出的结点
    	return node;
    }
    
    /**
     * 获取分区信息堆栈的大小
     *
     */
    int SizeofPartitionStack(PartitionStack *stack) {
    	// check stack
    	if (stack == NULL) {
    		return 0;
    	}
    
    	return stack->size;
    }
    
    /**
     * 判断分区信息堆栈是否为空
     * 返回0 ：非空
     * 返回1 ：空
     * 返回-1：出错
     */
    int IsPartitionStackEmpty(PartitionStack *stack) {
    	int result;
    
    	// check stack
    	if (stack == NULL) {
    		result = -1;
    	}
    
    	if (stack->size == 0) {
    		result = 1;
    	} else if (stack->size > 0) {
    		result = 0;
    	} else {
    		result = -1;
    	}
    
    	return result;
    }
    
    /*
     * 快速排序（迭代）
     *
     * */
    ElementType *LoopQuickSort(ElementType *arr, int low, int high) {
    	// 检查输入参数
    	if (arr == NULL || low > high || low < 0 || high < 0)
    		return NULL ;
    
    	// 建立分区信息堆栈
    	PartitionStack *stack = CreatePartitionStack();
    
    	// i为左分界下标，j为右分界下标
    	int i, j;
    	// 首个分区信息入栈
    	PushPartitionStack(stack, low, high);
    	while (!IsPartitionStackEmpty(stack)) {
    		// 待排序分区信息出栈
    		PartitionNode *node = PopPartitionStack(stack);
    		i = node->low;
    		j = node->high;
    		free(node);
    		int pivot;
    		if (i < j) {
    			// 计算支点位置
    			pivot = Partition(arr, i, j);
    			// 支点左边分区信息入栈
    			PushPartitionStack(stack, i, pivot - 1);
    			// 支点右边分区信息入栈
    			PushPartitionStack(stack, pivot + 1, j);
    		}
    	}
    
    	return arr;
    }

ElementType *Sort(ElementType *arr, int size) {
    	// 检查参数，若arr为NULL或size为0，则说明是空表，返回NULL
    	if (arr == NULL || size <= 0)
    		return NULL;
    
    	return LoopQuickSort(arr, 0, size - 1);
    }

int main() {
    
    	int size = 20;
    	int max = 300;
    	int *array = GetRandomArray(size, max);
    	printf("Original ");
    	PrintArray(array, size);
    	Sort(array, size);
    	printf("Sorted   ");
    	PrintArray(array, size);
    
    	return 0;
    }