栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

单向链表的实现--排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

单向链表的实现--排序

本想先用快速排序算法对一个数组的元素从小到大进行排序,然后把快速排序算法用于链表元素从小到大进行排序的,但是发现一个问题改变了我的想法,先把问题呈上。

volatile uint16_t count = 0;//统计递归执行的次数
volatile uint16_t num   = 0;//统计快速算法进行排序时执行的次数

//快速排序算法--从小到大依次排序
void quickSort(uint8_t *dataBuf,uint8_t leftSub,uint8_t rightSub)
{
        uint8_t left,right,temp;
        uint8_t keyNum;

        left          = leftSub;
        right        = rightSub;
        keyNum  = dataBuf[(leftSub+rightSub)/2];
        ++count;

        while(left <= right)
        {
                ++num;
                //从左到右找比keyNum大的元素
                while((dataBuf[left] < keyNum) && (left < rightSub))
                {
                    left++;
                }
                //从右到左找比keyNum小的元素
                while((dataBuf[right] > keyNum) && (right > leftSub))
                {
                    right--;
                }

                //若找到且满足条件的,则交换
                if(left <= right)
                {
                    temp = dataBuf[left];
                    dataBuf[left] = dataBuf[right];
                    dataBuf[right] = temp;
                    left++;
                    right--;
                }
        }

        if(left < rightSub)
        {
             quickSort(dataBuf,left,rightSub);
        }

        if(right >leftSub)
        {
             quickSort(dataBuf,leftSub,right);
        }
}

int main()
{
   uint8_t data[]={8,2,5,3,4,6,9,1,7};//组1:8,2,5,3,4,6,9,1,7    组2:9,7,8,6,5,4,2,3,1

    quickSort(data,0,sizeof(data)-1);//把数组,最左下标和最有下标作为参数传入快速排序函数中

    printf("count=%d,num=%d rn",count,num);
    
    for(uint8_t index = 0;index < sizeof(data);index++)
     {
        printf("%d ",data[index]);
     }
     return 0;
}

数组元素经过从小到大的排序后,输出打印显示如下所示,

 我们可以看到,对这样一组数据data[]={8,2,5,3,4,6,9,1,7}进行排序,调用快速排序算法函数调了6次,内部总共执行了9次完成了从小到大的排序,这种情况是比较理想的,如果我们把data数组的元素换成组2的元素,再打印结果,出乎了我们的预料,打印结果如下:

我们可以看到,用快速算法对数组data[]={9,7,8,6,5,4,2,3,1}从小到大进行排序,发现调用快速算法函数72次,内部总共执行510次,程序没有继续执行,发生异常了,如果在程序中使用快速算法,会导致程序内存溢出,程序崩溃等故障,所以在这里(单向链表元素数据项进行排序)就不用快速排序算法, 网上查了一下几种排序算法的稳定性,可以看到,插入、冒泡、堆、归并和基数排序是稳定的。

这里我们选择插入式排序对单向链表的元素数据项从小到大进行排序,首先还是先用插入排序对一个数组进行从小到大进行排序,然后在这个排序算法函数中把数组改为单向链表。

//快速排序算法--从小到大依次排序
void InsertSort(uint8_t *dataBuf,uint16_t length)
{
        int right = 0;
        int left   = 0;
        uint8_t temp = 0;
        for(right = 1;right < length;right++)
        {
             temp = dataBuf[right];//从无序待插入组取出第一个元素。
             left    = right-1;            //i-1即为有序组最后一个元素(与无序待插入元素相邻)的下标
             while((left >= 0)&&(temp < dataBuf[left]) )//注意判断条件为两个,left>=0对其进行边界限制。第二个为插入判断条件,右<左
             {
                  dataBuf[left+1] = dataBuf[left];//有序组元素向后移动,空出预插入无序组的第一个元素(temp装的值)
                  left--;
             }
             dataBuf[left+1] = temp;//找到合适位置,将元素插入。
             ArrayPrintShow(dataBuf,length);
        }
}

//信息打印显示
void ArrayPrintShow(uint8_t *data,uint16_t len)
{
    for(uint8_t index = 0;index < len;index++)
    {
        printf("%d ",data[index]);
    }
    printf("rn");
}


int main()
{
    uint8_t data[]={9,7,8,6,5,4,2,3,1};
    
    printf("原始数组排序如下:rn");
    ArrayPrintShow(data,sizeof(data));

    printf("rn数组经过排序如下:rn");
    InsertSort(data,sizeof(data));//把数组,最左下标和最有下标作为参数传入快速排序函数中
    return 0;
}

数组经过从小到大进行排序后,打印结果如下所示:

 下面我们就在这个插入方法中对前面讲的单向链表中的图书价格进行从小到达进行排序,最后再输出打印显示。

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/979472.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号