链表选择排序实现性能问题？

Question

我已经开发了以下代码，但我看到了一些我很难理解的异常行为：

class Node(object):
    def __init__(self,val):
        self.val = val
        self.next = None

    def get_data(self):
        return self.val

    def set_data(self,val):
        self.val = val

    def get_next(self):
        return self.next

    def set_next(self,next):
        self.next = next


class LinkedList(object):        

    def __init__(self,*values):
        self.count = len(values) -1
        self.head = Node(values[0])
        node = self.head
        for idx, val in enumerate(values):
            if idx == 0:
                continue
            else:
                tempnode = Node(val)
                node.set_next(tempnode)
                node = node.get_next()


    def get_count(self):
        return self.head

    def insert(self,data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node
        self.count +=1

    def insert_at(self,idx,val):
        if idx > self.count +2:
            return

        if idx == 0:
            self.insert(val)
        else:
            tempIdx = 0
            node = self.head
            while tempIdx < idx -1:
                node = node.get_next()
                tempIdx += 1
            continuation = node.get_next()
            insertion = Node(val)
            node.set_next(insertion)
            node.get_next().set_next(continuation)

    def find(self,val):
        item = self.head
        while item != None:
            if item.get_data() == val:
                return item
            else:
                item = item.get_next()

        return None

    def deleteAt(self,idx):
        if idx > self.count+1:
            return
        if idx == 0:
            self.head = self.head.get_next()
        else:
            tempIdx = 0
            node = self.head
            while tempIdx < idx -1:
                node = node.get_next()
                tempIdx +=1
            node.set_next(node.get_next().get_next())
            self.count -= 1

    def dump_list(self):
        tempnode = self.head
        while (tempnode != None):
            print("Node: ",tempnode.get_data())
            tempnode = tempnode.get_next()       


    def swap(self,idx_a,idx_b):
        if idx_a == idx_b:
            return
        elif idx_a > idx_b:
            idx_2,idx_1 = idx_a,idx_b
        else:
            idx_2,idx_1 = idx_b,idx_a

        node = self.head
        tempIdx = 0

        while tempIdx < idx_2:
            if tempIdx != idx_1:
                node = node.get_next()
                tempIdx += 1
            else:
                elem_1 = node.get_data()
                node = node.get_next()
                tempIdx += 1
        elem_2 = node.get_data()

        self.deleteAt(idx_1)
        self.deleteAt(idx_2-1)
        self.insert_at(idx_1,elem_2)
        self.insert_at(idx_2,elem_1)

    def move_min(self,sorted_idx):
        temp_idx = 0
        node = self.head
        while temp_idx <= self.count:

            if temp_idx <= sorted_idx:
                node = node.get_next()
                temp_idx += 1

            elif temp_idx == sorted_idx +1:
                selection = node.get_data()
                selected_idx = temp_idx
                node = node.get_next()
                temp_idx += 1

            else:
                if node.get_data() < selection:
                    selection = node.get_data()
                    selected_idx = temp_idx
                try:
                    node = node.get_next()
                    temp_idx +=1
                except:
                    break

        self.deleteAt(selected_idx)
        self.insert_at(sorted_idx, selection)
        return sorted_idx + 1  

    def selection_sort(self):
        sorted_idx = 0
        while sorted_idx < self.count +1:
            sorted_idx = self.move_min(sorted_idx)

现在，我对下面的链表使用选择排序

t1 = LinkedList(4,3,2,1,0)
t1.selection_sort()
t1.dump_list()

>>>>
Node:  0
Node:  1
Node:  3
Node:  4
Node:  2

选择排序方法简单地调用move_min方法，直到sorted_idx达到LL的长度。所以我认为问题必须涉及 move_min 函数。

一般流程是：跳过变量 sorted_idx 捕获的 LL 的所有已排序部分，然后将 selection 设置为以下节点的值。在这一点之后，如果任何节点的值低于选择，选择的值将被替换。循环完成后，最小值将从其当前位置移动到 sorted_idx 位置。最后 sorted_idx 将递增 1 并返回。

selection_sort方法在每次迭代中使用上面的返回值作为sorted_idx。

我真的不知道我哪里错了..

Answer 1

这实际上是由您的 insert_at 会员中的缺陷引起的。 deleteAt 递减 count，但 insert_at 可能永远不会调用 insert 来递增它。这会导致 selection_sort 中的循环过早退出，因为您正在执行 insert/delete 来模拟交换。解决此问题的方法应该是为任何成功的插入正确增加 count。

链表选择排序实现性能问题？

Linked List selection sort implementation performance issue?

python

linked-list

selection-sort