当前位置：首页 > news >正文

数据结构排序算法复习

news 2026/3/26 23:11:30

排序

冒泡排序

voidbupplesort(std::vector<int>&arr){intn=arr.size();for(inti=0;i<n;i++){boolf=false;for(intj=i;j<n-1-i;j++){if(arr[j]>arr[j+1]){if(arr[j]>arr[j+1])std::swap(arr[j],arr[j+1]);f=true;}}if(f==false){break;}}}

插入排序

voidinsertsort(std::vector<int>&arr){intn=arr.size();intend=0;for(;end<n-1;end++){intkey=arr[end+1];inttem=end;while(tem>=0){if(arr[tem]>key){arr[tem+1]=arr[tem];tem--;}else{break;}}arr[tem+1]=key;}}

希尔排序

voidshellsort(std::vector<int>&arr){intgap=arr.size();//分几组intn=arr.size();while(gap>1){gap=gap/3+1;//gap为1就是直接插入排序for(inti=0;i+gap<=n-1;i++){intend=i;intkey=arr[end+gap];while(end>=0){if(arr[end]>key){arr[end+gap]=arr[end];end-=gap;}else{break;}}arr[end+gap]=key;}}}

堆排序

voidheapsort(std::vector<int>&arr){std::priority_queue<int,std::vector<int>,std::greater<int>>q;inti=0;for(auto&ch:arr)q.push(ch);while(!q.empty()){arr[i++]=q.top();q.pop();}}

选择排序

void selectSort(std::vector<int>& arr) { int begin = 0; int end = arr.size() - 1; while (begin < end) { int minindex = begin; int maxindex = begin; for (int i = begin; i <=end; i++) { if (arr[i] > arr[maxindex])maxindex = i; if (arr[i] < arr[minindex])minindex = i; } std::swap(arr[minindex], arr[begin]); //如果最大值就是begin位置的情况 执行最小值和begin交换的时候会把最大值挪到minindex下标对应的位置 if (maxindex == begin)maxindex = minindex; std::swap(arr[end], arr[maxindex]); begin++; end--; } }

快速排序

void_quicksort1(std::vector<int>&arr,intleft,intright){// 递归终止条件：区间只有0或1个元素if(left>=right)return;// 1. 随机选择基准值位置（这一步本身没问题）intkeyi=left;intbegin=left;intend=right;while(begin<end){// 先从右找小于key的元素（先右后左，基准在随机位置不影响这个顺序）while(begin<end&&arr[end]>=arr[keyi])end--;// 再从左找大于key的元素while(begin<end&&arr[begin]<=arr[keyi])begin++;// 交换不符合条件的元素std::swap(arr[begin],arr[end]);}std::swap(arr[begin],arr[keyi]);_quicksort1(arr,left,begin-1);_quicksort1(arr,begin+1,right);}voidquicksort(std::vector<int>&arr){if(arr.empty())return;// 增加空数组保护，避免越界_quicksort2(arr,0,arr.size()-1);}

快速排序三路划分实现

//快速排序的三路归并实现 本质就是保证 [left,l]都小于key [l+1,r-1]都是key,[r,right]void_quicksort2(std::vector<int>&arr,intleft,intright){if(left>=right)return;intkey=arr[rand()%(right-left+1)+left];intl=left-1;intr=right+1;inti=left;while(i<r){if(arr[i]<key)std::swap(arr[++l],arr[i++]);elseif(arr[i]==key)i++;elsestd::swap(arr[i],arr[--r]);}_quicksort2(arr,left,l-1);_quicksort2(arr,r+1,right);}

快速排序的非递归算法

intpartion(std::vector<int>&arr,intleft,intright){intbegin=left;intend=right;while(begin<end){while(begin<end&&arr[end]>=arr[left])end--;while(begin<end&&arr[begin]<=arr[left])begin++;std::swap(arr[begin],arr[end]);}std::swap(arr[begin],arr[left]);returnbegin;}voidQuicksortStack(std::vector<int>&arr){std::queue<std::pair<int,int>>q;q.push(std::make_pair(0,arr.size()-1));while(!q.empty()){auto[l,r]=q.front();q.pop();intret=partion(arr,l,r);if(l<ret-1)q.push(std::make_pair(l,ret-1));if(ret+1<r)q.push(std::make_pair(ret+1,r));}}

归并排序

void_mergesort(std::vector<int>&arr,std::vector<int>&help,intleft,intright){if(left>=right)return;intmid=(right-left)/2+left;_mergesort(arr,help,left,mid);_mergesort(arr,help,mid+1,right);intbegin1=left;intbegin2=mid+1;inti=left;while(begin1<=mid&&begin2<=right){if(arr[begin1]<=arr[begin2]){help[i++]=arr[begin1++];}else{help[i++]=arr[begin2++];}}while(begin1<=mid){help[i++]=arr[begin1++];}while(begin2<=right){help[i++]=arr[begin2++];}for(intk=left;k<=right;k++)arr[k]=help[k];}voidmergesort(std::vector<int>&arr){intn=arr.size();std::vector<int>help(n);_mergesort(arr,help,0,n-1);}

归并排序的非递归实现

voidmergesortStack(std::vector<int>&arr){intn=arr.size();std::vector<int>help(n);//【begin1，end1】【begin2，end2】intgap=1;//记录每一组进行归并的begin1到end1之间的元素个数while(gap<n){for(inti=0;i<n;i+=2*gap){intbegin1=i;intend1=begin1+gap-1;intbegin2=end1+1;intend2=begin2+gap-1;intindex=i;//判断区间合法性· 第一段区间不要进行判断 我们进行合并需要两端区间 我们只要知道第二个// 区间是否存在 如果存在的话 end1一定是有效的 如果不存在就没有必要再次进行归并了 更换// 步长执行其他的就好if(end1>=n){break;}if(begin2>=n)break;end2=std::min(end2,n-1);while(begin1<=end1&&begin2<=end2){if(arr[begin1]<=arr[begin2]){help[index++]=arr[begin1++];}else{help[index++]=arr[begin2++];}}while(begin1<=end1){help[index++]=arr[begin1++];}while(begin2<=end2){help[index++]=arr[begin2++];}for(intk=i;k<=end2;k++)arr[k]=help[k];}gap*=2;}}