堆排序的C++实现

堆排序的要点在于【向上调整堆】以及【向下调整堆】。

将这两个要点搞清楚堆排序就很简单了。

—————————————————————–

#include <iostream>
#include <vector>
using namespace std;

//辅助函数
void Swap(vector<int> &v,int i,int j){
v[i]^= v[j];
v[j]^= v[i];
v[i]^= v[j];
}
void Print(vector<int> v){
for(auto vi = v.begin();vi!=v.end();++vi) cout<<*vi<<” “;
cout<<endl;
}

/*堆操作函数*/
//向下调整堆
void AdjustDown(vector<int> &v,int i,int n){
for(int j=i*2;j<=n;j=j*2){
if(j<n&&v[j]<v[j+1]) ++j;
if(v[i]>v[j]) break;
else{
Swap(v,i,j);
i=j;
}
}
}
//向上调整堆
void AdjustUp(vector<int> &v,int i,int n){
for(int j=i/2;v[i]>v[j];j/=2){
Swap(v,j,i);
i=j;
}
}
//建堆
void BuildMaxHeap(vector<int> &v,int n){
for(int i=n/2;i>0;–i){
AdjustDown(v,i,n);
}
}
void MaxHeapInsert(vector<int> &v,int ins){
v.push_back(ins);
}
//大顶堆排序
void HeapSort(vector<int> &v,int n){
BuildMaxHeap(v,n);
for(int i=n;i>1;–i){
Swap(v,i,1);
AdjustDown(v,1,i-1);
}
}
int main()
{
vector<int> v = {0,53,17,78,9,45,65,87,32,1,43,22,67,83};
HeapSort(v,v.size()-1);
Print(v);
BuildMaxHeap(v,v.size()-1);
MaxHeapInsert(v,44);
HeapSort(v,v.size()-1);
Print(v);
return 0;
}

快速排序之中间基准值的实现[C++实现]

在很多时候写快排选择基准值时都是使用第一个元素作为基准,今天使用了中间元素作为基准值来实现快排。

Tips:比较重要的一点是要更新基准值的位置

—————————————————————

#include <iostream>
#include <vector>
using namespace std;
int Partition(vector<int> &v,int low,int high){

int pivot = low+(high-low)/2;
while(low<high){
while(low<high&&v[high]>v[pivot]) –high;
while(low<high&&v[low]<v[pivot]) ++low;
if(low<high){
//交换元素
v[low]^=v[high];
v[high]^=v[low];
v[low]^=v[high];
//基准追踪
if(low==pivot) pivot = high;
else if(high==pivot) pivot=low;
//循环退出
if(v[low]==v[pivot]&&v[high]==v[pivot]) ++low;
}
}
return pivot;

}
void quickSort(vector<int> &v,int low,int high){
if(low<high){
int pos = Partition(v,low,high);
quickSort(v,low,pos-1);
quickSort(v,pos+1,high);
}
}

int main(){
vector<int> v={1,3,2,4,5,7,2,1};
quickSort(v,0,v.size()-1);
for(auto vi = v.begin();vi!=v.end();++vi) cout<<*vi<<” “;
cout<<endl;
return 0;
}