插入排序代碼

插入排序，將數(shù)組分為兩部分：有序，和無序的部分。如下面數(shù)組array={2, 5, 7, 4, 1, 3}，可以看出數(shù)組的{2,5,7}這三個(gè)數(shù)字時(shí)有序的；而{4,1,3}這三個(gè)數(shù)字是無序的。那么就需要對array數(shù)組無序的數(shù)字部分，往前依次進(jìn)行比較。

#include<iostream>
using namespace std;
swap( int array[], int j ) {    //交換方法 
    int temp = array[j];
    array[j] = array[j-1];
    array[j-1] = temp;
}
void insertSort( int array[] ) {//選擇排序方法 
    for( int i = 0; i < 9; i++ ) {
        for( int j = i+1; j > 0; j-- ) {
            if( array[j] < array[j-1] ) {
                swap( array, j );
            }
            else {
                break;
            }
        }
    }
} 
int main() {
    int array[] = {6, 2, 8, 1, 4, 9, 3, 0, 5, 7};
    insertSort( array );        //調(diào)用選擇排序方法 
    for( int i = 0; i < 10; i++ ) {
        cout << "array[" << i << "] = " << array[i] << endl;
    }
}

插入排序原理

案例講解

數(shù)組

第一趟循環(huán)

第二趟循環(huán)

第三趟循環(huán)

再舉如下案例

1. 在第一層循環(huán)中：
   1. array[1]和array[0]比較，array[1]<array[0]，則兩數(shù)交換：array[0]=2,array[1]=6;
      第一層循環(huán)排序的結(jié)果為：
      2, 6, 8, 1, 4, 9, 3, 0, 5, 7
2. 在第二層循環(huán)中：
   1. array[2]和array[1]比較，array[2]>array[1]，則無需交換；內(nèi)層循環(huán)終止；
      第二層循環(huán)排序的結(jié)果為：
      2, 6, 8, 1, 4, 9, 3, 0, 5, 7
3. 在第三層循環(huán)中：
   1. array[3]和array[2]比較，array[3]<array[2]，則兩數(shù)交換：array[3]=8,array[2]=1;
   2. array[2]和array[1]比較，array[2]<array[1]，則兩數(shù)交換：array[2]=6,array[1]=1;
   3. array[1]和array[0]比較，array[1]<array[0]，則兩數(shù)交換：array[1]=2,array[0]=1;
      第三層循環(huán)排序的結(jié)果為：
      1, 2, 6, 8, 4, 9, 3, 0, 5, 7
4. 在第四層循環(huán)中：
   1. array[4]和array[3]比較，array[4]<array[3]，則兩數(shù)交換：array[4]=8,array[3]=4;
   2. array[3]和array[2]比較，array[3]<array[2]，則兩數(shù)交換：array[3]=6,array[2]=4;
   3. array[2]和array[1]比較，array[2]>array[1]，則無需交換；內(nèi)層循環(huán)終止；
      第四層循環(huán)排序的結(jié)果為：
      1, 2, 4, 6, 8, 9, 3, 0, 5, 7
      ……
5. 第八層排序結(jié)果：
   0, 1, 2, 3, 4, 5, 6, 7, 9, 8
6. 第九層排序結(jié)果：
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9

綜上可得：
升序排序中。外層循環(huán)循環(huán)i次(i從0開始)，內(nèi)層循環(huán)將循環(huán)i+1次。令j=i+1，內(nèi)層循環(huán)每循環(huán)一次，都將array[j]與array[j-1]比較。若需要交換，交換即可；若無需交換，則終止內(nèi)層循環(huán)。

如果大家有什么問題，可以在評論區(qū)中向我提問。
今天更新的是插入排序，后天我會“選冒插”這三種排序進(jìn)行歸納總結(jié),其中會有學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的一些必要的基礎(chǔ)知識。希望我的文章對大家有一定的幫助！