查看: 385|回复: 0
收起左侧

[Leetcode] 【排序】常用的有几种?

|只看干货
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (26)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
先上十大排序的分析图,当然其中希尔排序的分析我不太确定,大家忽略即可


别被吓着了,就参考看看,也没必要全部掌握,lz一般常用三种:快排、归并排序、堆排序,当然冒泡、插入排序也比较常用,不过刷题这么久还没遇到必须冒泡插入的。所以就介绍下快排和归并,堆排序其实是根据具体题目进行堆优化,今天先focus on排序

1、快速排序
三个步骤:
    (1)在数组中找一个数k,一般是取中间的
    (2)把数组中小于k的放其左边,大于k的放其右边
    (3)递归处理两边
基本思路是这样,在进行第(2)步的时候,实际上用的双指针,大家可以参考下代码
具体讲下边界问题,下方代码红色部分可以看到,虽然是取中间的数,但写的(l+r)>>1,而递归处理两边的时候,前一部分带入的是l ~ j,后部分带入的是j+1 ~ r,这就是边界问题;比如当只有两个数[0, 1]时,此时l, r分别为0和1,假如我们找的数的位置是(l+r+1)>>1  =  0 + 1 + 1 >>1  =  1,因此选中的数是右边的1,在while循环里出来后i = 1, j = 1,因此递归处理两边时,左边的范围是0 ~ 1,右边是2 ~ 1;右边的会直接return,但左边的范围0~1和当前的l ~ r即0~1是一样的,无限递归下去

结论:当选择(l+r)>>1,递归处理的范围就要写 l ~ j 和 j + 1 ~ r,这就是用j进行划分

那可不可以用i来划分呢?当然可以

换一种方式:当用i划分时,就写成 l ~ i-1和i ~ r,而选取的位置就应该是(l+r+1)>>1

至于为什么这样,都是前辈高人们总结出来的,感兴趣的话可以自己用一些例子调试,都是边界问题,如果不想深究了,那就记住好了~当然还有些细节问题,可以看看注释

<>
  1. n = int(input())
  2. nums = list(map(int, input().split()))

  3. def quick_sort(nums, l, r):
  4.     if(l >= r): # 只有一个数或没有
  5.         return
  6.     pick, i, j = nums[[color=#ff0000](l+r)>>1[/color]], l-1, r+1
  7.     while i<j:
  8.         i+=1
  9.         while nums[i] < pick:
  10.             i += 1
  11.         j-=1
  12.         while nums[j] > pick:
  13.             j -= 1
  14.         if i < j: # 这个改成≤是无所谓的,等于时交换无影响
  15.             nums[i], nums[j] = nums[j], nums[i]
  16.     quick_sort(nums, l, [color=#ff0000]j[/color]) # 若这换成i-1,下面换成i,则前面的nums里(l+r)>>1也要再加1,防止边界问题
  17.     quick_sort(nums, [color=#ff0000]j+1[/color], r)

  18. if __name__ == "__main__":
  19.     quick_sort(nums, 0, n-1) # 列表整个传参时,相当于引用传参
  20.     for i in range(n):
  21.         print(nums[i], end=" " if i<n-1 else "")
复制代码


2、归并排序
三个步骤:
    (1)在数组中找一个位置k,一般是取中间的
    (2)先对左边的进行归并排序,再对右边进行归并排序
    (3)将已经排好序的两边进行归并
其实这个归并的思想不止是在排序的时候用,刷题的时候有时也会用到

这里的边界问题和快排是类似的,当mid = (l+r+1)>>1时,在递归到子数组长度为2时,mid会取到右边界 r,下个循环的范围又是l~r,无限循环了

因此,当mid = (l+r)>>1,范围应该是l~mid和mid+1~r
当mid = (l+r+1)>>1,范围写l~mid-1和mid~r

当然归并里面除了改边界,还要该归并时操作的范围,下面是第一种mid = (l+r)>>1的情况,当mid = (l+r+1)>>1的情况,大家可以自己动手试试

  1. n = int(input())
  2. nums = list(map(int, input().split()))

  3. def merge_sort(nums, l, r):
  4.     if l >= r:
  5.         return

  6.     mid = [color=#ff0000](l + r) >> 1[/color]
  7.     merge_sort(nums, l, [color=#ff0000]mid[/color])
  8.     merge_sort(nums, [color=#ff0000]mid + 1[/color], r)

  9.     i, j, tmp = l, mid + 1, []

  10.     while i <= mid and j <= r:
  11.         if nums[i] <= nums[j]:
  12.             tmp.append(nums[i])
  13.             i += 1
  14.         else:
  15.             tmp.append(nums[j])
  16.             j += 1

  17.     if i <= mid:
  18.         tmp.extend(nums[i:mid+1])
  19.     if j <= r:
  20.         tmp.extend(nums[j:r+1])

  21.     nums[l:r+1] = [per for per in tmp]

  22. if __name__ == "__main__":
  23.     merge_sort(nums, 0, n-1)
  24.     for i in range(n):
  25.         print(nums[i], end=" " if i < n-1 else "")
复制代码



最后,求米各位!!加米不扣自己的!

评分

参与人数 4大米 +5 收起 理由
monad + 1 很有用的信息!
yii + 2 给你点个赞!
xixi356 + 1 说的太对了!
yyz20002008 + 1 很有用的信息!

查看全部评分


上一篇:BFS什么时候可以忽略代表层序的for循环?
下一篇:转码选手如何积攒经验
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表