實現用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。

其餘的由你決定。