【数据结构】插入排序

插入排序代码

插入排序，将数组分为两部分：有序，和无序的部分。如下面数组array={2, 5, 7, 4, 1, 3}，可以看出数组的{2,5,7}这三个数字时有序的；而{4,1,3}这三个数字是无序的。那么就需要对array数组无序的数字部分，往前依次进行比较。

#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 );        //调用选择排序方法 
    for( int i = 0; i < 10; i++ ) {
        cout << "array[" << i << "] = " << array[i] << endl;
    }
}

插入排序原理

案例讲解

数组

第一趟循环

第二趟循环

第三趟循环

再举如下案例

在第一层循环中：
1. array[1]和array[0]比较，array[1]<array[0]，则两数交换：array[0]=2,array[1]=6;
  第一层循环排序的结果为：
  2, 6, 8, 1, 4, 9, 3, 0, 5, 7
在第二层循环中：
1. array[2]和array[1]比较，array[2]>array[1]，则无需交换；内层循环终止；
  第二层循环排序的结果为：
  2, 6, 8, 1, 4, 9, 3, 0, 5, 7
在第三层循环中：
1. array[3]和array[2]比较，array[3]<array[2]，则两数交换：array[3]=8,array[2]=1;
2. array[2]和array[1]比较，array[2]<array[1]，则两数交换：array[2]=6,array[1]=1;
3. array[1]和array[0]比较，array[1]<array[0]，则两数交换：array[1]=2,array[0]=1;
  第三层循环排序的结果为：
  1, 2, 6, 8, 4, 9, 3, 0, 5, 7
在第四层循环中：
1. array[4]和array[3]比较，array[4]<array[3]，则两数交换：array[4]=8,array[3]=4;
2. array[3]和array[2]比较，array[3]<array[2]，则两数交换：array[3]=6,array[2]=4;
3. array[2]和array[1]比较，array[2]>array[1]，则无需交换；内层循环终止；
  第四层循环排序的结果为：
  1, 2, 4, 6, 8, 9, 3, 0, 5, 7
  ……
第八层排序结果：
0, 1, 2, 3, 4, 5, 6, 7, 9, 8
第九层排序结果：
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

综上可得：
升序排序中。外层循环循环i次(i从0开始)，内层循环将循环i+1次。令j=i+1，内层循环每循环一次，都将array[j]与array[j-1]比较。若需要交换，交换即可；若无需交换，则终止内层循环。

如果大家有什么问题，可以在评论区中向我提问。
今天更新的是插入排序，后天我会“选冒插”这三种排序进行归纳总结,其中会有学习数据结构的一些必要的基础知识。希望我的文章对大家有一定的帮助！

最后编辑于：2019.04.17 09:01:40