黑龙江省建设教育信息网站推广自己的产品

目录

排序算法： 

时间复杂度： 

排序算法和冒泡排序之间的过渡：

冒泡排序

冒泡排序和快速排序之间的过渡：

快速排序

排序算法： 

#include <stdio.h> 
int main() 
{ int a[11],i,j,t; for(i=0;i<=10;i++) a[i]=0; //初始化为0 for(i=1;i<=5;i++) //循环读入5个数{
scanf("%d",&t); //把每一个数读到变量t中a[t]++; //进行计数} for(i=0;i<=10;i++) //依次判断a[0]~a[10] for(j=1;j<=a[i];j++) //出现了几次就打印几次printf("%d ",i); getchar();getchar(); //这里的getchar();用来暂停程序，以便查看程序输出的内容//也可以用system("pause");等来代替return 0; 
}

#include <stdio.h> 
int main() 
{ int book[1001],i,j,t,n; for(i=0;i<=1000;i++) book[i]=0; scanf("%d",&n);//输入一个数n，表示接下来有n个数for(i=1;i<=n;i++)//循环读入n个数，并进行桶排序{ scanf("%d",&t); //把每一个数读到变量t中book[t]++; //进行计数，对编号为t的桶放一个小旗子} for(i=1000;i>=0;i--) //依次判断编号1000~0的桶for(j=1;j<=book[i];j++) //出现了几次就将桶的编号打印几次printf("%d ",i); getchar();getchar(); return 0; 
}

时间复杂度： 

排序算法和冒泡排序之间的过渡：

冒泡排序

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来

#include <stdio.h> 
int main() 
{ int a[100],i,j,t,n; scanf("%d",&n); //输入一个数n，表示接下来有n个数for(i=1;i<=n;i++) //循环读入n个数到数组a中scanf("%d",&a[i]); 
//混混藏书阁：http://book-life.blog.163.com
//啊哈！算法//冒泡排序的核心部分for(i=1;i<=n-1;i++) //n个数排序，只用进行n-1趟{ for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数，想一想为什
么到n-i就可以了。{ if(a[j]<a[j+1]) //比较大小并交换{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(i=1;i<=n;i++) //输出结果printf("%d ",a[i]); getchar();getchar(); return 0; 
}

将上面代码稍加修改，就可以解决第 1 节遗留的问题，如下。
#include <stdio.h> 
struct student 
{ char name[21]; char score; 
};//这里创建了一个结构体用来存储姓名和分数
int main() 
{ struct student a[100],t; int i,j,n; scanf("%d",&n); //输入一个数n for(i=1;i<=n;i++) //循环读入n个人名和分数scanf("%s %d",a[i].name,&a[i].score); //按分数从高到低进行排序for(i=1;i<=n-1;i++) { for(j=1;j<=n-i;j++) { if(a[j].score<a[j+1].score)//对分数进行比较{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(i=1;i<=n;i++)//输出人名printf("%s\n",a[i].name); getchar();getchar(); return 0; 
}

冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N 2 )。

冒泡排序和快速排序之间的过渡：

#include <stdio.h> 
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用 
void quicksort(int left,int right) 
{ int i,j,t,temp; if(left>right) return; temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) { //顺序很重要，要先从右往左找 while(a[j]>=temp && i<j) j--; //再从左往右找 while(a[i]<=temp && i<j) i++; //交换两个数在数组中的位置 if(i<j)//当哨兵i和哨兵j没有相遇时{ t=a[i]; a[i]=a[j]; a[j]=t; } } //最终将基准数归位 a[left]=a[i]; a[i]=temp; quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程 quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程 
} 
int main() 
{ int i,j,t; //读入数据 scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); quicksort(1,n); //快速排序调用 //输出排序后的结果 for(i=1;i<=n;i++) printf("%d ",a[i]); getchar();getchar(); return 0; 
}

 啊哈算法---小哼买书（练习快速排序）_慢慢走比较快k的博客-CSDN博客

方法一：

#include <stdio.h> 
int main() 
{ int a[1001],n,i,t; for(i=1;i<=1000;i++) a[i]=0; //初始化scanf("%d",&n); //读入n for(i=1;i<=n;i++) //循环读入n个图书的ISBN号{ scanf("%d",&t); //把每一个ISBN号读到变量t中a[t]=1; //标记出现过的ISBN号} for(i=1;i<=1000;i++) //依次判断1~1000这个1000个桶{ if(a[i]==1)//如果这个ISBN号出现过则打印出来printf("%d ",i); } getchar();getchar(); return 0; 
}

#include <stdio.h>
int main()
{
int a[101],n,i,j,t;scanf("%d",&n); //读入n
for(i=1;i<=n;i++) //循环读入n个图书ISBN号
{
scanf("%d",&a[i]);
}//开始冒泡排序
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])
{ t=a[j]; a[j]=a[j+1]; a[j+1]=t; }
}
}
printf("%d ",a[1]); //输出第1个数
for(i=2;i<=n;i++) //从2循环到n
{
if( a[i] != a[i-1] ) //如果当前这个数是第一次出现则输出
printf("%d ",a[i]);
}
getchar();getchar();
return 0;
}

原书中的总结：

接下来我们还需要看下数据范围。每个图书 ISBN 号都是 1~1000 之间的整数，并且参

加调查的同学人数不超过 100，即 n≤100。之前已经说过，在粗略计算时间复杂度的时候，

我们通常认为计算机每秒钟大约运行 10 亿次（当然实际情况要更快）。因此以上两种方法都

可以在 1 秒钟内计算出解。如果题目中图书的 ISBN 号范围不是在 1~1000 之间，而是

-2147483648~2147483647 之间的话，那么第一种方法就不可行了，因为你无法申请出这么

大的数组来标记每一个 ISBN 号是否出现过。另外如果 n 的范围不是小于等于 100，而是小

于等于 10 万，那么第二种方法的排序部分也不能使用冒泡排序。因为题目要求的时间限制

是 1 秒，使用冒泡排序对 10 万个数进行排序，计算机要运行 100 亿次，需要 10 秒钟，因此

要替换为快速排序，快速排序只需要 100000×log2100000≈100000×17≈170 万次，这还不到

0.0017 秒。是不是很神奇？同样的问题使用不同的算法竟然有如此之大的时间差距，这就是

算法的魅力！

我们来回顾一下本章三种排序算法的时间复杂度。桶排序是最快的，它的时间复杂度是

O(N+M)；冒泡排序是 O(N 2 )；快速排序是 O(NlogN)