C语言用两种方法实现快速排序算法,
时间: 2023-06-12 14:06:42 浏览: 67
第一种方法是使用递归实现快速排序算法。具体步骤如下:
1. 选择一个基准元素,通常选择第一个元素;
2. 将所有比基准元素小的元素放在基准元素之前,所有比基准元素大的元素放在基准元素之后;
3. 对基准元素左右两部分分别递归地进行快速排序。
以下是使用递归实现快速排序的C语言代码:
```c
void quickSort(int arr[], int left, int right) {
int i, j, pivot, temp;
if (left < right) {
pivot = left;
i = left;
j = right;
while (i < j) {
while (arr[i] <= arr[pivot] && i < right) {
i++;
}
while (arr[j] > arr[pivot]) {
j--;
}
if (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = temp;
quickSort(arr, left, j - 1);
quickSort(arr, j + 1, right);
}
}
```
第二种方法是使用非递归实现快速排序算法。具体步骤如下:
1. 选择一个基准元素,通常选择第一个元素;
2. 使用一个栈来保存需要排序的区间,开始将整个数组的区间入栈;
3. 循环进行以下操作,直到栈为空:
- 出栈一个区间,将该区间进行划分,得到基准元素的位置;
- 如果左区间非空,则将左区间入栈;
- 如果右区间非空,则将右区间入栈。
以下是使用非递归实现快速排序的C语言代码:
```c
void quickSort(int arr[], int left, int right) {
int i, j, pivot, temp;
int stack[right - left + 1];
int top = -1;
stack[++top] = left;
stack[++top] = right;
while (top >= 0) {
right = stack[top--];
left = stack[top--];
pivot = left;
i = left;
j = right;
while (i < j) {
while (arr[i] <= arr[pivot] && i < right) {
i++;
}
while (arr[j] > arr[pivot]) {
j--;
}
if (i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
temp = arr[pivot];
arr[pivot] = arr[j];
arr[j] = temp;
if (j - 1 > left) {
stack[++top] = left;
stack[++top] = j - 1;
}
if (j + 1 < right) {
stack[++top] = j + 1;
stack[++top] = right;
}
}
}
```