算法排序之插入排序找问题

Question

数组的数据换成{12,73,45,69,35}这组数据或者{5,4,3,2,1}这组数据可以成功从小到大排序，但就是换成{17,11,20,3,6}这组数据时，排不了序，输出的为11 11 20 3 6；就很好奇为什么，代码什么的都没有改过

#include<iostream>
using namespace std;
int main()
{//从小到大排序 
    int n,t,k;
//    int a[5]={12,73,45,69,35};//这组可以成功排序 
    int a[5]={17,11,20,3,6}; //这组不能成功排序 
//    int a[5]={5,4,3,2,1}; //这组可以成功排序 
    
    for(int i=1;i<5;i++)//无序区 
    {
        t=a[i];//取出无序区中的第一个数和有序区中比较
        for(int j=i-1;j>=0;j--)//有序区，将数组中的第一个数默认为有序区的数 
        {
            if(t>a[j])
            {
            //由于无序区的数比有序区的数大，那么直接退出循环
                k=j+1;
                break; 
//            有序区已经有了顺序，即判断当前无序区的数大于，则无序区的数不需要再和前面的有序数作比较 
            } 
            else
            {
                a[j+1]=a[j];
            }
        } 
//        将无序数比较好，找到位置了之后放进去 
        a[k]=t;
    }
    for(int i=0;i<5;i++)
    {
        cout<<a[i]<<" ";
    } 
} 

490020189846121.png _

Answer 1

只分析未正确排序的这次，不妨在每次修改后打印数组元素，然后就可以发现是在i = 3时的插入有问题，k未被正确赋值，仍为上一轮循环值，因此出错

#include<iostream>
using namespace std;
int main()
{//从小到大排序 
    int n = 0, t = 0, k = 0;
    //int a[5]={12,73,45,69,35};//这组可以成功排序 
    int a[5] = { 17,11,20,3,6 }; //这组不能成功排序 
    //int a[5]={5,4,3,2,1}; //这组可以成功排序 

    for (int i = 1; i < 5; i++)//无序区 
    {
        t = a[i];//取出无序区中的第一个数和有序区中比较
        for (int j = i - 1; j >= 0; j--)//有序区，将数组中的第一个数默认为有序区的数 
        {
            // k = j;
            if (t > a[j])
            {
                //由于无序区的数比有序区的数大，那么直接退出循环
                k = j + 1;
                break;
                //            有序区已经有了顺序，即判断当前无序区的数大于，则无序区的数不需要再和前面的有序数作比较 
            }
            else
            {
                a[j + 1] = a[j];
                for (int i = 0; i < 5; i++)
                {
                    cout << a[i] << " ";
                }
                cout << "\n\n";
            }
        }
        //        将无序数比较好，找到位置了之后放进去 
        a[k] = t;
        for (int i = 0; i < 5; i++)
        {
            cout << a[i] << " ";
        }
        cout << "\n\n";
    }
    for (int i = 0; i < 5; i++)
    {
        cout << a[i] << " ";
    }
}

然后可能因为编译器问题，我这边跑出来的结果还有些不一样

可通过在内循环首行赋值k = j解决该问题