13518219792
网站建设资讯

NEWS

网站建设资讯

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

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

在这里插入图片描述

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

使用冒泡排序，时间复杂度为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元起，快前往官网查看详情吧


文章题目：十大排序（总结+算法实现）-创新互联
网页URL：http://cdweb.net/article/cojege.html

其他资讯