2

我已经编写了这段代码进行排序，它运行得很好。我想知道如何降低它的时间复杂度。

#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;
}

如果没有其他方法可以更改它，那么我是否必须更改算法？如果是这样，那么请提出一个算法？

谢谢。

4

3 回答 3

6

似乎您使用了某种已知速度很慢的选择排序。IRL 应用程序通常使用快速排序或合并排序（不是后者）。

我建议您也这样做（假设这是出于教育目的）。

否则，使用std::sort定义在<algorithm>.

另外，请注意您的代码不是标准的：

cin>>n;
int arr[n];

C++ 不支持 VLA。你最好使用 astd::vector代替。如果您使用 C++，请不要编写 C 代码。

于 2012-08-13T17:33:01.890 回答
3

您的算法是选择排序，一种O(n^2)算法：如果输入大小在 中线性增长n，则运行时间与 的二次函数成正比n。基于任意输入（即没有关于输入的先验知识）的比较排序的最小时间复杂度是O(n log n)。STL 函数std::sort提供了这种保证。

#include <algorithm>
#include <vector>

int main()
{
    int n;
    cin>>n;
    std::vector<int> arr;
    arr.resize(n);

    for(int i=0;i<n; ++i) // ++i rather than i++ is a good habit to get into
    {
        cin>>arr[i];
    }

    // O(N log N) complexity
    std::sort(arr.begin(), arr.end());

    return 0;
}

对于小的输入，选择排序（或插入排序）有时可以足够快。您还可以将其编码为 C++11 中的几行代码（它使用 lambda 表达式）

#include <algorithm>
#include <iterator>

template<class ForwardIterator>
void selection_sort(ForwardIterator first, ForwardIterator last)
{
        std::for_each(first, last, [](ForwardIterator it) {         // your outer loop
                auto const selection = std::min_element(it, last);  // your inner loop
                std::iter_swap(selection, it);                      // your swap code
        });
}

// call on your vector
selection_sort(arr.begin(), arr.end());

从这段代码中，选择排序的工作原理也很明显：重复地在数组的剩余部分中找到最小元素，并将其交换到位。它应该等同于你自己的代码，但我希望你同意它更容易理解（一旦你了解了 STL，就是这样）。

于 2012-08-13T17:35:28.183 回答
0

您正在使用选择排序对数组进行排序。此算法的运行时间 id O(n^2)。您可以使用合并排序或堆排序来排序运行时间为O(nlog(n)).
您还可以使用Intro Sort，它使用一个非常巧妙的技巧将QuickSort 的最坏情况降低到 O(n log n)，同时保持其他良好的性能特征

查看有关排序算法的 wiki 页面以获取更多详细信息。

于 2012-08-13T17:35:50.410 回答