c++ - 插入排序优化

Question

我正在尝试练习制作一些不同的排序函数，但我想出的插入函数给我带来了一些麻烦。我可以相当快地对小于 30K 的列表进行排序。但是我有一个包含 100K 个整数的列表，函数完成排序实际上需要 15 分钟。一切都正确排序，但我不认为应该花那么长时间。

我的代码是否遗漏了一些导致它花费这么长时间的东西？提前谢谢了。

void Sort::insertion_Sort(vector <int> v)
{
    int vecSize = v.size(); 

    //for loop to advance through the vector
    for (int i=0; i < vecSize; i++)
    {
        //delcare some variables 
        int cursor = i; 
        int inputCursor = i-1; 
        int temp = v[cursor]; 

        //check to see if we are considering only a single element 
        if (cursor > 0)
        {
            //if there is more than 1 element, then we test the following. 
            //1. is the cursor element less than the inputCursor(which 
            //is the previous element) 
            //2. is the input cursor greater than -1
            while (inputCursor > -1 && v[cursor] < v[inputCursor] )
            {

                    //if so, we swap the variables 
                    //then move the cursors back to check 
                    //the previous elment and see if we  need to swap again. 
                    temp = v[cursor];
                    v[cursor] = v[inputCursor];
                    v[inputCursor] = temp;
                    inputCursor--;
                    cursor--; 
            }
        }
    }
}

Answer 1

插入排序是一种O(n^2) 算法。对于大输入来说它很慢。处理 10 万个项目的列表比处理 3 万个项目的列表花费的时间大约长 11 倍。对于大于 20 左右的输入，您应该使用类似快速排序的东西，它是 O(n*log(n))。