数据结构与算法设计编程题（用C++描述），急，求大神解答~~~

Question

题目：在起泡排序过程中，有的关键字在某一次起泡过程中可能朝着与最终排序相反的方向移动，试举例说明（编程）。（例如某个数最终位置在最初位置的右边，但在中途某次排序时向左移了）

Answer 1

以待排序序列 { 2， 5， 3， 4， 1} 为例，按非递减有序排列。

第一趟起泡排序过程如下：

初始：      2   5   3   4   1
第1次：     2   5   3   4   1
第2次：     2   3   5   4   1              3比最终位置前移了一个位置
第3次：     2   3   4   5   1              4比最终位置前移了一个位置
第4次：     2   3   4   1   5

通过第一趟的排序过程发现，3、4原来在索引为2、3的位置，但经过第一趟排序过程后，3、4暂时移动到了索引为1、2的位置。

C++程序如下：

#include "iostream"
#include "iomanip"

using namespace std;

//输出数组中的所有元素
void display(int arr[], int n)
{
int i;

for(i=0; i<n; i++)
{
cout<<setw(4)<<arr[i];
}
cout<<endl;
}

//起泡排序
void bubbleSort(int arr[], int n)
{
int i, j;
int temp;

for(i=0; i<n-1; i++)
{
for(j=0; j<n-1-i; j++)
{
if(arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}

cout<<"第"<<i+1<<"趟："<<endl;
display(arr, n);
}
}
 
int main()
{
    int arr[] = {2, 5, 3, 4, 1};
int n = 5;

cout<<"初始状态："<<endl;
display(arr, n);

bubbleSort(arr, n);
 
    return 0;
}

运行测试：

初始状态：
    2   5   3   4   1
第1趟：
    2   3   4   1   5
第2趟：
    2   3   1   4   5
第3趟：
    2   1   3   4   5
第4趟：
    1   2   3   4   5