插入排序在百万输入后停止工作

Question

我已经实现了插入排序,我猜它很好.它从文件读取并正确排序它们输入10,100,1000,10000,10000.

但是,当我给出一百万输入时,它什么也没做.我甚至等了10分钟检查它是否太慢了.
我动态创建了我的数组,并尝试合并排序.它完美地工作了一百万输入但我无法理解为什么只有插入排序算法不能用于一百万输入.这是代码的一部分完成工作;

#include <iostream>
#include <fstream>

using namespace std;

void InsertionSort(int* array, int& size);
int main()
{
    int size;
    ifstream myfile("data.txt");
    myfile.open("data.txt");
    cout << "How many elements do you want to read" << endl;
    cin >> size;

    int* array = new int[size];
    for (int i = 0; i < size; i++) {
        myfile >> array[i];
    }

    InsertionSort(array, size);
    delete[] array;
}
void InsertionSort(int* array, int& size)
{
    int temp, j;

    for (int i = 1; i < size; i++) {
        j = i;
        while (j > 0 && array[j - 1] > array[j]) {
            temp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = temp;
            j--;
        }
    }
}

Answer 1

您的程序在O(n²)时间运行,因为您有两个嵌套循环,这两个循环都取决于输入的大小.因此,一旦你从10,000到1,000,000个元素,你的程序将需要100²=一万倍的时间来完成.此外,您的数据集之前可能适合处理器的缓存,但是不再使用100万个元素,因此这将进一步降低速度.

O(n²)算法使得事情变得非常缓慢.输入大小为10⁶,这意味着您的程序将完成10¹的操作.假设您的处理器最多以每秒10⁹的运算速度运行,并且您的算法每步将确实使用多个操作,则程序完成所需的时间将超过10³秒.