2

因此，对于编程作业，我们必须在 python 中重新编写 sort 函数来对单词列表进行排序。到目前为止，我已经使它能够根据每个单词的第一个字母对单词进行排序，现在我尝试运行递归以在第一个字母或任何字母相同的情况下对其进行排序。我遇到了“IndexError：字符串索引超出范围”错误的问题。到目前为止我所拥有的是

def insertion_sort(bookwords):
    for index in range(1,len(bookwords)):
        global word
        word=bookwords[index]
        i=index-1
        word_checker(bookwords, 0, i)

def word_checker(bookwords, num, i):
    while i>=0:
        wordleft=bookwords[i]
        if ord(word[num])<ord(wordleft[num]):
            bookwords[i+1]=bookwords[i]
            bookwords[i]=word
            i=i-1
        elif ord(word[num])==ord(wordleft[num]):
            num=num+1
            word_checker(bookwords, num, i)
        else:
            break


bookwords=["michael", "maddy", "michelle", "monstor", "money", "mountain", "miniscus", "mega"]

insertion_sort(bookwords)

print bookwords

我猜 num 变得比单词大，但是当字母不一样时，它会不停地运行很多次，所以我有点困惑为什么要这样做。任何帮助将不胜感激

更新

好的，现在它可以工作了，但是当我将它放入提供的代码中以测试大约 700000 个单词的速度时，它持续了 30+ 直到我停止它，因为排序功能需要 5 秒。这也是我的部分代码

import re
import pygame

# 159.172 assignment 2
# 
def mysort(words):
for index in range(1,len(words)):
    word=words[index]
    i=index-1
    word_checker(words, i, word)

def word_checker(words, i, word):
while i>=0:
    wordleft=words[i]
    if word==wordleft:
        break
    elif word<wordleft:
        words[i+1]=words[i]
        words[i]=word
        i=i-1
    else:
        return

# Do NOT change anything below here:
#
# Compare two lists
def compare(l1,l2):
    if len(l1) != len(l2):
        return False
    for a,b in zip(l1,l2):
        if a!=b:
            return False
    return True

# Open the book
book=open("allsherlock.txt", "rt")

# Make a list of all the words in the book
bookwords=[]
for line in book:
    for word in re.findall(r'\w+', line):
        bookwords.append(word.lower())

print "Loaded",len(bookwords),"words"
sortedbookwords=bookwords[:]
pygame.init()
# Use the sort function to sort the words for testing
sortedbookwords.sort()
starttime=pygame.time.get_ticks()
# Call our sort function
mysort(bookwords)
print "Sort took",pygame.time.get_ticks()-starttime,"ms"
print "Correct sort:",compare(bookwords,sortedbookwords)
4

2 回答 2

3

你必须改变这个：

 elif ord(word[num])==ord(wordleft[num]):
     num=num+1
     word_checker(bookwords, num, i)
 else:

至：

 elif ord(word[num])==ord(wordleft[num]):
     num=num+1
 else:

然后它将打印：['maddy', 'mega', 'money', 'michael', 'michelle', 'miniscus', 'monstor', 'mountain']

无论如何，我看不到在那里进行递归的意义，我认为插入排序不会进行递归。

更新

按字符比较时算法被破坏了，但是python可以为你比较字符串，所以这将给出正确的结果：

def insertion_sort(bookwords):
    for index in range(1,len(bookwords)):
        global word
        word=bookwords[index]
        i=index-1
        word_checker(bookwords, i)

def word_checker(bookwords,  i):
    while i>=0:
        wordleft=bookwords[i]
        if word<wordleft:
            bookwords[i+1]=bookwords[i]
            bookwords[i]=word
        i=i-1

bookwords=["michael", "maddy", "michelle", "monstor", "money", "mountain", "miniscus", "mega"]
insertion_sort(bookwords)
print bookwords #prints ['maddy', 'mega', 'michael', 'michelle', 'miniscus', 'money', 'monstor', 'mountain']
于 2013-10-10T23:58:55.317 回答
1

几件事：

  • Python 零索引字符串（所以从 0 到 len(string)-1）。和
  • 考虑只使用“for”来遍历每个字母。
于 2013-10-10T23:58:20.127 回答