本地南京网站建设,360网站导航公司地址怎么做,编程培训机构加盟品牌,锁定网站导航栏目录
排序算法#xff1a;
时间复杂度#xff1a;
排序算法和冒泡排序之间的过渡#xff1a;
冒泡排序
冒泡排序和快速排序之间的过渡#xff1a;
快速排序 排序算法#xff1a; 首先出场的是我们的主人公小哼#xff0c;上面这个可爱的娃就是啦。期末考试完了老…目录
排序算法
时间复杂度
排序算法和冒泡排序之间的过渡
冒泡排序
冒泡排序和快速排序之间的过渡
快速排序 排序算法 首先出场的是我们的主人公小哼上面这个可爱的娃就是啦。期末考试完了老师要将同 学们的分数按照从高到低排序。小哼的班上只有 5 个同学这 5 个同学分别考了 5 分、3 分、 5 分、2 分和 8 分哎考得真是惨不忍睹满分是 10 分。接下来将分数进行从大到小排序 排序后是 8 5 5 3 2。你有没有什么好方法编写一段程序让计算机随机读入 5 个数然后将这 5 个数从大到小输出#include stdio.h
int main()
{ int a[11],i,j,t; for(i0;i10;i) a[i]0; //初始化为0 for(i1;i5;i) //循环读入5个数{
scanf(%d,t); //把每一个数读到变量t中a[t]; //进行计数} for(i0;i10;i) //依次判断a[0]~a[10] for(j1;ja[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(i0;i1000;i) book[i]0; scanf(%d,n);//输入一个数n表示接下来有n个数for(i1;in;i)//循环读入n个数并进行桶排序{ scanf(%d,t); //把每一个数读到变量t中book[t]; //进行计数对编号为t的桶放一个小旗子} for(i1000;i0;i--) //依次判断编号1000~0的桶for(j1;jbook[i];j) //出现了几次就将桶的编号打印几次printf(%d ,i); getchar();getchar(); return 0;
}
时间复杂度
代码中第 6 行的循环一共循环了 m 次m 为桶的个数 第 9 行的代码循环了 n 次n 为待排序数的个数第 14 行和第 15 行一共循环了 mn 次。 所以整个排序算法一共执行了 mnmn 次。我们用大写字母 O 来表示时间复杂度因此该算法的时间复杂度是 O(mnmn)即 O(2*(mn))。我们在说时间复杂度的时候可以忽略较小 的常数最终桶排序的时间复杂度为 O(mn)。还有一点在表示时间复杂度的时候n 和 m 通常用大写字母即 O(MN)排序算法和冒泡排序之间的过渡
现在分别有 5 个人的名字和分数huhu 5 分、haha 3 分、xixi 5 分、hengheng 2 分和 gaoshou 8 分。请按照分数从高到低输出他们的名字。即应该输出 gaoshou、huhu、xixi、haha、hengheng。 发现问题了没有如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输 出的也仅仅是分数但没有对人本身进行排序。也就是说我们现在并不知道排序后的分数 原本对应着哪一个人这该怎么办呢不要着急请看下节——冒泡排序。简化版的桶排序不仅仅有所遗留的问题更要命的是它非常浪费空间例如需 要排序数的范围是 0~2100000000 之间那你则需要申请 2100000001 个变量也就是说要写 成 int a[2100000001]。因为我们需要用 2100000001 个“桶”来存储 0~2100000000 之间每一个数出现的次数。即便只给你 5 个数进行排序例如这 5 个数是 1、1912345678、2100000000,18000000 和 912345678你也仍然需要 2100000001 个“桶”这真是太浪费空间了还有,如果现在需要排序的不再是整数而是一些小数比如将 5.56789、2.12、1.1、3.123、4.1234 这五个数进行从小到大排序又该怎么办呢 冒泡排序 冒泡排序的基本思想是每次比较两个相邻的元素如果它们的顺序错误就把它们交换过来 #include stdio.h
int main()
{ int a[100],i,j,t,n; scanf(%d,n); //输入一个数n表示接下来有n个数for(i1;in;i) //循环读入n个数到数组a中scanf(%d,a[i]);
//混混藏书阁http://book-life.blog.163.com
//啊哈算法//冒泡排序的核心部分for(i1;in-1;i) //n个数排序只用进行n-1趟{ for(j1;jn-i;j) //从第1位开始比较直到最后一个尚未归位的数想一想为什
么到n-i就可以了。{ if(a[j]a[j1]) //比较大小并交换{ ta[j]; a[j]a[j1]; a[j1]t; } } } for(i1;in;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(i1;in;i) //循环读入n个人名和分数scanf(%s %d,a[i].name,a[i].score); //按分数从高到低进行排序for(i1;in-1;i) { for(j1;jn-i;j) { if(a[j].scorea[j1].score)//对分数进行比较{ ta[j]; a[j]a[j1]; a[j1]t; } } } for(i1;in;i)//输出人名printf(%s\n,a[i].name); getchar();getchar(); return 0;
} 冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N 2 )。 冒泡排序和快速排序之间的过渡 上一节的冒泡排序可以说是我们学习的第一个真正的排序算法并且解决了桶排序浪费 空间的问题但在算法的执行效率上却牺牲了很多它的时间复杂度达到了 O(N2 )。假如我 们的计算机每秒钟可以运行 10 亿次那么对 1 亿个数进行排序桶排序只需要 0.1 秒而冒 泡排序则需要 1 千万秒达到 115 天之久是不是很吓人那有没有既不浪费空间又可以快 一点的排序算法呢 快速排序 快速排序之所以比较快是因为相比冒泡排序每次交换是跳跃式的。每次排序的时候 设置一个基准点将小于等于基准点的数全部放到基准点的左边将大于等于基准点的数全 部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进 行交换交换的距离就大得多了。因此总的比较和交换次数就少了速度自然就提高了。当 然在最坏的情况下仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和 冒泡排序是一样的都是 O(N2 )它的平均时间复杂度为 O (NlogN)。其实快速排序是基于一 种叫做“二分”的思想。 #include stdio.h
int a[101],n;//定义全局变量这两个变量需要在子函数中使用
void quicksort(int left,int right)
{ int i,j,t,temp; if(leftright) return; tempa[left]; //temp中存的就是基准数 ileft; jright; while(i!j) { //顺序很重要要先从右往左找 while(a[j]temp ij) j--; //再从左往右找 while(a[i]temp ij) i; //交换两个数在数组中的位置 if(ij)//当哨兵i和哨兵j没有相遇时{ ta[i]; a[i]a[j]; a[j]t; } } //最终将基准数归位 a[left]a[i]; a[i]temp; quicksort(left,i-1);//继续处理左边的这里是一个递归的过程 quicksort(i1,right);//继续处理右边的这里是一个递归的过程
}
int main()
{ int i,j,t; //读入数据 scanf(%d,n); for(i1;in;i) scanf(%d,a[i]); quicksort(1,n); //快速排序调用 //输出排序后的结果 for(i1;in;i) printf(%d ,a[i]); getchar();getchar(); return 0;
} 书上对冒泡排序法的拓展介绍 快速排序由 C. A. R. Hoare东尼·霍尔Charles Antony Richard Hoare在 1960 年提出 之后又有许多人做了进一步的优化。如果你对快速排序感兴趣可以去看看东尼·霍尔 1962 年在 Computer Journal 发表的论文“Quicksort”以及《算法导论》的第七章。快速排序 算法仅仅是东尼·霍尔在计算机领域才能的第一次显露后来他受到了老板的赏识和重用 公司希望他为新机器设计一种新的高级语言。你要知道当时还没有 PASCAL 或者 C 语言这 些高级的东东。后来东尼·霍尔参加了由 Edsger Wybe Dijkstra1972 年图灵奖得主这个 大神我们后面还会遇到的到时候再细聊举办的 ALGOL 60 培训班他觉得自己与其没有 把握地去设计一种新的语言还不如对现有的 ALGOL 60 进行改进使之能在公司的新机器 上使用。于是他便设计了 ALGOL 60 的一个子集版本。这个版本在执行效率和可靠性上都在 当时 ALGOL 60 的各种版本中首屈一指因此东尼·霍尔受到了国际学术界的重视。后来他 在 ALGOL X 的设计中还发明了大家熟知的 case 语句也被各种高级语言广泛采用比如 PASCAL、C、Java 语言等等。当然东尼·霍尔在计算机领域的贡献还有很多很多他在 1980 年获得了图灵奖。 啊哈算法---小哼买书练习快速排序_慢慢走比较快k的博客-CSDN博客
解决这个问题的方法大致有两种。第一种方法先将这 n 个图书的 ISBN 号去重再进 行从小到大排序并输出第二种方法先从小到大排序输出的时候再去重。这两种方法都 可以。方法一
#include stdio.h
int main()
{ int a[1001],n,i,t; for(i1;i1000;i) a[i]0; //初始化scanf(%d,n); //读入n for(i1;in;i) //循环读入n个图书的ISBN号{ scanf(%d,t); //把每一个ISBN号读到变量t中a[t]1; //标记出现过的ISBN号} for(i1;i1000;i) //依次判断1~1000这个1000个桶{ if(a[i]1)//如果这个ISBN号出现过则打印出来printf(%d ,i); } getchar();getchar(); return 0;
}
这种方法的时间复杂度就是桶排序的时间复杂度为 O(NM)。 方法二第二种方法我们需要先排序再去重。排序我们可以用冒泡排序或者快速排序。 20 40 32 67 40 20 89 300 400 15 将这 10 个数从小到大排序之后为 15 20 20 32 40 40 67 89 300 400。 接下来要在输出的时候去掉重复的。因为我们已经排好序所以相同的数都会紧挨在第 1 章 一大波数正在靠近——排序 一起。只要在输出的时候预先判断一下当前这个数 a[i]与前面一个数 a[i1]是否相同。如 果相同则表示这个数之前已经输出过了不用再次输出不同则表示这个数是第一次出现 需要输出这个数。 #include stdio.h
int main()
{
int a[101],n,i,j,t;scanf(%d,n); //读入n
for(i1;in;i) //循环读入n个图书ISBN号
{
scanf(%d,a[i]);
}//开始冒泡排序
for(i1;in-1;i)
{
for(j1;jn-i;j)
{
if(a[j]a[j1])
{ ta[j]; a[j]a[j1]; a[j1]t; }
}
}
printf(%d ,a[1]); //输出第1个数
for(i2;in;i) //从2循环到n
{
if( a[i] ! a[i-1] ) //如果当前这个数是第一次出现则输出
printf(%d ,a[i]);
}
getchar();getchar();
return 0;
} 这种方法的时间复杂度由两部分组成一部分是冒泡排序的时间复杂度是 N (N2 )另 一部分是读入和输出都是 O(N)因此整个算法的时间复杂度是 O(2*NN 2)。相对于 N2 来 说2*N 可以忽略我们通常忽略低阶最终该方法的时间复杂度是 O(N2 )。原书中的总结 接下来我们还需要看下数据范围。每个图书 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(NM)冒泡排序是 O(N 2 )快速排序是 O(NlogN)
