问题标题: 插入排序

课堂内容

1. 插入排序：

1. 基本原理

与平时玩扑克牌整理手中牌的顺序的过程类似。

从第二张牌开始每次从桌上拿起一张牌，这张新牌与前面已经拍好顺序的牌进行比较，然后插入正确的位置。

 

2. 代码实现

从小到大排序：

for(int i=2;i<=n;i++)//从第二张牌开始，到第n张

{

key=a[i];      //先将第i张牌存放起来，方便挪动

j=i-1;

while(j>=1&&key<a[j])

{

a[j+1]=a[j];

j--;

}

//从第i-1张牌到第1张牌的范围，将顺序错乱的牌后挪

a[j+1]=key;     //将第i张牌挪入正确位置

}

 

从大到小排序：

for(int i=2;i<=n;i++)

{

key=a[i];

j=i-1;

while(j>=1&&key>a[j])

{

a[j+1]=a[j];

j--;

}

a[j+1]=key;

}

 

从小到大排序与从大到小排序的区别是while循环的条件不同，

从小到大是key<a[j];

从大到小是key>a[j].

 

 

2. 例题讲解

1711 考试成绩排名

#include<iostream>

using namespace std;

int a[55];

int main()

{

      int n,key,j;

      cin>>n;

      for(int i=1;i<=n;i++)

            cin>>a[i];

      for(int i=2;i<=n;i++)

      {

            key=a[i];

            j=i-1;

            while(j>=1&&key>a[j])

            {

                  a[j+1]=a[j];

                  j--;

            }

            a[j+1]=key;

      }

      for(int i=1;i<=n;i++)

            cout<<a[i]<<' ';

    return 0;

}

 

3880 站队啦

#include<iostream>

using namespace std;

int a[8010];

int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=2*n;i++)

        cin>>a[i];

    for(int i=n+1;i<=n+m;i++) {

        int key=a[i];

        int j=i-1;

        while(key<a[j]&&j>=1){

            a[j+1]=a[j];

            j--;

        }

        a[j+1]=key;

    }

    for(int i=1;i<=n+m;i++)

        cout<<a[i]<<' ';

    return 0;

}

 

3. 课后作业 （使用插入排序完成）

3883 2450 1068 3887