python - 链表选择排序实现性能问题?
问题描述
我已经开发了下面的代码,但是我看到了一些我很难理解的异常行为:
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 函数。
一般流程是: 跳过由变量捕获的 LL 的所有排序部分,sorted_idx
然后将 设置selection
为以下节点的值。在此之后,如果任何节点的值低于选择,则选择的值被替换。循环完成后,最小值将从其当前位置移动到 sorted_idx 位置。最后 sorted_idx 将增加 1 并返回。
selection_sort 方法在每次迭代中使用上面的返回值作为 sorted_idx。
我真的不确定我要去哪里错了..
解决方案
这实际上是由您的insert_at
成员中的缺陷引起的。deleteAt
decrements count
,但insert_at
可能永远不会调用insert
来增加它。这会导致您的循环selection_sort
过早退出,因为您正在执行插入/删除以模拟交换。对此的修复应该是count
为任何成功的插入正确递增。