Синтаксис/понимание Python

Question

def counting_sort(array, maxval): 
    """in-place counting sort""" 
    m = maxval + 1 
    count = [0] * m    # init with zeros 
    for a in array: 
     count[a] += 1    # count occurences 
    i = 0 
    for a in range(m):   # emit 
     for c in range(count[a]): # - emit 'count[a]' copies of 'a' #CONFUSED 
      array[i] = a 
      i += 1 
    return array 

print counting_sort([1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1], 7) 
#   prints: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7] 

Итак, в приведенном выше коде я не понимаю строку, помеченную путаным, 4 строки до последнего. Может быть, потому что я новичок в python или просто глуп.

1. Что происходит в первом случае? Когда диапазон []? ... "для каждого c в диапазоне пустого массива ....?
2. i dont get array[i] = a на строке под а также. Если a - первый элемент в массиве подсчета, который может быть равен нулю, как это может быть добавлены ....? Действительно запуталась ...

Ура!

Answer 1

1. range даст вам список с заданными начальным и конечным значениями. Например

   print range(5) 
   

   напечатает

   [0, 1, 2, 3, 4] 
   

   Когда вы говорите, range(m) или range(count[a]) он будет генерировать список до m или count[a] начиная с 0.

2. О array[i] = a

   В range(m) для каждого элемента, то код проверяет count[a]. Если count[a] равен 0, второй цикл не будет выполнен. (range(0) произведет пустой список) Итак, когда a будет 0 array[i] = a не будет выполнен.

Answer 2

Вы, видимо, понял, что count[a] будет 0, и, следовательно, range(count[a]) будет [].

Итак, что вы спрашиваете, есть то, что делает это сделать:

for i in []: 
    do_stuff(i) 

Ответ заключается в том, что цикл по каждому из элементов 0, другими словами, это не петля вообще. Он просто ничего не делает *

Это объясняется в документации для the for statement:.

... Люкс затем выполняется один раз для каждого элемента, предоставленного итератором ... Когда детали будут исчерпаны (что сразу когда последовательность пуста ...) ... цикл завершается.

---

И что косвенно объясняет свой второй бит путаницы:

Если это первый элемент в счетную массив, который может быть равен нулю, как оно может быть добавлено

Когда count[a] равно 0, вы никогда не попадете в цикл, так что случай никогда не возникнет.

---

* Если for оператор имеет else положение, это запустить пункт else.

Answer 3

Я упростил часть кода, возможно, это поможет вам хорошо понять суть алгоритма. После подсчета всех элементов массива мы можем восстановить отсортированный массив только с информацией, хранящейся в count[].

array=[] 
for a in range(m): 
    array.extend([a]*count[a])