C++插入排序不适用于大型数组

-2

我的insertSort函数适用于小型数组，但不适用于具有50,000个随机值的数组。我花了几个小时试图弄清楚这一点，但我很难过。这里是代码：C++插入排序不适用于大型数组

void insertionSort(int array[], int length) { 
    int swapHolder, counter, index; 
    for (counter = 1; counter < length; counter++) { 
     index = counter; 
     while (counter > 0 && array[index - 1] > array[index]) { 
       swapHolder = array[index]; 
       array[index] = array[index - 1]; 
       array[index - 1] = swapHolder; 
       index--; 
     } 
    } 
}

我的其他排序功能（bubbleSort）适用于大型数组，但我在这个问题上挂了。

来源

2016-07-05 Python guy

当你说“不行”时，你的意思是什么？你能否请尝试创建一个[最小，完整和可验证示例]（http://stackoverflow.com/help/mcve）并向我们展示？并请[请阅读如何提出良好问题]（http://stackoverflow.com/help/how-to-ask）。 –

为什么你递减'索引'而不是增加它O_o – mangusta

......你为什么要检查“counter> 0”，因为这将永远是真的？保证。 'counter'总是至少为1，并且永远不会递减。这个问题的答案很简单：“你的插入排序实现是错误的”。 –

线

while (counter > 0 && array[index - 1] > array[index]) {

应该

while (index > 0 && array[index - 1] > array[index]) {

在更深笔记，插入排序是O(n^2)所以平均的复杂性，它适用于小型阵列。也就是说，它不是排序50,000个值的正确算法。

来源

2016-07-05 01:39:39 aichao

那么，BubbleSort也不是。我猜他只是试图让它正确，并且即使对于大型阵列，两者都应该正常工作（虽然速度很慢）。 –

谢谢，这解决了我的问题。我的程序显示它仅花费1828毫秒来分类50,000个值。 –

@RudyVelthuis这是一个课程项目，显示各种排序/搜索方法的速度 –

C++插入排序不适用于大型数组

回答

相关问题