用c语言帮我写一个快速排序的程序,要求用非递归
时间: 2023-11-27 18:04:00 浏览: 36
下面是一个用C语言实现快速排序的非递归程序:
```c
#include <stdio.h>
#define MAX_STACK_SIZE 100
void quickSort(int arr[], int left, int right);
typedef struct {
int left;
int right;
} StackItem;
typedef struct {
StackItem items[MAX_STACK_SIZE];
int top;
} Stack;
void initStack(Stack *stack);
void push(Stack *stack, StackItem item);
StackItem pop(Stack *stack);
int isEmpty(Stack *stack);
int main() {
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组:");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
void quickSort(int arr[], int left, int right) {
Stack stack;
initStack(&stack);
StackItem item = {left, right};
push(&stack, item);
while (!isEmpty(&stack)) {
item = pop(&stack);
left = item.left;
right = item.right;
int i = left;
int j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j) {
item.left = left;
item.right = j;
push(&stack, item);
}
if (i < right) {
item.left = i;
item.right = right;
push(&stack, item);
}
}
}
void initStack(Stack *stack) {
stack->top = -1;
}
void push(Stack *stack, StackItem item) {
if (stack->top == MAX_STACK_SIZE - 1) {
printf("栈已满\n");
return;
}
stack->top++;
stack->items[stack->top] = item;
}
StackItem pop(Stack *stack) {
if (isEmpty(stack)) {
printf("栈已空\n");
StackItem item = {-1, -1};
return item;
}
StackItem item = stack->items[stack->top];
stack->top--;
return item;
}
int isEmpty(Stack *stack) {
return stack->top == -1;
}
```
在程序中,我们使用了非递归方式实现了快速排序。我们使用一个栈来存储每次分割出来的子数组的左右边界,然后不断从栈中弹出边界进行排序,直到栈为空为止。在排序过程中,我们使用了双指针法来实现数组的分割和排序。运行程序后,你会看到输出的排序后的数组。