问下插入排序

Question

void InsertSort()
{
int i,j,x;
for(i=1;i<n;i++){
      x=a[i]; //将此次待插入的元素存入x
     for(j=i-1;j>=0;j--)   //为x顺序向前寻找插入位置
           if(x<a[j])  a[j+1]=a[j];else break;
         a[j+1]=x;   //将x插入到已找到的插入位置
    }
}
       请问下这个插入排序为什么要把x放到a[j+1],而不是a[j];谢谢！我现在老是感觉x小于a[j],然后a[j]向后移了一位，应该把x放在a[j]里面啊

Answer 1

跳出循环的条件是什么？是x>=a[j],所以x要放在a[j+1]里。

Answer 2

你明白插入排序的意思吗？
首先插入排序的核心思想是插入一个标志位置，标志位置的左侧是有序的队列。
然后将这个标志位置插入到左侧有序的队列中，然后这个标志位置右移动。
a[j+1]=x;的意思就是标志位右移。

Answer 3

不好意思a[j+1]=x;的意思就是标志位右移解释不正确。

Answer 4

重写了下，你看下。void InsertSort() 
{ 
int i,j; 
for(i=1;i<n;i++){ 
     int x=a[i];
     j=i; 
    while(j>0&&a[j-i]>=x){
     a[j]=a[j-1];
      --j;
       }
     a[j]=x;
    } 
}