插入排序

插入排序：（小的往前走）

思想：

无序序列: 4  2  3  5  7  1  9  2  0 

                 i    j  //i、j对应指向上面的数字(不知道箭头符号在哪就没有画出来）

                temp=2(j)   4>2,4后移   j++

                2  4  3  5  7  1  9  2  0 //标红为已排序

                     i   j //i之前有序

                temp=3   3<4,4赋值到3的位置    i--

                2  4  4  5  7  1  9  2  0

                         i   j

                2<3,不交换    3->i+1的位置      j++,i->j-1

                 2  3  4  5  7  1  9  2  0

                             i   j

                temp=5      （i的值）4<5,i前面就不用再比了      j++，i->j-1;

                 2  3  4  5  7  1  9  2  0

                                  i   j

                temp=7;        5<7,不用再交换了

                 2  3  4  5  7  1  9  2  0

                                      i   j

                temp=1;          7>1; 7->j+1位置        i--;        

                 .... 2>1; 5->i+1位置

              i-1=-1<0;//停止条件

              temp->i+1                j++;i->j-1

              1  2  3  4  5  7   9  2  0

                                        i   j

               .....

              0  1  2  2  3  4  5  7   9   

              

代码实现：

//插入排序

int InsertSort(int arr,int length) {

    for (int j = 1; j < length; j++)

    {

        int i = j - 1;

        int temp = arr[j];

        for (;arr[i] >temp && i>=0;i--) //arr[i] >arr[j]错误，每次j都改变啦

        {

            arr[i+1] = arr[i];

        }//i退出的时候是-1或者当前arr[i]>arr[j]

        //if（arr[i] <= arr[j] || i = 0）

            arr[i+1] = temp;

    }

}

int main() {

    int arr[] = { 4,2,3,5,7,1,9,2,0 };

    InsertSort(arr, sizeof(arr) / sizeof(arr[0]));

    return 0;

}