最近看到了一道非常有趣的排序问题，这个问题可以大概描述成这样，我们首先看下图。
这道题是这样的，在图书馆里面，有一个图书管理员需要针对一些图书进行排序，方便管理，但是排序的方法有很多，这个管理员就想到了这样一种方法，如上图所示。图书本来的序列是混乱的，最后我们期望得到的结果序列是有序的，但是这个排序的方法却和普通的排序不太相同，这个方法具体为：管理员拿出其中的一本书，然后按照这个书的序列号，放到相应的为止，其新位置的相关的书籍也随着移动（如果放到前面去了，后面的相应位置的书籍全部后移，如果放到后面去了，则前面的相应位置的书籍全部前移），一直重复这样操作，直到整个书本有序为止。
仔细看看上面的图和解释，理解这个方法应该没有多大的问题，但是问题来了，这样操作到底会不会出现死循环呢，会出现这种可能，所以到底这样排序对不对，还需要用大脑和数据来证明。
下面我给出一段代码来解释，希望能够提供到一些思路。
int a[10];
int init();
int sort();
int print();
int getright(); int main(int argc, char** argv) {
init();
print();
cout<<"============"<<endl;
sort();
print();
return 0;
} int init(){
a[0] = 3;
a[1] = 1;
a[2] = 2;
a[3] = 5;
a[4] = 4;
a[5] = 9;
a[6] = 7;
a[7] = 8;
a[8] = 6;
a[9] = 0;
return 0;
} int getright(){
for(int i=0;i<10;i++){
if(a[i]!=i)
return 0;
}
return 1;
} int sort(){
while(!getright())
{
for(int i=0;i<10;i++)
{
int value = a[i];
int index = i;
continue;
if(value>index)
{
int temp = value;
for(int j=index;j<value;j++)
{
a[j]=a[j+1];
}
a[temp]=temp;
}
else if(value<index)
{
int temp = value;
for(int j=index;j>value;j–)
{
a[j]=a[j-1];
}
a[temp]=temp;
}
}
}
return 0;
} int print(){
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
}
int sort();
int print();
int getright(); int main(int argc, char** argv) {
init();
print();
cout<<"============"<<endl;
sort();
print();
return 0;
} int init(){
a[0] = 3;
a[1] = 1;
a[2] = 2;
a[3] = 5;
a[4] = 4;
a[5] = 9;
a[6] = 7;
a[7] = 8;
a[8] = 6;
a[9] = 0;
return 0;
} int getright(){
for(int i=0;i<10;i++){
if(a[i]!=i)
return 0;
}
return 1;
} int sort(){
while(!getright())
{
for(int i=0;i<10;i++)
{
int value = a[i];
int index = i;
if(value==index)
continue;
//value大于index
if(value>index)
{
int temp = value;
for(int j=index;j<value;j++)
{
a[j]=a[j+1];
}
a[temp]=temp;
}
else if(value<index)
{
int temp = value;
for(int j=index;j>value;j–)
{
a[j]=a[j-1];
}
a[temp]=temp;
}
}
}
return 0;
} int print(){
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
}
}
