C语言中的快速排序算法实现 [英] quicksort algorithm implementaion in c
本文介绍了C语言中的快速排序算法实现的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
这是c中quicksort算法的实现,对于给定的输入,我的程序以4 5 -343534 1
的形式输出,我是编程新手,如果您能指出我的错误,那将非常有帮助
This is the implementation of quicksort algorithm in c,here for the given input my program is giving output as 4 5 -343534 1
,i am new to programming ,Please it would be really helpful if you can point out my error
#include<stdio.h>
#include<stdlib.h>
int partition(int* A, int start, int end) {
int pivot = A[end];
int pindex = start;
for (int i = 0; i < end; i++) {
if (A[i] <= pivot) {
int temp = A[i];
A[i] = A[pindex];
A[pindex] = temp;
pindex = pindex + 1;
}
}
int temp = A[end];
A[end] = A[pindex];
A[pindex] = temp;
return pindex;
}
void quicksort(int* A, int start, int end) {
if (start < end) {
int pindex = partition(A, start, end);
quicksort(A, start, pindex - 1);
quicksort(A, pindex+1, end);
}
}
int main() {
int* a = (int*)malloc(sizeof(int) * 4);
a[0] = 1;
a[1] = 5;
a[2] = 4;
a[3] = 2;
quicksort(a, 0, 3);
printf("%d %d %d %d", a[0], a[1], a[2], a[3]);
system("pause");
}
推荐答案
您的问题来自partition
函数:
i
变量应以不为0的start
开头:
The i
variable should start a start
not at 0:
int partition(int* A, int start, int end)
{
int pivot = A[end];
int pindex = start;
for (int i = start; i < end; i++) {
if (A[i] <= pivot) {
int temp = A[i];
A[i] = A[pindex];
A[pindex] = temp;
pindex = pindex + 1;
}
}
int temp = A[end];
A[end] = A[pindex];
A[pindex] = temp;
return pindex;
}
可以通过以下方式改进代码:定义swap
函数以避免重复:
Your code can be improved in a way: define a swap
function to avoid repeating yourself:
#include<stdio.h>
#include<stdlib.h>
void print_array(int *A, int size)
{
for (int i = 0; i < size; ++i)
printf("%d ", A[i]);
puts("");
}
void swap(int *A, int i, int j)
{
if (i == j)
return ;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
int partition(int* A, int start, int end) {
int pivot = A[end];
int pindex = start;
for (int i = start; i < end; i++) {
if (A[i] <= pivot) {
swap(A, i, pindex);
pindex = pindex + 1;
}
}
swap(A, end, pindex);
return pindex;
}
void quicksort(int* A, int start, int end) {
if (start < end) {
int pindex = partition(A, start, end);
quicksort(A, start, pindex - 1);
quicksort(A, pindex+1, end);
}
}
int main() {
int i, size = 32;
int* a = malloc(sizeof * a * size);
for (i = 0; i < size; ++i)
a[i] = rand()%100;
print_array(a, size);
quicksort(a, 0, size-1);
print_array(a, size);
return 0;
}
赠予:
83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 29 2
2 11 15 21 23 26 26 27 29 29 30 35 35 36 40 49 59 62 62 63 67 67 68 72 77 82 83 86 86 90 92 93
这篇关于C语言中的快速排序算法实现的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文