选择排序顺序结构实现

朴灿烈づ我的快乐病毒、 2022-07-16 13:40 169阅读 0赞

2016年7月28日08:21:18
        选择排序算法思想描述:
        假设待排序的元素序列有n个,在第一趟排序的过程中,从n个元素中选择最小的元素,并将其放在元素序列最前面的位置,
        在第二趟排序的时候,从剩余的n-1个元素中选择最小的一个元素放在最前面的第二个位置,至到没有元素为止;
        假设数据为:[76,31,19,20]
        初始状态:[76,31,19,20];
        第一趟排序:令tempVal = 0,将76与后面的所有元素进行比较,31<S->data[tempVal],将tempVal = 1,继续往后进行比较,
                    19<S->data[tempVal],将tempVal = 2,继续往后进行比较,20<S->data[tempVal],不进行操作,继续往后进行比较
                    发现没有元素可以进行比较了,这时tempVal中保存了整个序列中最小元素的下标,将第一个位置的值和S->data[tempVal]
                    ___________________________________________________________
                    比较的时候若发现相等,那么为了保证排序的稳定性,就不做任何的操作,
                    继续往后进行比较,这个操作和大于情形相同;
                    ___________________________________________________________
                    进行交换位置,第一个最小值就保存到了第一个位置->[19,31,76,20];
        初始状态:[19,|31,76,20]
        第二趟排序:令tempVal = 1;将31与后面的所有元素进行比较,76>S->data[tempVal],不进行操作,继续往后进行比较,20<S->data[tempVal],
                    tempVal = 3,继续往后进行比较,发现没有可以比较的元素了,这时tempVal中保存了整个序列中最小元素的下标,
                    将该元素S->data[tempVal]与第二个位置的元素的值进行交换,次最小值就保存到了第二个位置->[19,20,76,31]
    
        初始状态:[19,20|,76,31]
        第三趟排序:令tempVal = 2,将76与后面的所有元素进行比较,31<S->data[tempVal];tempVal = 3;继续往后比较,
                   发现没有元素可以进行比较了,这时tempVal中保存了整个序列中最小元素的下标,将第三个位置的值和S->data[tempVal]
                   进行交换,->[19,20,31,|76]
        最后一个元素肯定就是最大值了;

#include<stdio.h>
    #include<stdlib.h>
    #define MAXISIZE 100
    #define random(x)(rand()%x)
    
    
    //顺序表结构体类型
    typedef struct 
    {
        int data[MAXISIZE];
        int length;
    }SeqList;
    
    //函数前置声明
    void initSeqList(SeqList * S);
    void seqListAssign(SeqList * S);
    void traverseSeqList(SeqList * S);
    void bubbleSort(SeqList * S);
    
    //交换两个数的数据
    void swapVal(int * p, int * q )
    {
        int tempVal;
        tempVal = *p;
        *p = *q;
        *q = tempVal;
        return;
    }
    
    //选择排序
    void selectIndexSort(SeqList * S)
    {
        int i;
        int j;
        int minIndex;
        for( i = 0;i<S->length-1;i++)
        {
            minIndex = i;
            //确定后面元素的最小下标
            for(j = i+1;j<S->length;j++)
            {
                if(S->data[j]<S->data[minIndex])
                {
                    minIndex = j;
                }
            }
            //将最小值和指定位置交换数值;
            swapVal(&S->data[i],&S->data[minIndex]);
        }
        return;
    }
    
    //选择排序
    void selectValueSort(SeqList * S)
    {
        int i;
        int j;
        int tempVal;
        for( i = 0;i<S->length-1;i++)
        {
            tempVal = S->data[i];
            //确定后面元素的最小下标
            for(j = i+1;j<S->length;j++)
            {
                if(S->data[j]<tempVal)
                {
                    tempVal = S->data[j];
                }
            }
            //将最小值和指定位置交换数值;
            swapVal(&S->data[i],&tempVal);
        }
        return;
    }
    
    //初始化顺序表
    void initSeqList(SeqList * S)
    {
        S->length = 0;
        return ;
    }
    
    //给顺序表赋值
    void seqListAssign(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 ;
    }
    
    //主函数
    int main(void)
    {
        SeqList S;
        initSeqList(&S);
        seqListAssign(&S);
        printf("产生的随机数据为:\n");
        traverseSeqList(&S);
        selectIndexSort(&S);
        //selectValueSort(&S);
        printf("排序后数据为:\n");
        traverseSeqList(&S);
        return 0;
    }