资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

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

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

在这里插入图片描述

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

使用冒泡排序，时间复杂度为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://cdkjz.cn/article/cojege.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

业务热线：400-028-6601 / 大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
400电话办理服务器租凭成都品牌网站建设成都微商城成都免费做网站公司鸿艺文化传播网页设计制作雪茄烟重庆网站建设新型地坪材料

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询400-028-6601

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图