devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【排序算法】七种排序算法的C++实现_排列c++实现

作者：AllinToyou | 2024-03-21 03:26:21

赞

踩

排列c++实现

通信工程的小伙伴请看文章使用说明

七种算法

(1) 插入类排序：直接插入排序、希尔排序
(2) 交换类排序：冒泡排序、快速排序
(3) 选择类排序：简单选择排序、堆排序
(4) 归并类排序：递归归并排序

数据结构定义

在这里插入图片描述

算法思想及实验代码

插入排序

直接插入排序：先判断目标位置的是否大于前面有序子列的最后一个元素，若不大于，则将0号位置设置为哨兵，把要插入的数据赋给它；插入数据从后面开始比较，如果大于前面的就记录下标，并将数据后移，直到插入数据碰到比它小的；最后将哨兵赋值给当前记录下标。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;
void InsertSort(Sqlist&list)
{
    int i,j;
    for(i=2;i<=list.length;++i)
    {
        if(list.data[i].key<list.data[i-1].key)
        {
            list.data[0].key=list.data[i].key;
            list.data[i].key=list.data[i-1].key;
            for(j=i-1;list.data[0].key<list.data[j].key;--j)
                list.data[j+1].key=list.data[j].key;
            list.data[j+1].key=list.data[0].key;
        }
    }
}
int main()
{
    int n;
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"直接插入排序如下"<<endl;
    InsertSort(list);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
希尔排序

先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;
void ShellInsert(Sqlist&list,int dk)
{
    int i,j;
    for(i=dk+1;i<=list.length;++i)
    {
        if(list.data[i].key<list.data[i-dk].key)
        {
            list.data[0]=list.data[i];
            for(j=i-dk;j>0&&(list.data[0].key<list.data[j].key);j=j-dk)
                list.data[j+dk]=list.data[j];
            list.data[j+dk]=list.data[0];
        }
    }
}
void ShellSort(Sqlist&list,int dlta[],int t)
{
    for(int k=0;k<t;++k)
        ShellInsert(list,dlta[k]);
}
int main()
{
    int n;
    int dlta[3]={5,3,1};
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"希尔排序如下"<<endl;
    ShellSort(list,dlta,3);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
简单选择排序

记录数组第一个元素的下标为最小值，从下一位进行遍历，若出现比它小的元素，则记下该处的下标，最后内循环结束，若最小值下标的值改变了，则交换两个元素，这次循环结束。之后再依次访问以下一个元素的第一个元素的子序列，进行循环。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef int Pos;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;
void SelectSort(Sqlist&list)
{
    int i,j,k;
    ElemType temp;
    for(i=1;i<list.length;++i)
    {
        k=i;
        for(j=i+1;j<=list.length;++j)
        {
            if(list.data[j].key<list.data[k].key)
                k=j;
        }
        if(k!=i)
        {
            temp=list.data[k];
            list.data[k]=list.data[i];
            list.data[i]=temp;
        }
    }
}

int main()
{
    int n;
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"选择排序如下"<<endl;
    SelectSort(list);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
堆排序

首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1；将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行即可。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef int Pos;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;

void HeapAdjust(Sqlist&list,int s,int n)
{
    ElemType root=list.data[s];
    for(int i=s*2;i<=n;i*=2)
    {
        if(i<n&&list.data[i].key>list.data[i+1].key)
            ++i;
        if(root.key<list.data[i].key)
            break;
        list.data[s]=list.data[i];
        s=i;
    }
    list.data[s]=root;
}

void HeapSort(Sqlist&list)
{
    ElemType temp;
    for(int i=list.length/2;i>0;--i)
        HeapAdjust(list,i,list.length);
    for(int j=list.length;j>1;--j)
    {
        temp=list.data[1];
        list.data[1]=list.data[j];
        list.data[j]=temp;
        HeapAdjust(list,1,j-1);
    }  
}

int main()
{
    int n;
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"堆排序如下"<<endl;
    HeapSort(list);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
冒泡排序

每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。而每一趟都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;
void BubbleSort(Sqlist&list)
{
    int i,j,flag=1;
    ElemType temp;
    for(i=1;i<=list.length&&flag;++i)
    {
        flag=0;
        for(j=1;j<=list.length-i;++j)
        {
            if(list.data[j].key>list.data[j+1].key)
            {
                flag=1;
                temp=list.data[j];
                list.data[j]=list.data[j+1];
                list.data[j+1]=temp;
            }
        }
    }
}
int main()
{
    int n;
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"冒泡排序如下"<<endl;
    BubbleSort(list);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
快速排序

通过一趟排序将待排序序列分隔成独立的两部分，将序列第一个元素设置为基准pivot，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef int Pos;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;
Pos Partition(Sqlist&list,int low,int high)
{
    list.data[0]=list.data[low];
    int pivotkey=list.data[low].key;
    while(low<high)
    {
        while(low<high&&list.data[high].key>=pivotkey)
            --high;
        list.data[low]=list.data[high];
        while(low<high&&list.data[low].key<=pivotkey)
            ++low;
        list.data[high]=list.data[low];
    }
    list.data[low]=list.data[0];
    return low;
}
void QuickSort(Sqlist&list,int low,int high)
{
    int pivotloc;
    if(low<high)
    {
        pivotloc=Partition(list,low,high);
        QuickSort(list,low,pivotloc-1);
        QuickSort(list,pivotloc+1,high);
    }
}
int main()
{
    int n;
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"快速排序如下"<<endl;
    QuickSort(list,1,list.length);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
递归归并排序

对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，合并成一个大的分组，逐层进行，最终所有的元素都是有序的。

#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef int InfoType;
typedef int Pos;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE+1];
    int length;
}Sqlist;

void MergeSort(Sqlist&list,int left,int right)
{
    if(left>=right)
        return;

    int mid=(left+right)/2;
    MergeSort(list,left,mid);
    MergeSort(list,mid+1,right);
    Sqlist temp;
    int k=left,i=left,j=mid+1;
    while(i<=mid&&j<=right)
    {
        if(list.data[i].key<=list.data[j].key)
            temp.data[k++]=list.data[i++];
        else
            temp.data[k++]=list.data[j++];
    }
    while (i<=mid)
        temp.data[k++]=list.data[i++];
    while(j<=right)
        temp.data[k++]=list.data[j++];
    for(int i=left;i<=right;++i)
    {
        list.data[i]=temp.data[i];
    }
}

int main()
{
    int n;
    Sqlist list;
    cout<<"共输入几个元素：";
    cin>>n;
    list.length=n;
    cout<<"依次输入元素的值：";
    for(int i=1;i<=n;++i)
        cin>>list.data[i].key;
    cout<<"归并排序如下"<<endl;
    MergeSort(list,1,list.length);
    for(int i=1;i<=n;++i)
        cout<<list.data[i].key<<' ';
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

分析与总结

算法分析
插入排序时间复杂度在最好情况下为O(n)，最坏情况下为O(n2)，平均情况下为O(n2)。总体来看，时间复杂度较高，属于稳定的排序。
希尔排序时间复杂度在最好情况下为O(n)，最坏情况下为O(n2)，平均情况下为O(n1.3)左右。总体来看，时间复杂度优于插入排序，但是它属于不稳定的排序
选择排序时间复杂度在最好情况下为O(n)，最坏情况下为O(n2)，平均情况下为O(n2)。总体来看，时间复杂度较高，属于稳定的排序。
堆排序时间复杂度在最好情况下为O(nlogn)，最坏情况下为O(nlogn)，平均情况下为O(nlogn)。总体来看，时间复杂度较好，而且在各种情况下，时间复杂度变化不大，适用范围较广，但是它属于不稳定的排序。
冒泡排序时间复杂度为 O(n2)，空间复杂度低，时间复杂度高，是稳定的排序。
快速排序时间复杂度在最好情况下为O(nlogn)，最坏情况下为O(n2)，平均情况下为O(nlogn)。总体来看，时间复杂度较好，并且优于同为对数阶的堆排序算法，但当数据的排列不好时，可能退化为O(n2)，而且它也属于不稳定的排序。
递归归并排序时间复杂度在最好情况下为O(nlogn)，最坏情况下为O(nlogn)，平均情况下为O(nlogn)。总体来看，时间复杂度较好，而且在各种情况下，时间复杂度变化不大，而且相对于堆排序来说，这个排序算法的空间复杂度较小，而且它属于稳定的排序。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/278069
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号