《算法導論》排序算法

看《算法導論》寫的部分代碼，做個記錄。

[cpp]
#include <iostream>  
#include <cmath>  
#include <vector>  
#define maxNumber 100000000;  
/*------------------------------------------------------------------------
*《算法導論》第2-7章涉及到的部分算法：
*            插入排序+合並排序+堆排序+快速排序
*Version1.0: 2013/04/27
*Version2.0目標：1.增加其他排序算法：冒泡排序+計數排序等
*                2.增加更多類型支持，不限於std::vector<int>
*------------------------------------------------------------------------*/ 
 
//------------插入排序算法-----------------  
void InsertionSort(std::vector<int> &A){ 
    int len = A.size(); 
    int i; 
    for (int j=1;j<len;++j){ 
        int key = A[j]; 
        i = j-1; 
        while (i>=0 && A[i]>key){ 
            A[i+1] = A[i]; 
            --i; 
        } 
        A[i+1] = key; 
    } 
}; 
 
 
//------------合並排序---------------------  
void Merge(std::vector<int> &A, int p, int q, int r){ 
    int n1 = q-p+1; 
    int n2 = r-q; 
    std::vector<int> L(n1+1); 
    std::vector<int> R(n2+1); 
    int i,j; 
    for ( i=0; i<n1; ++i) L[i]=A[p+i]; 
    for ( j=0; j<n2; ++j) R[j]=A[q+j+1]; 
    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<int> &A, int p, int r){ 
    int q; 
    if (p<r){ 
        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<int> &A, int i,int heap_size){ 
    int l = LEFT(i); 
    int r = RIGHT(i); 
    int largest; 
    if (l<heap_size && A[l]>A[i])  
        largest = l; 
    else  
        largest = i; 
    if (r<heap_size && A[r]>A[largest])  
        largest = r; 
    if (largest != i){ 
        std::swap(A[i],A[largest]); 
        MaxHeapify(A, largest, heap_size); 
    } 
}; 
 
void BuildMaxHeap(std::vector<int> &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<int> &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<int> &A, int p, int r){ 
    int x = A[r]; 
    int i = p-1; 
    for (int j=p;j<r;++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<int> &A, int p, int r){ 
    if (p<r){ 
        int q = Partition(A,p,r); 
        QuickSort(A,p,q-1); 
        QuickSort(A,q+1,r); 
    } 
}; 

#include <iostream>
#include <cmath>
#include <vector>
#define maxNumber 100000000;
/*------------------------------------------------------------------------
*《算法導論》第2-7章涉及到的部分算法：
*            插入排序+合並排序+堆排序+快速排序
*Version1.0: 2013/04/27
*Version2.0目標：1.增加其他排序算法：冒泡排序+計數排序等
*                2.增加更多類型支持，不限於std::vector<int>
*------------------------------------------------------------------------*/

//------------插入排序算法-----------------
void InsertionSort(std::vector<int> &A){
 int len = A.size();
 int i;
 for (int j=1;j<len;++j){
  int key = A[j];
  i = j-1;
  while (i>=0 && A[i]>key){
   A[i+1] = A[i];
   --i;
  }
  A[i+1] = key;
 }
};

//------------合並排序---------------------
void Merge(std::vector<int> &A, int p, int q, int r){
 int n1 = q-p+1;
 int n2 = r-q;
 std::vector<int> L(n1+1);
 std::vector<int> R(n2+1);
 int i,j;
 for ( i=0; i<n1; ++i) L[i]=A[p+i];
 for ( j=0; j<n2; ++j) R[j]=A[q+j+1];
 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<int> &A, int p, int r){
 int q;
 if (p<r){
  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<int> &A, int i,int heap_size){
 int l = LEFT(i);
 int r = RIGHT(i);
 int largest;
 if (l<heap_size && A[l]>A[i])
  largest = l;
 else
  largest = i;
 if (r<heap_size && A[r]>A[largest])
  largest = r;
 if (largest != i){
  std::swap(A[i],A[largest]);
  MaxHeapify(A, largest, heap_size);
 }
};

void BuildMaxHeap(std::vector<int> &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<int> &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<int> &A, int p, int r){
 int x = A[r];
 int i = p-1;
 for (int j=p;j<r;++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<int> &A, int p, int r){
 if (p<r){
  int q = Partition(A,p,r);
  QuickSort(A,p,q-1);
  QuickSort(A,q+1,r);
 }
};