快速排序算法C语言实现（源代码） - ultimate
快速排序算法C语言实现（源代码）
快速排序算法
快速排序算法在很多的数据结构与算法书中都有讲解，关于它不过多介绍了.
快速排序算法的时间复杂度最坏情况下是O(n^2)也就是每次哨兵几乎都不起作用的情况下,平均时间复杂度是O(nlgn).
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 100
/*
快速排序算法的两个主要步骤，分割（Partition和QuickSort）
*/
int Partition(int A[],int p,int q);
int QuickSort(int A[],int p,int q);
int test();
int main()
{
test();
return 0;
}
/*
一个很简单的测试函数
*/
int test()
{
int a[MAX];
int i;
srand((int)time(0));
for(i = 0;i<MAX;i++)
{
a[i] = rand();
}
for(i = 0;i<MAX;i++)
printf(“%d\t“,a[i]);
printf(“\n“);
QuickSort(a,0,MAX–1);
for(i = 0;i<MAX;i++)
printf(“%d\t“,a[i]);
printf(“\n“);
Partition步骤中哨兵选取的是最后一个元素作为哨兵
*/
int Partition(int A[],int p,int q)
{
int i,j,x,t;
x = A[q];
i = p–1;
for (j = p;j<=q;j++)
if(A[j] < x)
{
i++;
t = A[j];
A[j] = A[i];
A[i] = t;
}
A[q] = A[i+1];
A[i+1] = x;
return i+1;
}
/*
递归调用的QuickSort程序
*/
int QuickSort(int A[],int p,int r)
{
if(p<r)
{
int q = Partition(A,p,r);
QuickSort(A,p,q–1);
QuickSort(A,q+1,r);
}
}
#include<stdlib.h>
#include<time.h>
#define MAX 100
/*
快速排序算法的两个主要步骤，分割（Partition和QuickSort）
*/
int Partition(int A[],int p,int q);
int QuickSort(int A[],int p,int q);
int test();
int main()
{
test();
return 0;
}
/*
一个很简单的测试函数
*/
int test()
{
int a[MAX];
int i;
srand((int)time(0));
for(i = 0;i<MAX;i++)
{
a[i] = rand();
}
for(i = 0;i<MAX;i++)
printf(“%d\t“,a[i]);
printf(“\n“);
QuickSort(a,0,MAX–1);
for(i = 0;i<MAX;i++)
printf(“%d\t“,a[i]);
printf(“\n“);
}
Partition步骤中哨兵选取的是最后一个元素作为哨兵
*/
int Partition(int A[],int p,int q)
{
int i,j,x,t;
x = A[q];
i = p–1;
for (j = p;j<=q;j++)
if(A[j] < x)
{
i++;
t = A[j];
A[j] = A[i];
A[i] = t;
}
A[q] = A[i+1];
A[i+1] = x;
return i+1;
}
/*
递归调用的QuickSort程序
*/
int QuickSort(int A[],int p,int r)
{
if(p<r)
{
int q = Partition(A,p,r);
QuickSort(A,p,q–1);
QuickSort(A,q+1,r);
}
}
版权声明：本文为ultimate原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。