在循环排序算法中，我正在寻找一种情况，我们观察到算法的不稳定性质

Question

我正在阅读有关循环排序算法的内容，发现它本质上是不稳定的，但是，我很难想出一个案例来显示循环算法的不稳定性质。有人可以给出一个案例，我们可以观察到算法的不稳定性质吗？

有关该算法的更多信息：- https://en.wikipedia.org/wiki/Cycle_sort

这是我的循环排序算法代码：-

        #include <iostream> 

        using namespace std;

        int main()
        {
            int n;
            cin >> n;
            int *arr;
            arr=new int[n];
            for (int i = 0; i < n; i++)
                cin >> arr[i];
            int cyStart, item, pos;
            for (int cyStart = 0; cyStart < (n - 1); cyStart++)
            {
                item = arr[cyStart];
                pos = cyStart;
                for (int i = cyStart + 1; i < n; i++)
                {
                    if (item > arr[i])
                        pos++;
                }
                if (pos == cyStart)
                    continue;
                while (item == arr[pos])
                    pos++;
                if (item != arr[pos])
                    swap(arr[pos], item);
                while (cyStart != pos)
                {
                    pos = cyStart;
                    for (int i = cyStart + 1; i < n; i++)
                    {
                        if (item > arr[i])
                            pos++;
                    }
                    while (item == arr[pos])
                        pos++;   
                    if (item != arr[pos])
                        swap(arr[pos], item);
                }
            }
            for(int i=0;i<n;i++)
                cout << arr[i] << " ";
            return 0;
        }

Answer 1

假设我们有一组数据，如下所示： 2 组字母“A”到“E”。为了更好地区分它们，我将调用带有附加数字的重复数据。所以“A”将是“A1”和“A2”等等。 现在让我们尝试根据您提到的算法对它们进行排序。

• 第1步： 取出第一个数据，并找到它应该放在哪里。由于我们知道有 10 个项目，或者 2 组 5 个相同的项目，我们知道“E1”将被放置在第 9 位。

• 第2步： “E1”放在第9位，将之前在第9位的项目取出进行排序。

• 第 3 步： “E2”放在第10位，“D2”取出进行排序。

• 第四步： “E2”放在第7位，“B2”取出进行排序。

  
  现在你可能已经注意到一个问题了！！

  “D2”放在第7位，也就是说“D1”只能放在第8位，尽管它应该放在“D2”的前面。

  嗯，这就是“不稳定排序”的意思。排序的结果将独立于原始数据的顺序！

继续排序：

• 第 5 步：
• 第 6 步：
• 第 7 步：
• 您刚刚完成了第一个周期。
• 开始下一个循环：
• 第 8 步：
• 第 9 步：
• 第 10 步：
• 第 11 步：
• 第 12 步：
• 你刚刚完成了你的排序

现在查看您的数据，您会注意到 2 对数据的排序不稳定：