十大排序（总结+算法实现）

2022-12-03 23:14| 来源: 网络整理| 查看: 265

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

在这里插入图片描述

冒泡排序

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

像气泡一样从低往上浮现

vector bubbleSort(vectornums) {int length=nums.size();for(int i=0;iif(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=nums[j]//当找到满足非递增的数组时，进行处理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;inums[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;knums[k]=tempArr[j-left];j++;}//代表右边已经处理完毕，将左侧区间的值直接拷贝到原数组即可else if(j>right){nums[k]=tempArr[i-left];i++;}//两边都未处理完毕，则比较二者大小，将元素中较小的元素放在左边else if(tempArr[i-left]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;ij++;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;ifor(int j=0;jint 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;iif(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;vectorbuckets(bucketCount,vector());//利用映射函数将数据分配到每个桶中for(int i=0;i//对每个桶的内部函数进行排序//调用之前写的排序算法buckets[i]=quickSort(buckets[i]);//取出每个桶中的元素for(int j=0;jint length=nums.size();int bits=maxBit(nums);//设置数组保存从0~9的数字int radix=1;for(int i=0;iint temp=(nums[j]/radix)%10;count[temp]++;}//计算前缀和，判断前面由于个位数不存在的值for(int j=1;jint 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) //像气泡一样从低往上浮现 vector bubbleSort(vectornums) {int length=nums.size();for(int i=0;iif(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=nums[j]//当找到满足非递增的数组时，进行处理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;inums[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;knums[k]=tempArr[j-left];j++;}//代表右边已经处理完毕，将左侧区间的值直接拷贝到原数组即可else if(j>right){nums[k]=tempArr[i-left];i++;}//两边都未处理完毕，则比较二者大小，将元素中较小的元素放在左边else if(tempArr[i-left]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;ij++;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;ifor(int j=0;jint 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;iif(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;vectorbuckets(bucketCount,vector());//利用映射函数将数据分配到每个桶中for(int i=0;i//对每个桶的内部函数进行排序//调用之前写的排序算法buckets[i]=quickSort(buckets[i]);//取出每个桶中的元素for(int j=0;jint length=nums.size();int bits=maxBit(nums);//设置数组保存从0~9的数字int radix=1;for(int i=0;iint temp=(nums[j]/radix)%10;count[temp]++;}//计算前缀和，判断前面由于个位数不存在的值for(int j=1;jint 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);coutcoutcoutcoutcoutcout

【本文地址】

十大排序（总结+算法实现）

十大排序（总结+算法实现）

今日新闻

推荐新闻