сортировать список без использования .sort()

Question

Я пытаюсь найти способ сортировки списка с правильной петлей.

меня это до сих пор:

def min_sorted(xs): 
    Min= xs[0] 
    minsorted= list() 
    for x in xs: 
     if x < (Min): 
      Min= x 
      minsorted.append(Min) 
      remove_val_once(x,xs) 
    return minsorted 

Когда я проверить его с помощью xs=[5,3,4,2,1] это то, что приходит:

>>> min_sorted([5,3,4,2,1]) 
[3, 2, 1] 

Что происходит с 5 и 4

мой код для minval (xs):

def minval(xs): 
min_= xs[0] 
for x in xs[1:]: 
    if x < min_: 
     min_=x  
return min_ 

мой код remove_val_once:

def remove_val_once(val,xs): 
    for i in range(len(xs)): 
     if val==xs[i]: 
      del(val) 
      return True 
      break 
    if val!=xs[i]: 
     return False 

Answer 1

def min_sorted(values): 
    result = [] 
    while values: 
     m = min(values) 
     result.append(m) 
     values.remove(m) 
    return result 

Answer 2

Вы манипулируя список хз внутри цикла, это делает ваш вести себя петлю странным образом. Я предлагаю скопировать xs во временный список и манипулировать им. Смотрите код:

def min_sorted(xs): 
    Min= xs[0] 
    minsorted= list() 
    t = xs[:] 
    while t: 
     Min = min(t) 
     minsorted.append(Min) 
     remove_val_once(t,Min) 
    return minsorted 

Это O алгоритм (п^2), потому что сама мин функция О (п) и мы пробегаем по первоначальному списку ввода.

Существует также ошибка в вашем remove_val_once, использование вами del не соответствует действительности. Это должно быть так:

del xs[i] 

Answer 3

Прежде всего: ваш алгоритм в корне ошибочен; вы не можете сортировать список таким образом.

Вы собираетесь пропустить элементы, как вы обрабатываете список по двум причинам:

1. Вы выбросите предыдущее значение Min никогда не добавляя его. Вот почему вы пропускаете 5.

2. Вы изменяете список при повторении. При обработке 3 вы удаляете его из списка. Цикл рассматривал второй элемент в списке, но удаление 3 изменяет список от [5, 3, 4, 2, 1] до [5, 4, 2, 1], после которого цикл продолжается до третьего, а теперь 2. Вы пропустили 4.

Относительно того, почему ваш алгоритм не будет работать: думать о том, как ваш алгоритм будет обрабатывать список с наименьшим значением уже при старте, как [1, 5, 4, 3, 2].

Answer 4

5 и 4 отбрасываются вашим алгоритмом сортировки. Весь ваш код делает первый элемент xs, который меньше xs[0], затем следующий элемент списка, который меньше этого, затем следующий элемент меньше этого и т. Д. До конца списка; он никогда ничего не делает со значениями, которые пропускаются.

Answer 5

Есть более простые способы сортировки без использования .sort().Я представляю вам встраивание сортировать:

def insertionSort(unsortedList): 
    # copy list 
    length = len(unsortedList) 
    sortedList = [None] * length 
    for i in range(length): 
    sortedList[i] = unsortedList[i]; 
    for i in range(1, length): 
     j = i-1 
     value = sortedList[i] 
     while j >= 0 and value < sortedList[j]: 
      sortedList[j+1] = sortedList[j] 
      j = j-1 
     sortedList[j+1] = i 

Answer 6

Простой, наивную пузырьковой сортировки:

import random 

def bubble_sort(unsorted): 
    length = len(unsorted) - 1 
    sorted = False 
    while not sorted: 
     sorted = True 
     for i in range(length): 
      if unsorted[i] > unsorted[i+1]: 
       sorted = False 
       unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i] 

li = [random.randint(-100,100) for i in range(20)] 
bubble_sort(li) 
print li 

Answer 7

http://en.wikipedia.org/wiki/Quicksort

Quicksort который н входе п (очень быстро). Это деление на алгоритм покорения, и я чувствую, что его очень просто запомнить шаги.

def qsort(arr): 
    if len(arr) <= 1: return arr 
    pivot = arr[0] 
    left = []; right = [] 
    for i in arr[1:]: 
    if arr[i] < pivot: left.append(i) 
    else: right.append(i) 
    return qsort(left) + [pivot] + qsort(right) 

Псевдо Код:

• Базовый вариант.
• Выберите ось.
• Разделить влево и вправо, исключая шарнир.
• Return QSort (слева) + [ось] + QSort (справа)