《算法导论》排序算法 - c++编程基础

Merge(std::vector &A, int p, int q, int r){
int n1 = q-p+1;
int n2 = r-q;
std::vector L(n1+1);
std::vector R(n2+1);
int i,j;
for ( i=0; i for ( j=0; j L[n1] = maxNumber;
R[n2] = maxNumber;
i = 0;
j = 0;
for (int k =p; k<=r;++k){
if (L[i]<=R[j]){
A[k]=L[i];
++i;
}
else{
A[k] = R[j];
++j;
}
}
};

void MergeSort(std::vector &A, int p, int r){
int q;
if (p q = (int)floor(double((p+r)/2));
MergeSort(A,p,q);
MergeSort(A,q+1,r);
Merge(A,p,q,r);
}
};

//------------堆排序--------------------------
int LEFT(int i){
return (2*(i)+1); //与书中不同，C++从0开始
};
int RIGHT(int i){
return (2*(i)+2);
};

void MaxHeapify(std::vector &A, int i,int heap_size){
int l = LEFT(i);
int r = RIGHT(i);
int largest;
if (lA[i])
largest = l;
else
largest = i;
if (rA[largest])
largest = r;
if (largest != i){
std::swap(A[i],A[largest]);
MaxHeapify(A, largest, heap_size);
}
};

void BuildMaxHeap(std::vector &A){
int heap_size = A.size();
for (int i = (int)floor(double(A.size()/2)); i>=0; --i)
MaxHeapify(A,i,heap_size);
}

void HeapSort(std::vector &A){
BuildMaxHeap(A);
int heap_size = A.size(); //
for (int i = A.size()-1;i>=1;--i){
std::swap(A[0],A[i]);
heap_size = heap_size-1;
MaxHeapify(A,0,heap_size);
}
}

//------------快速排序-----------------------------
int Partition(std::vector &A, int p, int r){
int x = A[r];
int i = p-1;
for (int j=p;j if (A[j]<=x){
++i;
std::swap(A[i],A[j]);
}
}
std::swap(A[i+1],A[r]);
return i+1;
};

void QuickSort(std::vector &A, int p, int r){
if (p int q = Partition(A,p,r);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
};

《算法导论》排序算法 (二)