如何降低排序的时间复杂度？

Question

我已经编写了这个代码用于排序,它运行完全正常.我想知道如何减少时间复杂度.

#include <iostream>

using namespace std;

void sort(int a[], int n)
{
    int min, temp;
    for(int i=0;i<n-1;i++)
    {
        min=i;
        for(int j=i+1;j<n;j++)
        {
            if(a[min]>a[j])
            {
                min=j;
            }
        }
        temp=a[i];
        a[i]=a[min];
        a[min]=temp;
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<endl;
    }
}
int main()
    {
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,n);
    return 0;
}

如果没有其他方法可以更改它,那么我是否必须更改算法？如果是,那么请建议一个算法？

谢谢.

Answer 1

看起来你使用某种选择排序,这已知很慢.IRL应用程序通常使用快速排序或合并排序(而不是后者).

我建议你这样做(假设这是出于教育目的).

否则,使用中std::sort定义<algorithm>.

另请注意,您的代码不是标准的:

cin>>n;
int arr[n];

C++不支持VLA.你最好用一个std::vector代替.如果您使用C++,请不要编写C代码.