Python 冒泡排序仅在大数时中断

Question

我正在尝试创建一个冒泡排序测试算法，该算法生成 x 个随机整数并输出到控制台和一个文本文件。创建的数字数量以及随机整数的最大值由变量 bigsize 决定。 当 big size 为 ~2300 时，代码似乎可以工作，有时它更多有时更少。不过我总能得到 2000 的工作。

编辑：同样值得注意的是，代码似乎在排序过程中中断，因为我获得了一个文件来输出未排序的数字，没有任何问题。

import random
import sys

bigsize = 2000

def main():
    sys.setrecursionlimit(7000)
    array = create_list()
    print_array(array)
    bubble_sort(array)
    display_out(array)
      
def create_list():
    array = [0] * bigsize
    for x in range(bigsize):
        array[x] = random.randint(0, bigsize)
    return array

def bubble_sort(array):
    increment = 0
    buffer = 0
    for x in range(len(array) - 1):
        if (array[increment + 1] <= array[increment]):
            buffer = array[increment + 1]
            array[increment + 1] = array[increment]
            array[increment] = buffer
        increment = increment + 1
    increment = 0
    for x in range(len(array) - 1):
        if (array[increment + 1] >= array[increment]):
            increment = increment + 1
        elif (array[increment + 1] < array[increment]):
            bubble_sort(array)

def display_out(array):
    for x in range(bigsize):
        print(array[x])
 
main()

Answer 1

你的性格不正常。首先，递归没有任何用处：您没有减少任务——您只是使用递归代替排序的外循环。那时，您实施不正确。我强烈建议您在处理递归之前多练习一些更基本的编程技能。

第一个（非）问题是一个简单的低效率问题：您的循环将 x 作为索引，但循环体忽略了 x，同时它保持 increment 和 相同的值。没有理由有两个独立的变量。您可以在网络上的几乎所有冒泡排序中看到它是如何使用的：

for pos in range(len(array) - 1):
    if array[pos+1] < array[pos]:
        # switch the elements

你在第二个循环中有类似的低效率：

increment = 0
for x in range(len(array) - 1):
    if (array[increment + 1] >= array[increment]):
        increment = increment + 1

同样，您忽略 x 并将 increment 保持在相同的值......直到您发现元素顺序不正确：

    elif (array[increment + 1] < array[increment]):
        bubble_sort(array)

当你这样做时，你会再次出现，但不会改变 increment。当你从这个递归中 return 时，数组必须被正确排序（假设递归逻辑是正确的），然后你继续 this 循环，遍历现在排序的数组，确保数组有序 bigsize 次。

整个循环很愚蠢：如果您在第一个循环中进行切换时简单地设置一个标志，您就会知道是否需要再次排序。您将进行一次额外的迭代，但这不会影响时间复杂度。例如：

done = True
for pos in range(len(array) - 1):
    if array[pos+1] < array[pos]:
        array[pos], array[pos+1] = array[pos+1], array[pos]
        
# Replace the second loop entirely
if not done:
    bubble_sort(array)

我强烈建议您通过正确跟踪结果来检查程序的运行情况。然而，首先要清理逻辑。删除（暂时）写入文件的多余代码，放入一些基本的跟踪 print 语句，并研究现有的冒泡排序，看看你在哪里让这一切太“冗长”。事实上，删除递归并简单地重复排序直到 done.

当我用 bigsize=5000 尝试此操作时，它重复出现到 3818 级并退出。如果您清理程序后问题仍然存在，我将把跟踪工作留给您。在您加强逻辑并跟踪操作之前，修复“无声死亡”没有多大意义，这样您就知道您正在修复一个原本可以工作的程序。当前的代码并没有像发布指南所说的那样“让其他人更容易帮助您”。

Python 冒泡排序仅在大数时中断

Python bubble sort breaks with large numbers only

python

sorting

bubble-sort