快速排序:是冒泡排序的一种改进
主要思想:找到一个基准,从后往前找比基准小的,都将它放到左边,从前往后找比基准大的都放到右边,这样就将数组分为两部分,并且左边的都比右边的大,然后进行递归操作。
C语言代码:
-
#include<stdio.h>
-
#define MAX 225
-
-
int R[MAX];
-
//快速排序,递归函数
-
int Partition(int i,int j)
-
{
-
int privot=R[i]; //让基准等于左侧第一个数字
-
while(i<j)
-
{
-
while(i<j&&R[j]>=privot)
-
j--; //从右向左找比基准小的
-
if(i<j)
-
R[i++]=R[j];
-
while(i<j&&R[i]<=privot)
-
i++; //从左向右找比基准大的
-
if(i<j)
-
R[j--]=R[i];
-
}
-
R[i]=privot;
-
return i;
-
}
-
-
void Quick_Sort(int low,int high)
-
{
-
if(low<high)
-
{
-
int p=Partition(low,high);
-
Quick_Sort(low,p-1);
-
Quick_Sort(p+1,high);
-
}
-
}
-
-
int main()
-
{
-
int i,n;
-
printf("快速排序示例:\n");
-
printf("Please input the n above 1 and below %d\n",MAX);
-
scanf("%d",&n);
-
if(n<1||n>MAX)
-
{
-
printf("Please input right n!");
-
return 0;
-
}
-
printf("Please input the array under n one by one:\n");
-
for(i=1;i<=n;i++)
-
{
-
scanf("%d",&R[i]);
-
}
-
printf("The array you input is:\n");
-
for(i=1;i<=n;i++)
-
{
-
printf("%d ",R[i]);
-
}
-
Quick_Sort(1,n);
-
printf("The array after Quick_Sort is:\n");
-
for(i=1;i<=n;i++)
-
{
-
printf("%d ",R[i]);
-
}
-
return 0;
-
}
阅读(1341) | 评论(0) | 转发(0) |