0

我正在尝试找到一种方法来正确循环排序列表。

到目前为止我有这个：

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
4

8 回答 8

3

首先：您的算法存在根本缺陷；您不能以这种方式对列表进行排序。

您将在处理列表时跳过元素，原因有两个：

  1. 您丢弃之前的值，Min而无需附加它。这就是你跳过的原因5。

  2. 您在迭代时更改列表。处理时3，您将其从列表中删除。循环正在查看列表中的第二项，但删除3将列表从 更改为[5, 3, 4, 2, 1]，[5, 4, 2, 1]之后循环继续到第三项 now 2。你跳过了4那里。

至于为什么你的算法不起作用：想想你的算法将如何处理一个在开始时已经具有最小值的列表，比如[1, 5, 4, 3, 2].

于 2013-11-10T01:42:13.987 回答
2

您正在循环内操作列表 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) 算法，因为 min 函数本身是 O(n) 并且我们正在遍历原始输入列表。

您的 中还有一个错误remove_val_once，您的使用del是错误的。它应该是这样的：

del xs[i]
于 2013-11-10T01:41:12.933 回答
1

5 和 4 被您的“排序”算法丢弃。您的代码所做的就是取xs小于的xs[0]第一个元素，然后取小于该列表的下一个元素，然后取小于该列表的下一个元素，依此类推到列表的末尾；它永远不会对跳过的值做任何事情。

于 2013-11-10T01:42:27.333 回答
1

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

快速排序是 n log 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(left) + [pivot] + qsort(right)
于 2013-12-06T16:54:59.587 回答
0 
def min_sorted(values):
    result = []
    while values:
        m = min(values)
        result.append(m)
        values.remove(m)
    return result
于 2013-11-10T01:39:20.910 回答
0

简单、幼稚的冒泡排序：

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-10T02:04:33.203 回答
0

在不使用 .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-10T01:47:59.187 回答
0 
def min_sorted(xs):
    for i in range(0, len(xs)):
        for j in range(1+i, len(xs)):
            if xs[i] > xs[j]:
                temp = xs[i]
                xs[i] = xs[j]
                xs[j] = temp
    return xs
print("sorted list : ", min_sorted([5, 3, 4, 2, 1]))
于 2021-11-24T09:41:31.740 回答