欢迎光临散文网 会员登陆 & 注册

谁教你这么剪的 | 11大排序的原理讲解和Python源码剖析

2023-06-07 19:25 作者:thoseTips  | 我要投稿

科代表来简单讲一下。

没完全懂的赶紧点展开吧。

拖宽一点享受更好体验。

以下均展示从小到大排序思路。

待排序序列用a[]表示,三个端点是l, mid, r,两层循环索引是i和j,可能还有其它指针p和q

(给零基础用户:请注意第一个元素是a[0],最后一个元素是a[-1])

一、 选择排序

  1. 简介:生活中常见的排序方法,例如:一个挑剔的美食家在品尝糕点,ta可能先吃最丑的,再吃第二丑的,然后……
  2. 原理:先m=a[0]然后往后走,每个数都与m比较,更小则更新m,这样走到最后,那么m就是最小的数了,把它放到开头,然后从a[1]开始找,第二小的数放到第二位……以此类推,每次把一个较小数放到正确位置
  3. 复杂度:
  4. 时间复杂度:O(n^2)
  5. 每一趟都必须走到最后才能确定标记的是最小值。
  6. 实际上大概是O(0.5*n^2),因为每次把待排序部分缩减了1,画出来是个三角形。
  7. 空间复杂度:O(1)
  8. 优化:
  • 双选每一趟同时记录最小和最大,每次就可以归位两个元素,那么就可以把趟数缩减为1/2,同时每趟把待排序部分缩短了2,“走到最后”的过程就会更快。

二、冒泡排序

  1. 简介:相当老牌的排序,很适合排序初学者。
  2. 原理:先比较a[0]a[1]大的换朝后,然后比较a[1]a[2],大的还是换朝后,一直换下去……现在最大的在a[-1];接下来再比较一轮,第二大的就在a[-2];……像是池塘里的泡泡,每次浮上来一个最大的。
  3. 复杂度:
  4. 时间复杂度:O(n^2)
  5. 每一趟都必须把元素放到待排序部分的末端。
  6. 实际上大概是O(0.5*n^2),解释同选择排序。
  7. 空间复杂度:O(1)
  8. 优化:
  • 很多人都想过优化冒泡排序,可是没有成功。
  • 除了某些迷人的性质外,冒泡排序其实不是那么值得研究。
  • 只有几种简单的优化:(这些名字是我瞎编的,别当真)
  • 1. 非连换:当前数位置记作p、比较位置记作q 当a[p] > a[q]时仅仅移动q直到a[p] <= a[q]时交换a[p]和a[q-1],再p=q,这可以减少一些内存的写访问(毕竟q也就是j本来就是要移动的)
  • 2. 完毕剪枝:添加一个标记flag,每一趟先flag=false,若是发生了交换再设为true,若某一趟完了还是false,则说明已经排完了,return。

三、插入排序

  1. 简介:另一种生活中常见的排序,比如打斗地主理牌的时候你可能会用这一招。
  2. 原理:先拿起a[1],如果a[1]a[0]小则插在a[0]前面。现在a[0~1]是有序的了,拿起a[2],插进合适的位置……到a[k]时,a[0~k-1]也是有序的了,把a[k]也插到合适位置
  3. 复杂度:
  4. 时间复杂度:O(n^2)
  5. 哈哈哈还是O(n^2),真是太逊了
  6. 每次向已排序部分插入,使已排序增长1,也大概是O(0.5 n^2)
  7. 空间复杂度:O(1)
  8. 实际上,生活中这个排序复杂度为O(n),毕竟人眼一次可以比较好几个数的大小关系,而物理世界也不需要一个一个的移动数字。
  9. 优化
  • 覆盖式:先令p=k-1,把a[k]保存到m里,然后把m和a[p]比较,如果m比较大那就不用管了,否则用a[p]覆盖a[k],然后把p减少1,继续比较、覆盖直到某次m比较大,最后把m放在a[p+1]的位置上(刚刚p已经减少了1,加回去)。(视频里已经用了这个方法力)
  • 链表:用数据结构“链表”优化,然后就可以O(n)比较,O(1)插入,减少写访问。
  • 二分插入:如果数据结构对查询和插入都比较友好(比如块状链表),可以用二分的方法找到插入位置。

四、归并排序

  1. 简介:分治法典型范例。归是递归,并是合并。
  2. 原理:如果l~r超过2,先将a[l~mid]和a[mid~r]分别升序排序(迭代或递归)。申请一片空间,然后让p=l,q=mid,然后将a[p]和a[q]中较小者放入空间,再把较小一侧的指针右移,重复直到某一指针达到尾部,将另一部分剩下的所有元素直接复制到空间,再把空间覆盖a,返回。
  3. 复杂度:
  4. 时间:O(n log2(n))
  5. 哦终于有个能用的了。
  6. 每次都对n个元素操作且分成两半递归,则递归有log2(n)层。
  7. 空间:O(n) (记得释放你的临时空间,不然……再申请一点就会爆炸 就是O(n^log2(n))了,内存直接死了)
  8. 优化:
  • 短列别排:对较短的序列使用其它的排序(一般是插入排序,因为短的好插入,比归并还快),可以省算法时间,还可以避免频繁的申请/释放内存。

懒了,待会再更新。


5 桶排序

6 计数排序

谁教你这么剪的 | 11大排序的原理讲解和Python源码剖析的评论 (共 条)

分享到微博请遵守国家法律