c# - 冒泡排序程序
问题描述
我正在创建一个冒泡排序程序,它对数组中的随机整数进行排序。该数组应该能够容纳多达一百万个已排序的整数。当我达到一个很高的数字(例如,250,000)时,程序将坐在那里,从不输出任何东西。代码如下:
using System;
namespace SortingProject
{
class MainClass
{
public static void Main(string[] args)
{
//create an array to hold integers
int[] list = new int[50000];
//call random function to populate integer values
Random rand = new Random();
//add integers to array
for (int i = 0; i < list.Length; i++) {
list[i] = rand.Next(1,50000);
}
//call bubble sort method and input the array
BubbleSorting(list);
}
//bubble sort method and logic
public static void BubbleSorting(int[] array)
{
//initialize time start
DateTime start = DateTime.Now;
DateTime end;
end = DateTime.Now;
//initialize element integer
int element = 0;
for (int bubble = 0; bubble < array.Length; bubble++)
{
//create for loop to perform bubble sort
for (int sort = 0; sort < array.Length - 1; sort++)
{
if (array[sort] > array[sort + 1])
{
element = array[sort + 1];
array[sort + 1] = array[sort];
array[sort] = element;
}
}
}
//loop and print array contents
for (int i = 0; i < array.Length; i++)
Console.Write(array[i] + " ");
//calculate time it takes to sort array
end = DateTime.Now;
TimeSpan ts = end.Subtract(start);
Console.WriteLine(" ");
Console.WriteLine("Duration = {0} ms", ts.TotalMilliseconds);
}
}
}
我通常在程序运行时等待一段时间,但它似乎被更大的数组冻结了。任何有关为什么的帮助将不胜感激。
解决方案
测试了代码,它运行良好(测试了 250000 个值)。正如评论中所指出的,冒泡排序算法并不是最优化的算法。其复杂性由下式给出:
for (int bubble = 0; bubble < array.Length; bubble++)
{
//create for loop to perform bubble sort
for (int sort = 0; sort < array.Length - 1; sort++)
{
\\do logic
}
}
外部 for 循环将执行 N 次循环。内部 for 循环将执行 N 次循环。大 O 表示法的复杂度为 N*N,因此我们有 O(N^2)。
对于 250000 个值,将有 62,500,000,000 次迭代。
请记住,复杂性(如果愿意的话,所花费的时间)与值 N 的数量成正比,您需要排序的值越多,冒泡排序完成所需的时间就越长。
推荐阅读
- c# - 当前上下文中不存在的类函数
- git - Gitconfig 凭据操作系统检查
- java - 我在测试课上缺少什么?
- java - ITextPDF 例外 - 用于 HR 标签,不使用 HR
- r - 提取空格后的文本字符串和带有 gsub R 的符号
- c# - ModelState.AddModelError 设置为显示 Canned 消息而不是真正的错误
- flutter - Flutter 中的自动填充文本字段
- postgresql - ORA-28545 NET8 错误数据库链接 oracle 到 postgresql
- r - grep vs agrep 中的撇号和可选参数(?)
- php - 更新到 Codeigniter 3 后无法发送电子邮件