实现用C++

Question

我们的教授懒惰的排序算法给了我们一个编程练习：

胡安Tamad是一个懒惰的人。他的任务是对数字列表进行排序， 但他超级懒惰。他厌倦了搞清楚如何将所有的 数字全部换掉，直到所有的数字都按照升序排列。所以，他用自己的算法来到 ，这将保证新列表 排序。以下是它的工作原理：

要获得大小为n的列表，我们需要n-1次迭代。在每次迭代中，检查第n个数字是否小于第n + 1个数字。如果它是， 那么这两个数字已经排序，我们可以跳过这个迭代如果它们不是，我们会不断地递减第一个数字，直到这两个数字按顺序排列。

例如，假设输入的是

10 5 7 6 1 

在第一次迭代中，我们比较10和5。10大于5，所以我们 递减直到其较小：

4 5 7 6 1 

现在我们比较5和7. 5小于7，所以我们不需要做任何事情 ，我们跳过这个迭代。我们去下，比较7 和6 7比6大，所以我们递减前三个数字 ，直到它小于6，我们得到这样的：

2 3 5 6 1 

现在我们比较6和1。同样，6比1大，所以我们递减 前四个数字，直到它小于1，我们得到这样的：

-4 -3 -1 0 1 

，我们就大功告成了。现在这个清单是按照完美的顺序排列的。

您的任务是实现Juan Tamad在 C++程序中的排序算法。你的程序读取一个输入n和数字的列表n 数字。您的程序使用Juan Tamad的 算法对数字进行排序。

所以我想知道是否有人可以帮助至少在阐明问题。 到目前为止，我的脑海里产生了：

#include<iostream> 
using namespace std; 

int main(){ 

    int n; 
    cin >> n; 

    int a[n]; 

    for(int i = 0; i< n; i++) 
    cin>> a[i]; 

    for(int i = 0; i< n; i++) 
    cout<< a[i] << " "; 

//______________________________________ 
    for(int i = 0; i < n-1; i++){ 
    for(int j = i + 1; j < n-1; j++){ 
     if(a[i] > a[j]) 
     a[i]--; 
     } 

    } 

    for(int i = 0; i < n; i++) 
    cout << a[i] << " "; 

    return 0; 
} 

样品试验：

$./a.out 
Enter value of n: 5 
Enter 5 numbers: 10 5 7 6 1 
Output: -4 -3 -1 0 1 

$./a.out 
Enter value of n: 10 
Enter 10 numbers: 10 9 8 7 6 5 4 3 2 1 
Output: -8 - 7 - 6 -5 -4 -3 -2 -1 0 1 

$./a.out 
Enter value of n: 6 
Enter 6 numbers: 1 2 3 1 2 3 
Output: -2 -1 0 1 2 3 

$./a.out 
Enter value of n: 10 
Enter 6 numbers: 5 7 11 6 16 2 9 16 6 16 
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16 

$./a.out 
Enter value of n: 1 
Enter 6 numbers: 100 
Output: 100 

Answer 1

这是超级懒执行提到懒算法：它只有O(n)复杂：

template <class It> 
auto lazy_sort(It begin, It end) -> void 
{ 
    auto rbegin = std::make_reverse_iterator(end); 
    auto rend = std::make_reverse_iterator(begin); 

    auto it = rbegin; 
    if (it == rend) 
     return; 
    auto prev_val = *it; 
    ++it; 

    int diff = 0; 

    for (; it != rend; ++it) 
    { 
     diff += std::max(0, *it - prev_val + 1); 

     prev_val = *it; 
     *it -= diff; 
    } 
} 

BOOST_AUTO_TEST_CASE(test_lazy_sort) 
{ 
    std::vector<int> v = {10, 5, 7, 6, 1};  

    lazy_sort(v.begin(), v.end()); 

    BOOST_CHECK((v == std::vector<int>{-4, -3, -1, 0, 1})); 
} 

Answer 2

这里是s你OME点：

for(int i = 0; i < n-1; i++) 

而不是去[first, last)我会去(first, last]这是因为你需要看看以前的值。但你的方式也行得通。

for(int j = i + 1; j < n-1; j++) 

这里您无条件地通过i的权利。这是错误的。您需要：

• 首先检查是否v[i + 1] >= v[i]。如果不是，这些元素就位。您可以继续使用

• 其他。你需要减少所有元素[first, i)。为此，for应该是这样的：

  为（INT J = 0;Ĵ<我; ++ j）的

• ，你不要1需要实际递减。你可以看到元素之间的差异，然后减去。例如，当您遇到元素6 1时，您需要从所有元素中减去6（6 - 1 + 1），直到i。

其余的由你决定。