先看的是数据结构与算法分析--c语言描述,看来半天硬是不知所云,大概只弄清了枢纽的选择,我们一般选取
A[0] or A[N-1]大概是不对的.那就random喽...不过这个是题外话.突然想起手中还有本算法导论.
已看算法导论果然懂了,清晰易懂,人见人爱,强烈建议购买^_^
A[N]如下
2 8 7 1 3 5 6 4
描述的时候就去A[N-1]为枢纽了啊,random的话就先 swap(A[rand()%N],A[N-1])一下
2 8 7 1 3 5 6 4
i j //i=-1,j=0,x=4
此时A[j]
2 8 7 1 3 5 6 4
i j //i=0,j=1,x=4
A[1]=8>x=4
2 8 7 1 3 5 6 4
i j //i=0,j=2,x=4
A[1]=7>x=4
2 8 7 1 3 5 6 4
2 1 7 8 3 5 6 4
i j //i=0,j=3,x=4
A[3]=1 < x=4 i++;swap(A[1],A[3])
2 8 7 1 3 5 6 4
2 1 3 8 7 5 6 4
i j //i=0,j=4,x=4
A[4]=3 < x=4 i++;swap(A[2],A[3])
最后 swap(A{i+1],A[r])
|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 20
void swap(int* a,int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int partition(int a[], int start, int end)
{
//int num = rand()%(end-start+1);
// swap(a+num,a+end);
int x = a[end];
int i = start-1;
int j = start;
for(;j<end;j++) //注意这里是j
{
if(a[j]<=x)
{
i++;
swap(a+i, a+j);
}
}
swap(a+i+1,a+end);
return i+1;
}
void quick_sort(int a[],int start,int end)
{
int q;
if(start<end)
{
q = partition(a, start, end);
quick_sort(a, start, q-1);
quick_sort(a, q+1, end);
}
}
void print_array(int* a)
{
int i = 0;
for(;i<MAX;i++)
{
if((i+1)%20==0)
printf("%d\n",a[i]);
else
printf("%d\t",a[i]);
}
}
int main(int argc, char *argv[])
{
int i = 0;
int a[MAX];
srand((unsigned)time(NULL));
for(;i<MAX;i++)
a[i] = rand()%50;
printf("before quick sort\n");
print_array(a);
quick_sort(a, 0, MAX-1);
printf("after quick sort\n");
print_array(a);
system("PAUSE");
return 0;
}
|
阅读(1587) | 评论(0) | 转发(0) |
