我怎样才能让这个c++编程速度更快？

Question

我正在尝试使用合并排序和标准字符串比较对字符串进行排序。问题是，这个程序本来就很慢。当我尝试检查我的解决方案时，我超出了运行时预期。有没有办法可以使用其他数据结构来做同样的事情，但访问速度更快？这是代码。感谢您的帮助。

编辑：我知道使用 sort() 而不是我自己的合并排序算法会更快，但我的要求是使用合并排序。问题在于超出了 SPOJ 的运行时要求。

#include <iostream>
using namespace std;

void MergeSortA(int low , int high);
void MergeA(int low ,int mid ,int high);

string stringData[50000];
int main()
{
    int testCases;
    int linesInTestCase;

    scanf("%d", &testCases);
    while(testCases--)
    {
        scanf("%d", &linesInTestCase);
        for(int i = 0; i < linesInTestCase; ++i)
            cin >> stringData[i];

        // Sort the data
        MergeSortA(0, linesInTestCase - 1);

        // Print array of strings one by one
        for(int i = 0; i < linesInTestCase; ++i) {
            cout << stringData[i] << endl;
        }
    }
    return 0;
}

void MergeSortA(int low , int high)
{
    int mid = 0;
    if(low < high)
    {
        mid = ((low+high)/2);
        MergeSortA(low , mid);
        MergeSortA(mid+1,high);
        MergeA(low,mid,high);
    }
}
void MergeA(int low ,int mid , int high)
{
    int i = low, j = mid+1 , k = low;
    string Temp[50000];

    while(i <= mid && j <= high) {
        if( stringData[i] < stringData[j] ) {
            Temp[k].assign(stringData[i]);
            i++;
        }
        else {
            Temp[k].assign(stringData[j]);
            j++;
        }
        k++;
    }

    if(i > mid ) {
        for(int h = j ;h <= high ; h++ ) {
            Temp[k].assign(stringData[h]);
            k++;
        }
    }
    else
        for(int h = i; h<= mid ; h++ ) {
            Temp[k].assign(stringData[h]);
            k++;
        }

    // Copy from low to high
    for(int l = low; l <= high ; l++) {
        stringData[l].assign(Temp[l]);
    }
}

Answer 1

正如您所说，这是 SPOJ 问题，我会尝试不改变您的程序结构，但是，这里存在真正的瓶颈：

void MergeA(int low ,int mid , int high)
{
    int i = low, j = mid+1 , k = low;
    string Temp[50000]; //<--- Allocation happens every time this function is called

无论何时调用 MergeA，都会构造 50000 个字符串。每次都会被破坏，阻碍算法。只需添加 static 即可：

void MergeA(int low ,int mid , int high)
{
    int i = low, j = mid+1 , k = low;
    static string Temp[50000]; //Now it is constructed & destructed only once in the program