八大排序算法C/C++代码实现

本文主要是介绍八大排序算法C/C++代码实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

八大排序算法代码实现

tip:

本文所有排序算法均为升序排序

基本数据结构

typedef int dataType;
//这里主要针对整型数据进行排序
typedef struct
{
    vector<dataType> key;  //顺序表关键字
    int length;  //顺序表长度
}List;

tip:

这里vector<dataType>表示以储存dataType类型的vector定义的对象key
在本文中的用途与数组基本无差别，可用dataType key[SIZE];代替

一、插入排序

原始版本

//排序部分为0-L.length-1
void InsertSort_0(List &L)//对顺序表L进行插入排序
{
    int i,j;
    dataType temp;
    for(i=1;i<L.length;i++)
    {
        //将i号数据插入0到i-1的有序序列中
        temp = L.key[i];
        for(j=i-1;j>=0;j--)//向前寻找应该插入该数据的位置
        {
            if(L.key[j]>temp)
                L.key[j+1] = L.key[j];
            else
                break;
        }
        L.key[j+1] = temp;
    }
}

改进版本1

将顺序表的0号位置清空，作为哨兵位，在1到length的位置放置数据，可以省去循环出口判断的时间,也无需额外的变量来临时储存插入的数据

//排序部分为1-L.length
void InsertSort_1(List &L)
{
    int i,j;
    for(i=2;i<=L.length;i++)//注意这里开始和结束的位置和之前有所不同
    {
        L.key[0] = L.key[i];//将要插入的数据放到哨兵位上
        for(j=i-1;;j--)
        {
            if(L.key[j]>L.key[0])
                L.key[j+1]=L.key[j];
            else
                break;
        }
        L.key[j+1] = L.key[0];
    }
}

改进版本2

在寻找插入数据应该插入的位置时本质上是在做一个顺序查找，我们可以用二分查找取而代之，能够更大程度地减小复杂度

//排序部分为1-L.length
void InsertSort_2(List &L)
{
    int i,j,k;
    int low,high,mid;
    for(i=2;i<=L.length;i++)
    {
        L.key[0] = L.key[i];
        low = 1;    //查找区间下界
        high = i-1; //查找区间上界
        while(low<=high)
        {
            mid = (low+high)/2;
            if(L.key[mid]>L.key[0])
                high = mid-1;   //在前一段区间查找
            else
                low = mid+1;    //在后一段区间查找
        }
        //最后插入点一定是在L.key[mid]左或右，比较大小确定插入位置
        if(L.key[0]>=L.key[mid])
            k = mid+1;
        else
            k = mid;
        //将有序部分插入位置后面的所有点后移一位
        for(j=i-1;j>=k;j--)
            L.key[j+1] = L.key[j];
        L.key[k] = L.key[0];
    }
}

二、希尔排序

//排序部分为1-L.length
void ShellInsert(List &L,int d)//增量为d的插入排序(以插入排序的改进版本1为基础)
{
    int i,j;
    for(i=d+1;i<=L.length;i++)
    {
        L.key[0] = L.key[i];
        for(j=i-d;j>=0;j-=d)
        {
            if(L.key[j]>L.key[0])
                L.key[j+d] = L.key[j];
            else
                break;
        }
        L.key[j+d] = L.key[0];
    }
}
void ShellSort(List &L)
{
    int i;
    for(i=L.length/2;i>=1;i/=2)
        ShellInsert(L,i);
}

三、冒泡排序

原始版本

//排序部分为0-L.length-1
void BubbleSort(List &L)
{
    int i,j;
    dataType temp;
    for(i=1;i<=L.length-1;i++)//执行n-1次冒泡
    {
        for(j=0;j<L.length-i;j++)
            if(L.key[j]>L.key[j+1])
            {
                temp = L.key[j];
                L.key[j] = L.key[j+1];
                L.key[j+1] = temp;
            }
    }
}

改进版本

当序列相对有序时无需进行过多的比较操作，每次冒泡记录下最后一次交换的位置，从0位置到标记位置即是无序部分，下一次冒泡只需比较到这里即可，当标记位置为0时，冒泡结束

//排序部分为0-L.length-1
void BubbleSort_1(List &L)
{
    int i,sig,lastchange;
    dataType temp;
    sig = L.length-1;
    while(sig>0)
    {
        lastchange = 0;
        for(i=0;i<sig;i++)
        {
            if(L.key[i]>L.key[i+1])
            {
                temp = L.key[i];
                L.key[i] = L.key[i+1];
                L.key[i+1] = temp;
                lastchange = i;
            }
        }
        sig = lastchange;
    }
}

四、快速排序

//排序部分为0-L.length-1
int pivot(List &L,int low,int high)//一趟快速排序，返回枢轴的位置
{
    dataType temp = L.key[low];
    while(low<high)
    {
        while(low<high && L.key[high]>=temp)//从右边找到比枢轴小的数据
            high--;
        L.key[low] = L.key[high];
        while(low<high && L.key[low]<=temp)//从左边找到比枢轴大的数据
            low++;
        L.key[high] = L.key[low];
    }
    L.key[low] = temp;
    return low;
}
void QSort(List &L,int low,int high)
{
    if(low<high)
    {
        int pivotLoc = pivot(L,low,high);
        QSort(L,low,pivotLoc-1);    //对前一部分进行快速排序
        QSort(L,pivotLoc+1,high);   //对后一部分进行快速排序
    }
}
void QuickSort(List &L)
{
    QSort(L,0,L.length);
}

五、选择排序

经典算法

//排序部分为0-L.length-1
void SelectSort(List &L)
{
    int i,j,k;
    dataType temp;
    for(i=0;i<L.length-1;i++)
    {
        temp = L.key[i];
        k = i;
        for(j=i+1;j<L.length;j++)
        {
            if(temp>L.key[j])
            {
                temp = L.key[j];
                k = j;
            }
        }
        L.key[k] = L.key[i];
        L.key[i] = temp;
    }
}

六、堆排序

建堆的过程中需要从L.length/2开始到0依次进行调整即可

//堆的结构采用顺序表形式储存
//为了做到升序排序，我们要构建一个大顶堆
//排序部分为1-L.length
void HeapAdjust(List &L,int low,int high)
{
    int i=low,j=2*i;
    L.key[0] = L.key[low];
    while(j<=high)
    {
        if(j+1<=high && L.key[j+1]>L.key[j])    //选取大的子树
            j++;
        if(L.key[j] > L.key[0]) //如果子树数据比其本身大，进行调整
        {
            L.key[i] = L.key[j];
            i = j;
            j = 2*i;
        }
        else    
            break;
    }
    L.key[i] = L.key[0];
}
void HeapSort(List &L)
{
    int i;
    for(i=L.length/2;i>0;i--)   //建成大顶堆
        HeapAdjust(L,i,L.length);
    for(i=L.length;i>1;i--) //逐个移动，移动后调整
    {
        L.key[0] = L.key[1];
        L.key[1] = L.key[i];
        L.key[i] = L.key[0];
        HeapAdjust(L,1,i-1);
    }
}

七、归并排序

二路归并排序(递归)

先不断地对数组进行递归平分，一直分到不能再分，然后回溯的过程中两两进行数组归并操作

//排序部分为1-L.length
void Merge(List &S,List &L,int low,int mid,int high)    
{
    //将有序的S(low到mid)和有序的S(mid+1到high)归并成有序的T(low到high)
    //这个函数的操作相当于两个数组的异地归并
    int i = low,j = mid+1,k = low;
    while(i<=mid && j<=high)
    {
        if(S.key[i]<=S.key[j])
        {
            L.key[k] = S.key[i];
            i++;
            k++;
        }
        else
        {
            L.key[k] = S.key[j];
            j++;
            k++;
        }
    }
    while(i<=mid)
    {
        L.key[k] = S.key[i];
        i++;
        k++;
    }
    while(j<=high)
    {
        L.key[k] = S.key[j];
        j++;
        k++;
    }
}
//将S的low到high部分归并为有序的到T中对应位置
void MSort(List &S,List &L,int low,int high)
{
    int i;
    int mid;
    if(low<high)
    {
        mid = (low+high)/2; //对S平分
        MSort(L,S,low,mid); //对前半段进行归并排序
        MSort(L,S,mid+1,high);//对后半段进行归并排序
        Merge(S,L,low,mid,high);//讲两部分归并
    }
}
void MergeSort(List &L)
{
    int i;
    List S = L;
    for(i=1;i<=L.length;i++)
        S.key[i] = L.key[i];
    MSort(S,L,1,L.length);
}

二路归并排序(非递归)

//排序部分为1-L.length
void Merge(List &S,List &L,int low,int mid,int high);   //归并部分仍用之前的代码
void MergeSort_1(List &L)
{
    int len,i,j;
    List S = L;
    for(len=1;len<=L.length;len*=2)
    {
        for(i=1;i<=L.length-2*len+1;i+=2*len)
            Merge(S,L,i,i+len-1,i+2*len-1);
        if(i+len<=L.length)
            Merge(S,L,i,i+len-1,L.length);
        S = L;
    }
}

八、基数排序

tip:在此算法中用到了vector的几个函数成员，在此进行说明

push_back();    //相当于出栈
size();         //返回vector的长度，相当于数组长度
clear();        //将vector中所有数据清空

对多位数的按数位进行的基数排序

typedef struct  //队列结构
{
    vector<dataType> data;
    int start = 0;
}Queue;
//排序部分为0-L.length-1
void RadixSort(List &L)
{
    //对0-9999的数据进行基数排序
    const int maxIndex = 4;
    int i,k;
    int radix = 1;
    int n;
    Queue Q[10];
    for(k=1;k<=maxIndex;k++)//分别对个十百千位进行处理
    {
        for(i=0;i<L.length;i++) //分配数据
        {
            n = (L.key[i]/radix)%10;
            Q[n].data.push_back(L.key[i]);
        }
        for(i=0,n=0;n<10;n++)   //收集数据
        {
            while(Q[n].start!=Q[n].data.size())
            {
                L.key[i] = Q[n].data[Q[n].start];
                Q[n].start++;
                i++;
            }
            Q[n].data.clear();  //重置队列
            Q[n].start = 0;
        }
        radix*=10;  //处理更高一位
    }
}

对一般较小数字进行的二进制基数排序

//排序部分为0-L.length-1
void RadixSort_1(List &L)
{
    int i,k;
    int maxIndex;
    int radix = 1;
    int n;
    Queue Q[2];
    dataType max = L.key[0];
    for(i=0;i<L.length;i++) //计算二进制最高位数
        if(L.key[i]>max)
            max = L.key[i];
    maxIndex = sqrt(max)+1;
    for(k=1;k<=maxIndex;k++)    //分别对二进制的每一位进行处理
    {
        for(i=0;i<L.length;i++) //分配数据
        {
            n = (L.key[i]/radix)%2;
            Q[n].data.push_back(L.key[i]);
        }
        for(i=0,n=0;n<2;n++)    //收集数据
        {
            while(Q[n].start!=Q[n].data.size())
            {
                L.key[i] = Q[n].data[Q[n].start];
                Q[n].start++;
                i++;
            }
            Q[n].data.clear();  //重置队列
            Q[n].start = 0;
        }
        radix*=2;   //处理更高一位
    }
}

本文持续更新中，如有错误或不足之处，欢迎批评指正。

这篇关于八大排序算法C/C++代码实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程

八大排序算法C/C++代码实现

八大排序算法代码实现

tip:

基本数据结构

tip:

一、插入排序

原始版本

改进版本1

改进版本2

二、希尔排序

三、冒泡排序

原始版本

改进版本

四、快速排序

五、选择排序

经典算法

六、堆排序

七、归并排序

二路归并排序(递归)

二路归并排序(非递归)

八、基数排序

tip:在此算法中用到了vector的几个函数成员，在此进行说明

对多位数的按数位进行的基数排序

对一般较小数字进行的二进制基数排序

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯