十大排序（总结+算法实现）-创新互联

十大排序（总结+算法实现）十大排队的性能分析

在这里插入图片描述

为虎林等地区用户提供了全套网页设计制作服务，及虎林网站建设行业解决方案。主营业务为成都网站设计、成都做网站、虎林网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！冒泡排序

使用冒泡排序，时间复杂度为O(n^2),空间复杂度为O(1)

像气泡一样从低往上浮现

vectorbubbleSort(vectornums)
{int length=nums.size();
    for(int i=0;ifor(int j=length-2;j>=i;j--)
        {if(nums[j]>nums[j+1])
            {int temp=nums[j+1];
                nums[j+1]=nums[j];
                nums[j]=temp;
            }
        }
    }
    return nums;
}

选择排序

使用选择排序，时间复杂度为O(n^2),空间复杂度为O(1)。寻找关键字最小的坐标

vectorselectSort(vectornums)
{int length=nums.size();
    int minPos=INT_MIN;
    for(int i=0;iminPos=i;
        for(int j=i+1;jminPos=nums[j]

插入排序使用插入排序，时间复杂度为O(n^2),空间复杂度O(1)
vectorinsertSort(vectornums)
{int length=nums.size();
    for(int i=0;i//当找到满足非递增的数组时，进行处理
        int temp=nums[i+1];
        int preIndex=i;
        while(preIndex>=0&&nums[preIndex]>temp)
        {//数组往后挪，直到找到第一个小于该值的值
            nums[preIndex+1]=nums[preIndex];
            preIndex--;
        }
        nums[preIndex+1]=temp;
        
    }
    return nums;
}
希尔排序使用希尔排序进行实现，平均时间复杂度为O(nlogn)，空间复杂度为O(1)
希尔排序是在插入排序的基础上进行改进的算法
先将序列划分成大区间，先对每一个区间进行排序，使后一个区间里的所有对应位置的值都大于前一个区间所有对应位置的值
然后不断循环，直到最后大区间全部都变成了小区间，则此时代表已经排号序了
vectorshellSort(vectornums)
{int length=nums.size();
    int gap=length>>1;
    int temp;
    while(gap)
    {//类似插入排序
        //i从第二个区间开始的
        for(int i=gap;itemp=nums[i];
            int preIndex=i-gap;
             
            while(preIndex>=0&&nums[preIndex]>temp)
            {nums[preIndex+gap]=nums[preIndex];
                preIndex-=gap;
            }
            nums[preIndex+gap]=temp;
        }
        gap=gap>>1;
    }
    return nums;
}
归并排序归并排序，平均时间复杂度O(nlogn)，空间复杂度O(n)
//归并排序，平均时间复杂度O(nlogn)，空间复杂度O(n)
//使用递归实现归并排序
vectormergeSort(vectornums)
{mSort(nums,0,nums.size()-1);
    return nums;
}

//在[left,right]这个区间中进行归并排序，整个nums经过整个函数后就是一个有序数组
//使用回溯的思想
void mSort(vector&nums,int left,int right)
{//定义递归终止条件
    if(left>=right)
    {return;
    }
    //防止位溢出
    int mid=left+((right-left)>>1);
    //回溯
    mSort(nums,left,mid);
    mSort(nums,mid+1,right);
    merge(nums,left,mid,right);
}


void merge(vector&nums,int left,int mid,int right)
{//创建一个临时数组用以保存合并排序之后的数组,并把这个区间的值赋给其
    vectortempArr(nums.begin()+left,nums.begin()+right+1);
    
    //合并两个区间，i代表左边开始索引，j代表右边开始索引
    int i=left;
    int j=mid+1;

    for(int k=left;k<=right;k++)
    {//代表左边已经处理完毕，将右边的直接替代即可
        if(i>mid)
        {nums[k]=tempArr[j-left];
            j++;
        }
        //代表右边已经处理完毕，将左侧区间的值直接拷贝到原数组即可
        else if(j>right)
        {nums[k]=tempArr[i-left];
            i++;
        }
        //两边都未处理完毕，则比较二者大小，将元素中较小的元素放在左边
        else if(tempArr[i-left]<=tempArr[j-left]){nums[k]=tempArr[i-left];
            i++;
        }
        else
        {nums[k]=tempArr[j-left];
            j++;
        }
    }
}
快速排序平均时间复杂度为O(nlogn)，最坏平均复杂度为O(n^2),空间复杂度O(logn)
vectorquickSort(vectornums)
{qSort(nums,0,nums.size()-1);
    return nums;
}


void qSort(vector&nums,int left,int right)
{//定义递归终止条件
    if(left>=right)
    {return;
    }

    //设置枢轴
    int pivot=partition(nums,left,right);
    //递归实现
    qSort(nums,left,pivot-1);
    qSort(nums,pivot+1,right);
}

int partition(vector&nums,int left,int right)
{int pivot=nums[left];
    int j=left;

    for(int i=left+1;i<=right;i++)
    {//大放过小交换
        if(nums[i]j++;
            swap(nums,i,j);
        }
    }
    swap(nums,left,j);
    return j;
}

void swap(vector&nums,int index1,int index2)
{int temp=nums[index1];
    nums[index1]=nums[index2];
    nums[index2]=temp;
}
堆排序堆排序，算法平均时间复杂度为O(nlogn),空间复杂度O(1)
vectorheapSort(vectornums)
{//首先构建一个大堆
    for(int i=nums.size()/2-1;i>=0;--i)
    {heapAdjust(nums,i,nums.size());
    }

//从大堆中逆序得到递增序列
    for(int i=nums.size()-1;i>=0;--i)
    {swap(nums,0,i);
        heapAdjust(nums,0,i);
    }
    return nums;

}

void heapAdjust(vector&nums,int i,int length)
{int max=i;
    //构建左右结点
    int lChild=i*2+1;
    int rChild=i*2+2;

    if(lChildnums[max])
    {max=lChild;
    }
    if(rChildnums[max])
    {max=rChild;
    }
    if(max!=i)
    {swap(nums,i,max);
        heapAdjust(nums,max,length);
    }
}
计数排序计数排序，时间复杂度O(n+k),空间复杂度O(k)
vectorcountSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //数值作为索引，个数作为值
   vectorcount(maxVal,0);

   vectortemp(nums);
//数字需要减去1才能实现
   for(int i=0;i++count[nums[i]-1];
   }

   nums.clear();

   for(int i=0;ifor(int j=0;jnums.push_back(i+1);
        }
   }
   return nums;
}
vectorcountSort2(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //数值作为索引，个数作为值
   vectorcount(maxVal-minVal+1,0);
    int bias=0-minVal;
   for(int i=0;i++count[nums[i]+bias];
   }

    int index=0,i=0;
    while(indexif(count[i]!=0)
        {nums[index]=i-bias;
            count[i]--;
            index++;
        }
        else{i++;
        }
    }

   return nums;
}
桶排序平均时间复杂度为O(n+k),空间复杂度为O(n+k)
//桶排序  平均时间复杂度为O(n+k),空间复杂度为O(n+k)
//设置总共有5个桶
vectorbucketSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];

   //设置桶的大小
   int bucketSize=5;
   //设置桶的数目
   int bucketCount=(maxVal-minVal)/bucketSize+1;

   vector>buckets(bucketCount,vector());

    //利用映射函数将数据分配到每个桶中
    for(int i=0;ibuckets[(nums[i]-minVal)/bucketSize].push_back(nums[i]);
    }

    int index=0;
    for(int i=0;i//对每个桶的内部函数进行排序
        //调用之前写的排序算法
        buckets[i]=quickSort(buckets[i]);
    //取出每个桶中的元素
        for(int j=0;jnums[index++]=buckets[i][j];
        }
    }
    return nums;
}
基数排序平均时间复杂度为O(n*k),空间复杂度为O(n+k)
//基数排序，平均时间复杂度为O(n*k),空间复杂度为O(n+k)
//按位对应的数，从高位开始依次比较，进行排序

vectorradixSort(vectornums)
{int length=nums.size();
    int bits=maxBit(nums);

    //设置数组保存从0~9的数字
   
    int radix=1;
    for(int i=0;i<=bits;i++)
    {//获取更新的数组
        vectornewArray(length);
        //根据最后一位数字的值保存排序数组
        vectorcount=vector(10,0);

        for(int j=0;jint temp=(nums[j]/radix)%10;
            count[temp]++;
        }

        //计算前缀和，判断前面由于个位数不存在的值
        for(int j=1;j<10;j++)
        {count[j]+=count[j-1];
        }
//指定更新阵列的新位置，count[temp]--则是用来判断这个位置是否到位
        for(int j=length-1;j>=0;j--)
        {int temp=(nums[j]/radix)%10;
            newArray[count[temp]-1]=nums[j];
            count[temp]--;
        }

        nums=newArray;
        radix*=10;
    }
    return nums;


}

//获取数组中大值的位数
int maxBit(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
    int d=0;
    // int p=10;
    while(maxVal>0)
    {maxVal/=10;
        ++d;
    }
    return d;
}
全部测试代码#include#include#include
#includeusing namespace std;

void mSort(vector&nums,int left,int right);
void merge(vector&nums,int left,int mid,int right);
void qSort(vector&nums,int left,int right);
int partition(vector&nums,int left,int right);
void swap(vector&nums,int index1,int index2);
void heapAdjust(vector&nums,int i,int length);
int maxBit(vectornums);

//使用冒泡排序，时间复杂度为O(n^2),空间复杂度为O(1)
//像气泡一样从低往上浮现
vectorbubbleSort(vectornums)
{int length=nums.size();
    for(int i=0;ifor(int j=length-2;j>=i;j--)
        {if(nums[j]>nums[j+1])
            {int temp=nums[j+1];
                nums[j+1]=nums[j];
                nums[j]=temp;
            }
        }
    }
    return nums;
}


//使用选择排序，时间复杂度为O(n^2),空间复杂度为O(1)
//寻找到关键字最小的坐标
vectorselectSort(vectornums)
{int length=nums.size();
    int minPos=INT_MIN;
    for(int i=0;iminPos=i;
        for(int j=i+1;jminPos=nums[j]insertSort(vectornums)
{int length=nums.size();
    for(int i=0;i//当找到满足非递增的数组时，进行处理
        int temp=nums[i+1];
        int preIndex=i;
        while(preIndex>=0&&nums[preIndex]>temp)
        {//数组往后挪，直到找到第一个小于该值的值
            nums[preIndex+1]=nums[preIndex];
            preIndex--;
        }
        nums[preIndex+1]=temp;
        
    }
    return nums;
}

//使用希尔排序进行实现，平均时间复杂度为O(nlogn)，空间复杂度为O(1)
//希尔排序是在插入排序的基础上进行改进的算法
//先将序列划分成大区间，先对每一个区间进行排序，使后一个区间里的所有对应位置的值都大于前一个区间所有对应位置的值‘
//然后不断循环，直到最后大区间全部都变成了小区间，则此时代表已经排号序了
vectorshellSort(vectornums)
{int length=nums.size();
    int gap=length>>1;
    int temp;
    while(gap)
    {//类似插入排序
        //i从第二个区间开始的
        for(int i=gap;itemp=nums[i];
            int preIndex=i-gap;
             
            while(preIndex>=0&&nums[preIndex]>temp)
            {nums[preIndex+gap]=nums[preIndex];
                preIndex-=gap;
            }
            nums[preIndex+gap]=temp;
        }
        gap=gap>>1;
    }
    return nums;
}

//归并排序，平均时间复杂度O(nlogn)，空间复杂度O(n)
//使用递归实现归并排序
vectormergeSort(vectornums)
{mSort(nums,0,nums.size()-1);
    return nums;
}

//在[left,right]这个区间中进行归并排序，整个nums经过整个函数后就是一个有序数组
//使用回溯的思想
void mSort(vector&nums,int left,int right)
{//定义递归终止条件
    if(left>=right)
    {return;
    }
    //防止位溢出
    int mid=left+((right-left)>>1);
    //回溯
    mSort(nums,left,mid);
    mSort(nums,mid+1,right);
    merge(nums,left,mid,right);
}


void merge(vector&nums,int left,int mid,int right)
{//创建一个临时数组用以保存合并排序之后的数组,并把这个区间的值赋给其
    vectortempArr(nums.begin()+left,nums.begin()+right+1);
    
    //合并两个区间，i代表左边开始索引，j代表右边开始索引
    int i=left;
    int j=mid+1;

    for(int k=left;k<=right;k++)
    {//代表左边已经处理完毕，将右边的直接替代即可
        if(i>mid)
        {nums[k]=tempArr[j-left];
            j++;
        }
        //代表右边已经处理完毕，将左侧区间的值直接拷贝到原数组即可
        else if(j>right)
        {nums[k]=tempArr[i-left];
            i++;
        }
        //两边都未处理完毕，则比较二者大小，将元素中较小的元素放在左边
        else if(tempArr[i-left]<=tempArr[j-left]){nums[k]=tempArr[i-left];
            i++;
        }
        else
        {nums[k]=tempArr[j-left];
            j++;
        }
    }
}



//快速排序：平均时间复杂度为O(nlogn)，最坏平均复杂度为O(n^2),空间复杂度O(logn)
vectorquickSort(vectornums)
{qSort(nums,0,nums.size()-1);
    return nums;
}


void qSort(vector&nums,int left,int right)
{//定义递归终止条件
    if(left>=right)
    {return;
    }

    //设置枢轴
    int pivot=partition(nums,left,right);
    //递归实现
    qSort(nums,left,pivot-1);
    qSort(nums,pivot+1,right);
}

int partition(vector&nums,int left,int right)
{int pivot=nums[left];
    int j=left;

    for(int i=left+1;i<=right;i++)
    {//大放过小交换
        if(nums[i]j++;
            swap(nums,i,j);
        }
    }
    swap(nums,left,j);
    return j;
}

void swap(vector&nums,int index1,int index2)
{int temp=nums[index1];
    nums[index1]=nums[index2];
    nums[index2]=temp;
}


//堆排序，算法平均时间复杂度为O(nlogn),空间复杂度O(1)
vectorheapSort(vectornums)
{//首先构建一个大堆
    for(int i=nums.size()/2-1;i>=0;--i)
    {heapAdjust(nums,i,nums.size());
    }

//从大堆中逆序得到递增序列
    for(int i=nums.size()-1;i>=0;--i)
    {swap(nums,0,i);
        heapAdjust(nums,0,i);
    }
    return nums;

}

void heapAdjust(vector&nums,int i,int length)
{int max=i;
    //构建左右结点
    int lChild=i*2+1;
    int rChild=i*2+2;

    if(lChildnums[max])
    {max=lChild;
    }
    if(rChildnums[max])
    {max=rChild;
    }
    if(max!=i)
    {swap(nums,i,max);
        heapAdjust(nums,max,length);
    }
}


//计数排序，时间复杂度O(n+k),空间复杂度O(k)
vectorcountSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //数值作为索引，个数作为值
   vectorcount(maxVal,0);

   vectortemp(nums);
//数字需要减去1才能实现
   for(int i=0;i++count[nums[i]-1];
   }

   nums.clear();

   for(int i=0;ifor(int j=0;jnums.push_back(i+1);
        }
   }
   return nums;
}


//计数排序，时间复杂度O(n+k),空间复杂度O(k)
//优化空间
vectorcountSort2(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];
   //数值作为索引，个数作为值
   vectorcount(maxVal-minVal+1,0);
    int bias=0-minVal;
   for(int i=0;i++count[nums[i]+bias];
   }

    int index=0,i=0;
    while(indexif(count[i]!=0)
        {nums[index]=i-bias;
            count[i]--;
            index++;
        }
        else{i++;
        }
    }

   return nums;
}


//桶排序  平均时间复杂度为O(n+k),空间复杂度为O(n+k)
//设置总共有5个桶
vectorbucketSort(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
   int minVal=nums[min_element(nums.begin(),nums.end())-nums.begin()];

   //设置桶的大小
   int bucketSize=5;
   //设置桶的数目
   int bucketCount=(maxVal-minVal)/bucketSize+1;

   vector>buckets(bucketCount,vector());

    //利用映射函数将数据分配到每个桶中
    for(int i=0;ibuckets[(nums[i]-minVal)/bucketSize].push_back(nums[i]);
    }

    int index=0;
    for(int i=0;i//对每个桶的内部函数进行排序
        //调用之前写的排序算法
        buckets[i]=quickSort(buckets[i]);
    //取出每个桶中的元素
        for(int j=0;jnums[index++]=buckets[i][j];
        }
    }
    return nums;
}


//基数排序，平均时间复杂度为O(n*k),空间复杂度为O(n+k)
//按位对应的数，从高位开始依次比较，进行排序

vectorradixSort(vectornums)
{int length=nums.size();
    int bits=maxBit(nums);

    //设置数组保存从0~9的数字
   
    int radix=1;
    for(int i=0;i<=bits;i++)
    {//获取更新的数组
        vectornewArray(length);
        //根据最后一位数字的值保存排序数组
        vectorcount=vector(10,0);

        for(int j=0;jint temp=(nums[j]/radix)%10;
            count[temp]++;
        }

        //计算前缀和，判断前面由于个位数不存在的值
        for(int j=1;j<10;j++)
        {count[j]+=count[j-1];
        }
//指定更新阵列的新位置，count[temp]--则是用来判断这个位置是否到位
        for(int j=length-1;j>=0;j--)
        {int temp=(nums[j]/radix)%10;
            newArray[count[temp]-1]=nums[j];
            count[temp]--;
        }

        nums=newArray;
        radix*=10;
    }
    return nums;


}

//获取数组中大值的位数
int maxBit(vectornums)
{int maxVal=nums[max_element(nums.begin(),nums.end())-nums.begin()];
    int d=0;
    // int p=10;
    while(maxVal>0)
    {maxVal/=10;
        ++d;
    }
    return d;
}




int main()
{vectornums={9,9,2,18,3,7,34,356,5};

    vectorres=bubbleSort(nums);
    cout<<"冒泡排序的结果为:";
    for(int i:res)
    {cout<cout<cout<cout<cout<cout<cout<cout<cout<cout<

                
     你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
                    

                    网页题目：十大排序（总结+算法实现）-创新互联                    

                    网站地址：http://kswjz.com/article/cojege.html


                
                    
                    
                        扫二维码与项目经理沟通
                        我们在微信上24小时期待你的声音
                        解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
                    
                
                
                    其他资讯
                    
                        如何在vue中使用G2图表
Vim使用技巧怎么提升
layui导出所有数据的例子
服务器可以解析多少域名
dir在linux中指的是什么


        
            
                
                    行业动态
                    企业网站建设的重要性！
                    现在虽然是移动互联网时代，但企业网站依然重要，包含PC站点，移动站。可以说企业网站关系企业的未来发展和前途，尤其对中小企业更是如此，一些中小企业老板，对自己的名片很在乎，因为这是个门面。...
                
            
            
                服务项目
                
                    
                        
                            网站建设
                            
                            查看详情
                        
                    
                    
                        
                            移动端/APP
                            
                            查看详情
                        
                    
                    
                        
                            微信/小程序
                            
                            查看详情
                        
                    
                    
                        
                            技术支持
                            
                            查看详情
                        
                    
                    
                        
                            其它服务
                            
                            查看详情
                        
                    
                    
                        
                            更多服务项目
                             用我们的专业和诚信赢得您的信赖，从PC到移动互联网均有您想要的服务！
                            获取更多
                        
                    
                
            
            
                 联系吧 在百度地图上找到我们 
                电话：13518219792
                如遇占线或暂未接听请拨：136xxx98888
                 业务咨询 技术咨询 售后服务


    
        
            
                
                    网站设计
                    响应式网站设计
四川成都网站设计
成都网站设计
成都网站设计
                
                
                    网站制作
                    网站制作价格
手机网站制作
网站制作
梓潼网站制作公司
                
                
                    联系我们
                    电话：13518219792
                    邮箱：631063699@qq.com
                    地址：成都青羊区锦天国际1002号
                    网址：www.kswjz.com
                
                
                    网站建设
                    营销型网站建设
成都响应式网站建设
成都网站建设
成都网站建设公司
                
                
                    
                    
                         
                            微信二维码
                        
                    
                
            
        
        
            
                友情链接
                成都app软件开发
网络营销推广
网站制作公司
腾讯云免备案空间
云南护栏打桩机
攀枝花网站建设
店面门头广告
成都微信二次开发公司
谷歌推广
新津网站运维
            
        
    
    
        
             Copyright © 2002-2023 www.kswjz.com 快上网建站品牌 QQ：244261566 版权所有 备案号：蜀ICP备19037934号
            
             
        
    
    
        
            在线咨询
            
            13518219792
             
                 
                    微信二维码
                
            
             
                 
                    移动版官网

十大排序（总结+算法实现）-创新互联

扫二维码与项目经理沟通

其他资讯

行业动态

企业网站建设的重要性！

服务项目

网站建设

移动端/APP

微信/小程序

技术支持

其它服务

更多服务项目

联系吧 在百度地图上找到我们

电话：13518219792

联系吧在百度地图上找到我们