专栏首页图灵技术域数据结构7种排序算法(无基数排序)

数据结构7种排序算法(无基数排序)

一、实验目的 掌握多种排序方法的基本思想,包括直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等,并能够用高级语言实现。通过对这些算法效率的比较,加深对算法的理解。 二、实验原理

三.实验内容 用随机数(介于1-100)产生10个待排序数据元素的关键字值)。 ① 采用直接插入排序和希尔排序方法对上述待排数据进行排序并输出序后的有序序列; ② 采用冒泡排序、快速排序方法对上述待排数据进行排序并输出序后的有序序列; ③ 采用简单选择排序、堆排序方法对上述待排数据进行排序并输出序后的有序序列; ④ 采用归并排序方法对上述待排数据进行排序并输出排序后的有序序列;

头文件:

C++

#include<cstdio>
#include<iostream>
#include<cstdlib>
 
#define MAXSIZE 100
 
using namespace std;
 
typedef int KeyType;
typedef int InfoType;
 
typedef struct{
    KeyType key;
    InfoType otherinfo;
}RedType;
 
typedef struct{
    RedType r[MAXSIZE+1];
    int length;
}SqList;

①插入排序

C++

void InsertSort(SqList &L)
{
    int i,j,a=0,b=0;
    for(i=1;i<=L.length;++i)
    {
        if(L.r[i].key<L.r[i-1].key)
        {
            L.r[0]=L.r[i];
            L.r[i]=L.r[i-1];
            a++;
        }
        for(j=i-2;L.r[0].key<L.r[j].key;--j)
            L.r[j+1]=L.r[j];b++;
        L.r[j+1]=L.r[0];
    }
    cout<<"比较次数:"<<a<<"移动次数:"<<b<<endl;
}

②折半插入排序

C++

void BInsertSort(SqList &L)
{
    int low,high,m;
    for(int i=2;i<=L.length;++i)
    {
        L.r[0]=L.r[i];
        low=1;high=i-1;
        while(low<=high)
        {
            m=(low+high)/2;
            if(L.r[0].key<L.r[m].key)high=m-1;
            else low=m+1;
        }
        for(int j=i-1;j>=high+1;--j)
            L.r[j+1]=L.r[j];
        L.r[high+1]=L.r[0];
    }
}

③选择排序

C++

void SelectSort(SqList &L)
{
    int j,k;
    for(int i=1;i<=L.length;++i)
    {
        k=i;
        for(j=i+1;j<=L.length;j++)
            if(L.r[j].key<L.r[k].key)k=j;
        if(k!=i)
        {
            L.r[0].key=L.r[i].key;
            L.r[i].key=L.r[k].key;
            L.r[k].key=L.r[0].key;
        }
    }
}

④起泡排序

C++

void BubbleSort(SqList &L)
{
    int i,j;
    for(i=1;i<=L.length;++i)
    {
        for(j=1;j<L.length-i+1;++j)
        {
            if(L.r[j+1].key<L.r[j].key)
            {
                L.r[0].key=L.r[j].key;
                L.r[j].key=L.r[j+1].key;
                L.r[j+1].key=L.r[0].key;
            }
        }
    }
}

⑤快速排序

C++

int Partition(SqList &L,int low,int high)
{
    L.r[0]=L.r[low];
    KeyType pivotkey=L.r[low].key;
    while(low<high)
    {
        while(low<high&&L.r[high].key>=pivotkey)--high;
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=pivotkey)++low;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0];
    return low;
}
 
void QSort(SqList &L,int low,int high)
{
    if(low<high)
    {
        int pivotloc=Partition(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
    }
}

⑥希尔排序

C++

void ShellInsert(SqList &L,int dk)
{
        int i,j;
        for(i=dk+1;i<=L.length;++i)
        {
            if(L.r[i].key<L.r[i-dk].key){L.r[0]=L.r[i];
            for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
                L.r[j+dk]=L.r[j];
            L.r[j+dk]=L.r[0];
            }
        }
}
 
void ShellSort(SqList &L,int dlta[],int t)
{
    for(int k=0;k<t;++k)
        ShellInsert(L,dlta[k]);
}

⑦堆排序

C++

typedef SqList HeapType;
void HeapAdjust(HeapType &H,int s,int m)
{
    RedType rc=H.r[s];int j;
    for(j=2*s;j<=m;j*=2)
    {
        if(j<m&&H.r[j].key<H.r[j+1].key)++j;
        if(!(rc.key<H.r[j].key))break;
        H.r[s]=H.r[j];s=j;
    }
    H.r[s]=rc;
}
void HeapSort(HeapType &H)
{
    int i;
    RedType temp;
    for(i=H.length/2;i>0;--i)
        HeapAdjust(H,i,H.length);
    for(i=H.length;i>1;--i)
    {
        temp=H.r[1];
        H.r[1]=H.r[i];
        H.r[i]=temp;
        HeapAdjust(H,1,i-1);
    }

⑧归并排序

void Merge(RedType SR[],RedType &TR[],int i,int m,int n)
{
    int j,k;
    for(j=m+1,k=i;i<=m&&j<=n;++k)
    {
        if(SR[i].key<=SR[j].key)
            TR[k]=SR[i++];
        else
            TR[k]=SR[j++];
    }
    int t;
    if(i<=m)
    {
        for(t=i;t<=m;t++)
            TR[k+t-i]=SR[t];
    }
    if(j<=n)
    {
        for(t=j;t<=m;t++)
            TR[k+t-j]=SR[t];
    }
}
 
void MSort(RedType SR[],RedType *TR1,int s,int t)
{
    int m;
    RedType TR2[MAXSIZE+1];
    if(s==t)TR1[s]=SR[s];
    else{
        m=(s+t)/2;
        MSort(SR,TR2,s,m);
        MSort(SR,TR2,m+1,t);
        Merge(TR2,TR1,s,m,t);
    }
}
void MergeSort(SqList &L)
{
    MSort(L.r,L.r,1,L.length);
}

随机生成函数

C++

void RandSqList(SqList &L)
{
    int n,max,min;
    printf("输入顺序表的大小\n");
    cin>>n;
    printf("输入最小值和最大值\n");
    cin>>min>>max;
    L.length=n;
    printf("随机产生%d个数\n",n);
    for(int i=1;i<=L.length;++i)
    {
        L.r[i].key=rand()%(max-min+1);
        L.r[i].key+=min;
    }
    printf("顺序表创建成功!\n");
}

输出函数

C++

void Output(SqList L)
{
    printf("输出:\n");
    for(int i=1;i<=L.length;i++)
        cout<<"data"<<"["<<i<<"]"<<": "<<L.r[i].key<<endl;
}

四.实验小结 (1)若n较小(例如n<50),可采用直接插入排序、冒泡排序或简单选择排序。如果记录中的数据较多,移动较费时的,应采取简单选择排序法。

(2)若记录的初始状态已经按关键码基本有序,则选用直接插入排序或冒泡排序法为宜。

(3)若n较大,则应采用改进排序方法,如快速排序、堆排序或归并排序法。这些排序算法的时间复杂度均为O(nlog2n),但就平均性能而言,快速排序被认为是目前基于比较记录关键码的内部排序中最好的排序方法,但遗憾的是,快速排序在最坏情况下的时间复杂度是O(n2),堆排序与归并排序的最坏情况时间复杂度仍为O(nlog2n)。堆排序和快速排序法都是不稳定的排序。若要求稳定排序,则可选用归并排序。

(4)基数排序可在O (d×n) 时间内完成对n个记录的排序,d是指单逻辑关键码的个数,一般远少于n。但基数排序只适用于字符串和整数这类有明显结构特征的关键码。

(5)前面讨论的排序算法,除基数排序外,都是在顺序存储上实现的。当记录本身的信息量很大时,为避免大量时间用在移动数据上,可以用链表作为存储结构。插入排序和归并排序都易在链表上实现,但有的排序方法,如快速排序和堆排序在链表上却很难实现。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript 数据结构与算法之美 - 桶排序、计数排序、基数排序

    笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便以后复习。

    夜尽天明
  • 数据结构(九)——排序算法

    上篇文章给大家介绍数据结构中一个较为常用的思想——递归。主要介绍了递归的相关概念以及通过一些案例来进一步说明递归的用法。本文介绍数据结构中排序的算法。其实我们在...

    一计之长
  • 数据结构基础温故-7.排序

    排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

    Edison Zhou
  • 算法与数据结构(五):基本排序算法

    排序是将一组无序的数据根据某种规则重新排列成有序的这么一个过程,当时在大学需要我们手工自己实现的主要有三种:选择排序、插入排序和冒泡排序。因为它比较简单,所以这...

    Masimaro
  • 算法和数据结构: 二 基本排序算法

    本篇开始学习排序算法。排序与我们日常生活中息息相关,比如,我们要从电话簿中找到某个联系人首先会按照姓氏排序、买火车票会按照出发时间或者时长排序、买东西会按照销量...

    yaphetsfang
  • 排序算法-基数排序

    排序算法-基数排序 <?php /** * php算法实战. * * 排序算法-基数排序 * * 分为两种LSD,MSD * * LSD: * ...

    guanguans
  • 排序算法 --- 基数排序

    基数排序是桶排序的扩展,它将所有待排序的数值统一为同样的数位长度,数位较短的前面补0,然后从最低位开始,依次进行一次排序。这样从最低为排序一直到最高位排序完成后...

    贪挽懒月
  • 【数据结构】七大排序算法

    排序的相关概念 排序的分类 根据在排序过程中带排序的记录是否全部被放置在内存中,排序分为: 内排序 外排序 1.内排序 内排序是在排序整个过程中,带排序的所有...

    我就是马云飞
  • 数据结构 插入排序算法

    插入排序算法是所有排序方法中最简单的一种算法,其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据。

    Meng小羽
  • 算法和数据结构:堆排序

    在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象。最简单的一个例子就是,在手机上玩游戏的时候,如果...

    yaphetsfang
  • Java数据结构与算法--排序算法

    常见的五种排序算法: 冒泡排序;选择排序;插入排序;归并排序;快速排序; 前三种是基本排序算法,后两个是高级的排序算法;

    Java编程指南
  • 排序算法(十):基数排序

    基数排序也可以称为多关键字排序,同计数排序类似,也是一种非比较性质的排序算法。将待排序集合中的每个元素拆分为多个总容量空间较小的对象,对每个对象执行桶排序后,则...

    zhipingChen
  • 算法渣-排序-基数排序

    需要注意的是线性排序算法是非基于比较的排序算法,都有使用限制才能达到线性排序的效果

    码农戏码
  • 数据结构-常用的排序算法

    好久不见哈,我终于又更新了,惊不惊喜,意不意外,哈哈哈哈。等之后会专门写一篇文章给大家汇报汇报我最近在忙什么呢,今天这篇还是接着之前的数据结构系列继续,主要讲讲...

    张俊红
  • 算法与数据结构(六):堆排序

    上一次说到了3种基本的排序算法,三种基本的排序算法时间复杂度都是O(n^2),虽然比较简单,但是效率相对较差,因此后续有许多相应的改进算法,这次主要说说堆排序算...

    Masimaro
  • 数据结构与算法-拓扑排序

    为了保证总项目的顺利进行,必须要对这些子项目进行一定的先后顺序规化,为了解决这类问题,我们可以采用拓扑排序的方法。

    越陌度阡
  • 数据结构与算法-键盘排序

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • 数据结构和算法——选择排序

    选择排序的工作方式是:维护已排序的子列表,从主列表中找到最小的项,然后将其交换到子列表的最后一个元素,直到对所有项进行排序为止。

    Lemon黄
  • 数据结构和算法——贝壳排序

    贝壳排序是插入排序的概括。与插入排序不同,它不比较连续项目,而是使用间隔i(称为间隔)将主列表分成几个子列表,然后使用插入排序对子列表进行排序。

    Lemon黄

扫码关注云+社区

领取腾讯云代金券