直接插入排序顺序结构

心已赠人 2022-07-16 13:41 131阅读 0赞

2016年7月27日18:13:11 假设用户数据为:[22,6,17,8] 直接插入排序的思想是:将待排序元素分为已排序子集和未排序子集,依次从未排序子集中取出一个元素 插入到已排序子集的合适的位置,使得已排序的子集任然为有序子集,当未排序的 子集为空时,排序结束 初始时:[22,|6,17,8] 将t = 6;
        第一趟排序:[22,|22,17,8];将6与22比较->发现6<22,将22向后移动;将6插入到第一个位置[6,22,|17,8]
        状态:[6,22,|17,8] 将t = 17;
        第二趟排序:[6,22,|22,8];将17与22比较->发现17<22,将22向后移动;在将17与6比较->发现17>6;将17插入到6的后面:[6,17,22|,8] 状态:[6,17,22|,8] 将t = 8;
        第三趟排序:[6,17,22|,22]将8与22比较->发现8<22,将22向后移动;将8与17比较->发现8<17,将17向后移动[6,17,17|,22]
        将8与6比较->发现8>6,将元素插入到6的后面[6,8,17,22|]
        此时发现未排序的子集为空,算法结束;

#include<stdio.h>
    #include<stdlib.h>
    #define random(x)(rand()%x)
    #define MAXISIZE 100
    
    //顺序表的结构体类型
    typedef struct 
    {
        int data[MAXISIZE];
        int length;
    }SeqList;
    
    //函数前置声明
    void insertSort(SeqList * S);
    void initSeqList(SeqList * S);
    void setSeqList(SeqList * S,int len);
    void traverseSeqList(SeqList * S);
    void traverseSeqList1(SeqList * S);
    
    //给顺序表中元素进行1-1000整数的随机赋值
    void setSeqList1(SeqList * S)
    {
        int i;
        for(i = 0;i<MAXISIZE;i++)
        {
            S->data[i] = random(1000);
        }
        S->length = MAXISIZE;
        return;
    }
    
    //遍历顺序表中的元素
    void traverseSeqList(SeqList * S)
    {
        int i;
        for( i = 0;i<S->length;i++)
        {
            printf("%-6d",S->data[i]);
    
        }
        printf("\n");
        return;
    }
    
    //给顺序表中的元素进行赋值
    void setSeqList(SeqList * S,int len)
    {
        int i;
        for(i = 0;i<len;i++)
        {
            printf("请输入第%d个元素:",i+1);
            scanf("%d",&S->data[i]);
        }
        S->length = i;
        return;
    }
    
    //顺序表的初始化
    void initSeqList(SeqList * S)
    {
        S->length = 0;
    }
    
    //直接插入排序
    void insertSort(SeqList * S)
    {
        int i;
        int j;
        int tempVal;
        for( i = 1;i<S->length;i++)
        {
            tempVal = S->data[i];
            for( j = i-1;j>=0&&tempVal<S->data[j];j--)
            {
                /*
                    if(tempVal<S->data[tempVal-1])
                        S->data[tempVal] = S->data[tempVal-1];
                    if(tempVal>S->data[tempVal-1])
    
                    if(tempVal<S->data[tempVal-2])
                        S->data[tempVal-1] = S->data[tempVal-2];
                        ......
                    if(tempVal<S->data[0])
                        S->data[1] = S->data[0]; 
                */
                if(tempVal<S->data[j])
                    S->data[j+1] = S->data[j]; 
            }
            S->data[j+1] = tempVal;
        }
        return ;
    }
    
    int main(void)
    {
        int len;
        SeqList S;
        initSeqList(&S);
        /*printf("请输入您需要排序的数据的个数:len=");
        scanf("%d",&len);*/
        setSeqList1(&S);
        printf("您所输入的数据为:\n");
        traverseSeqList(&S);
        insertSort(&S);
        printf("排序后的数据为:\n");
        traverseSeqList(&S);
    
    
    
        return 0;
    }