大家好,欢迎来到IT知识分享网。
写在最前:
教材上描述了几种排序方法,其中重点讲解了冒泡法排序。而冒泡法排序的原理虽简单,但放到计算机上实际运算却是个不小的工程。
先来回顾一下冒泡法排序的基本步骤:
void sort(int a[],int n)
{
int i,j,t;
for(i=1;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
}
在定义冒泡法排序的函数中我们可以看到用了两次for循环,也就是说,所需要的循环遍数为n(n-1)/2次,根据时间复杂度的计算公式可以得出,冒泡法排序的时间复杂度是O(n²)。效率低不说,如果遇到了来坑你的出题者,故意把数组元素往大了出,很有可能就会出现Runtime Error。
快速排序法的基本思路:
简单介绍一下快速排序法的基本思路:任意选取一个数据作为关键数据(一般都选择第一个),然后在数组内由后向前进行搜索,把比关键数据小的数放在其前,比关键数据大的数放在其后。这个过程称为一趟快速排序。
一趟快速排序算法一般包括以下步骤:
1.定义一个待排序数组a[0]…..a[n]。
2.设置两个变量i、j,令i=0、j=n-1。
3.定义变量key,用于储存关键数组,即key=a[0]。
4.从a[j]开始向前搜索(由后向前,包括a[j]),找到第一个小于key的元素,并与key交换。
5.从a[0]开始向后搜索(由前向后,包括a[0]),找到第一个大于key的元素,并与key交换。
6.重复上述第4、5步,直到i==j。
简单的来说,就是在最开始确定一个关键元素key,这个关键元素key的值永远不变,每次由前向后,或者是由后向前的搜索都是将数组内元素和key进行比较,最后的目的是为了把key放在中间,小的放前面(由后向前找小于),大的放后面(由前向后找大于)。每次交换过后,i、j的值都发生相应的改变,变为交换之前,key所处的位置。
那么将key放在中间之后,key之前和key之后的元素并没有按照规律排序。那么在一趟快速排序的基础上,可以以key为分界点,将数组分割,使用递归,将key之前和key之后的函数进行快排。
定义快速排序的函数:
void quicksort(int a[],int first,int end)
{
int i=first,j=end,key=a[first];
while(i<j)
{
while(i<j&&a[j]>=key)
j--;
a[i]=a[j];
while(i<j&&a[i]<=key)
i++;
a[j]=a[i];
}
a[i]=key;
if(first<i-1)
quicksort(a,first,i-1);
if(end>i+1)
quicksort(a,i+1,end);
}
那么在快速排序的过程中我们可以发现,每一趟快排结束之后,数组都被分成了两部分,即由n个元素的序列分为了2个n/2的排序问题,然后再进行递归调用完成剩余步骤。排序的效率为O(nlogn),比冒泡法的效率高很多。
p.s.:快速排序函数其实在stdlib.h里有现成的,可以直接拿来用(但我不会用那玩意=^=)。
接下来看一道例题:
TZOJ3751
描述
给定n个整数,请使用快速排序算法对其进行从小到大排序。
输入
输入数据有多组,每组包含2行,第一行为正整数n(n<=100000),第二行为n个整数。
输出
每组数据占一行,每行输出排序后的n个整数,以空格分开。
样例输入
5
1 3 2 4 5
6
2 5 1 3 3 2
样例输出
1 2 3 4 5
1 2 2 3 3 5
完整代码:
#include<stdio.h>
#define maxn 100001//注意这里题目要求的n的大小
void quicksort(int a[],int first,int end)
{
int i=first,j=end,key=a[first];
while(i<j)
{
while(i<j&&a[j]>=key)
j--;
a[i]=a[j];
while(i<j&&a[i]<=key)
i++;
a[j]=a[i];
}
a[i]=key;
if(first<i-1)
quicksort(a,first,i-1);
if(end>i+1)
quicksort(a,i+1,end);
}
int main()
{
void quicksort(int a[],int first,int end);
int n,a[maxn],i,j,k;
while(~scanf("%d",&n)){
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
quicksort(a,0,n-1);
for(i=0;i<n;i++)
{if(i==n-1)
printf("%d",a[i]);
else
printf("%d ",a[i]);
}
printf("\n");
}
return 0;
}
这里因为define maxn的时候没有达到题目要求的那么大,刚开始直接习惯的写#define maxn 1001了,runtime error了好几次。。。。
欢迎私信,评论区一起交流!
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/27518.html