排序列表不使用.sort（）

我試圖找到一種方法來正確循環排序列表。排序列表不使用.sort（）

我有這個至今：

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

來源

2013-11-10 user300

什麼'remove_val_once'的定義是什麼？ – jwodder

'remove_val_once（）'做什麼？仔細觀察'Min'的第一個值會發生什麼？你從來沒有做過任何事情。 –

您不能使用單個循環對數組進行排序。你可以做的最好的是O（n log n）時間。 – wvdz

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

來源

2013-11-10 01:39:20 furas

我幾乎不認爲你應該在手動實現排序算法時使用min（）函數。 – wvdz

@robert國王：我只是想改變它:)謝謝。 – furas

你操控循環內的列表XS，這使得您的行爲循環以奇怪的方式。我建議將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（n^2）算法，因爲最小的功能本身就是O（n）和我們正在通過原始輸入列表循環。

您的remove_val_once還有一個錯誤，您使用del是錯誤的。它應該是這樣的：

del xs[i]

來源

2013-11-10 01:41:12 Raiyan

這隻會返回最少的數字 – user300

如果你打算使用min（），你可以使用'while xs：'循環。 –

@MartijnPieters：採取的點，代碼編輯。 OP沒有說明min是否禁忌 – Raiyan

首先：你的算法是根本上有缺陷的;你不能以這種方式對列表進行排序。

你會爲你處理列表中跳過的元素，有兩個原因：

你丟棄的Min以前的值而沒有附加它。這就是爲什麼你跳過5。
您正在修改列表，同時重複。處理3時，將其從列表中刪除。循環查看列表中的第二項，但刪除3將列表從[5, 3, 4, 2, 1]更改爲[5, 4, 2, 1]，之後循環繼續到第三個項目，現在爲2。您在那裏跳過4。

至於爲什麼你的算法是行不通的：想想怎麼你的算法會在啓動時已經處理好與最小值的列表，像[1, 5, 4, 3, 2]。

來源

2013-11-10 01:42:13

5和4正被您的「排序」算法丟棄。你的代碼所做的是取xs的第一個元素，它小於xs[0]，那麼列表中的下一個元素小於該元素，則下一個元素小於該元素，依此類推到列表末尾;它從不會對跳過的值做任何事情。

來源

2013-11-10 01:42:27 jwodder

有更簡單的方法來排序而不使用.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

來源

2013-11-10 01:47:59 user2975255

我認爲你必須再次格式化代碼。 – furas

-1

簡單，天真的冒泡排序：

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

來源

2013-11-10 02:04:33 dawg

爲什麼不快速排序？ – Raiyan

@Raiyan：你認真地投下了這個票，因爲它不是快速排序與泡泡排序？ – dawg

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

快速排序，它是N日誌N（非常快）。這是征服算法的一個分支，我覺得記住這些步驟非常簡單。

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)

僞代碼：

基本情況。
選擇數據透視。
除左邊和右邊分開樞軸。
返回的qsort（左）+ [透視] +的qsort（右）

來源

2013-12-06 16:54:59 kwoodson

排序列表不使用.sort（）

回答

相關問題