一道看不懂的函数题目

超级新手

def ins_sort_rec(seq, i):
    if i == 0: return
    ins_sort_rec(seq, i - 1)
    j = i
    while j > 0 and seq[j - 1] > seq[j]:
        seq[j - 1], seq[j] = seq[j], seq[j - 1]
        j -= 1

seq = [3,-6,79,45,8,12,6,8]
ins_sort_rec(seq, len(seq)-1)
print(seq[5])

可以简单讲述一下下代码的运行过程吗
是一道理论题 要求结果
运行结果为12  但是直接在纸上写 不知道是怎样的过程
谢谢！！！！
┭┮﹏┭┮

newu

就是一个升序排序的算法，用了递归函数。

超级新手

newu 发表于 2019-6-28 19:41
就是一个升序排序的算法，用了递归函数。

嗯  但是我不太明白具体的过程
第一次 i 取7  然后呢j=7 seq[6]>seq[7] 不成立了 下一步该怎么办呢
还是我理解出了错误QAQ

RIXO

呃，大概就是一个排序算法，冒泡排序吧，就是一圈一圈的循环比较相邻的两个数字，把大的放后面小的放前面，这样把列表  [:1]的数比较一遍，然后再把[:2]的数比较一遍，再比较[:3]的数。。。。就这样一直比较到[:len(seq)-1]的数，就也是全部数组比较一遍，然后给出一个顺序的数组
排序前   seq = [3,-6,79,45,8,12,6,8]
排序后   seq = [-6,3,6,8,8,12,45,79]
所以 seq[5] == 12

newu

超级新手 发表于 2019-6-28 19:51
嗯  但是我不太明白具体的过程
第一次 i 取7  然后呢j=7 seq[6]>seq[7] 不成立了 下一步该怎么办呢
还 ...

额，是这样的，这个是一个递归的插入排序，
它先开始会一直执行这个ins_sort_rec(seq, i - 1)递归函数，
直到i-1等于0的时候，才会执行下边的语句， 此时 i = 1， 然后层层向上

                               
登录/注册后可看大图

newu

超级新手 发表于 2019-6-28 19:51
嗯  但是我不太明白具体的过程
第一次 i 取7  然后呢j=7 seq[6]>seq[7] 不成立了 下一步该怎么办呢
还 ...

这是它的非递归版本，先研究下

1. def ins_sort(seq):
   
2.     for i in range(1,len(seq)):
   
3.         j = i
   
4.         while j>0 and seq[j-1]>seq[j]:
   
5.             seq[j - 1], seq[j] = seq[j], seq[j - 1]
   
6.             j -= 1

复制代码

迷雾少年

外层循环用递归的冒泡排序

超级新手

newu 发表于 2019-6-28 20:06
这是它的非递归版本，先研究下

嗯嗯这个非递归版本的我明白了
冒泡排序的方法
  if i == 0: return
    ins_sort_rec(seq, i - 1)
    j = i
但是原题这里还是不太明白

newu

超级新手 发表于 2019-6-28 20:36
嗯嗯这个非递归版本的我明白了
冒泡排序的方法
  if i == 0: return

我把关键的地方分解一下：

seq = [3,-6,79,45,8,12,6,8]
ins_sort_rec(seq,7)
   i不等于0
   ins_sort_rec(seq,6)
      i不等于0
      ins_sort_rec(seq,5)
         i不等于0
         ins_sort_rec(seq,4)
            i不等于0
            ins_sort_rec(seq,3)
               i不等于0
               ins_sort_rec(seq,2)
                  i不等于0
                  ins_sort_rec(seq,1)
                     i不等于0
                     ins_sort_rec(seq,0)
                         i终于等于0了，返回
                     这里就开始执行剩下没执行的代码
                     j=i
                     while...
                 j=i
                 while...
              ....
          ....

超级新手

newu 发表于 2019-6-28 20:42
我把关键的地方分解一下：

seq = [3,-6,79,45,8,12,6,8]

i=0
j=0
while j>0 这里好像就不成立了？

newu

超级新手 发表于 2019-6-28 21:13
i=0
j=0
while j>0 这里好像就不成立了？

抱歉我对齐偏差了，应该是i = 1,j = 1,执行完之后，再执行上个函数调用剩下的代码

超级新手

newu 发表于 2019-6-28 21:17
抱歉我对齐偏差了，应该是i = 1,j = 1,执行完之后，再执行上个函数调用剩下的代码

再执行上个函数调用剩下的代码 是什么意思呀

newu

超级新手 发表于 2019-6-28 23:30
再执行上个函数调用剩下的代码 是什么意思呀

def ins_sort_rec(seq, i):
    if i == 0: return
    ins_sort_rec(seq, i - 1) # 这个函数递归总有结束的时候吧
   # 下边就是剩下的代码
    j = i
    while j > 0 and seq[j - 1] > seq[j]:
        seq[j - 1], seq[j] = seq[j], seq[j - 1]
        j -= 1