Insert sort

Insertion sort ：（ Small ones go forward ）

thought ：

Disordered sequence : 4  2  3  5  7  1  9  2  0 

                 i    j  //i、j Corresponding to the number pointing above ( If you don't know where the arrow symbol is, you don't draw it ）

                temp=2(j)   4>2,4 Move backward    j++

                2  4  3  5  7  1  9  2  0 // The red Is sorted

                     i   j //i It was orderly

                temp=3   3<4,4 Assign values to the 3 The location of     i--

                2  4  4  5  7  1  9  2  0

                         i   j

                2<3, Don't swap     3->i+1 The location of       j++,i->j-1

                 2  3  4  5  7  1  9  2  0

                             i   j

                temp=5      （i Value ）4<5,i There is no need to compare the front       j++,i->j-1;

                 2  3  4  5  7  1  9  2  0

                                  i   j

                temp=7;        5<7, No more exchanges

                 2  3  4  5  7  1  9  2  0

                                      i   j

                temp=1;          7>1; 7->j+1 Location         i--;        

                 .... 2>1; 5->i+1 Location

              i-1=-1<0;// Stop conditions

              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   

              

Code implementation ：

// Insertion sort

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] error , Every time j Everything has changed

        {

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

        }//i When I quit -1 Or the current 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;

}