首页 > 编程语言 > 详细

【初赛】——排序

时间:2019-09-16 21:59:41      阅读:82      评论:0      收藏:0      [点我收藏+]

还有一个月就要开始我的初赛了!

如果没搞好就前功尽弃了呢。

所以今天开始努力复习初赛知识!

技术分享图片

 

   计数排序(桶排)就是对于一个序列,找小于某一个数的数的数量,就能直接得到这个数排序后所在位置,是一种牺牲空间换时间的做法,十分稳定。

  选择排序就是每次遍历数组找到最小的元素,放在头部,再从剩下的里面找次小的,放在头部,重复直到排序完成,非常慢,数组的位置也会影响时间,所以不稳定。

  冒泡排序比较熟悉,就是每两位比较一下大小,进行交换操作等,但是无论数组怎样变换,遍历的次数是固定的,所以也很稳定。

  插入排序是一个从无到有的过程,每次从数组中随机挑一个数字,在排序数组中找到合适位置插入,因为每次遍历找到元素,还要将后面的部分移动一次,所以实际上复杂度是稳定1+2+…+n=O(n^2)的。(另外还有二分插排这种东西,也是O(n^2))。

  快排就是sort,将排序序列根据一个key分成两部分,左边小于key,右边大于key,再分治解决,但是不稳定,最优情况和二分法差不多,但最坏能到达2次方级别。

  归并排序就是完全利用分治思想来排序,先不断二分,最后将分出来的两份对应比较大小,交换顺序的操作,递归时合并即可,由于完全利用二分思想,所以递归层数也是固定的,稳定O(nlogn)。

  堆排序是利用堆维护的一种排序方式,每次将堆顶值取出,再将序列尾元素放到堆头,进行一次下沉操作,新的最大值就出来了。由于下沉操作不稳定,所以整个排序就不稳定了,但平均复杂度还是O(nlogn)的。

  基数排序是根据数字的位来排序的,就不多叙述了。

  希尔排序,又称增量排序,可以认为是插排的改进版,O(n^1.3~2),不稳定。

 

 

 

 

【初赛】——排序

原文:https://www.cnblogs.com/Nelson992770019/p/11529984.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!