几种常用排序算法

/*几种常用的排序算法*/

/*算法名称: 冒泡排序
 *复杂度:O(n^2)
 *参数说明:
 *--start:起始地址
 ×--end:结束地址*/
template <class T>
void BubbleSort(T *start, T *end){
 for (T *i = end - 1; i > start; i--)
  for (T *j = start; j < i; j++)
   if (*j > *(j + 1)){
    T tmp = *j;
    *j = *(j + 1);
    *(j + 1)  = tmp;
   }
}

/*算法名称: 选择排序
 *复杂度:O(n^2) */
template <class T>
void SelectionSort(T *start, T *end){
 for (int *i = start; i < end - 1; i++)
  for (int *j = i + 1; j < end; j++)
   if (*i > *j){
    T tmp = *i;
    *i = *j;
    *j = tmp;
   }
}

 

/*算法名称: 归并排序
 *复杂度:O(n^log2n)
 *参数说明:
 *--buf:进行归并时的零时数组*/
template <class T>
void MergeSort(T *start, T *end, T buf[]){
 if (start < end - 1){
  int p = (end - start) / 2;
  MergeSort(start, start + p, buf);
  MergeSort(start + p, end, buf);

  T *l = start, *r = start + p;
  for (int i = 0; i < end - start; i++){
   if (l < start + p && r < end){
    if (*l < *r)
     buf[i] = *l++;
    else
     buf[i] = *r++;
   }else{
    if (l < start + p) buf[i] = *l++;
    else buf[i] = *r++;
   }
  }
  for (int i = 0; i < end - start; i++)
   start[i] = buf[i];
 }
}

/*算法名称: 快速排序
 *复杂度:O(n^2) (最坏情况)*/
template <class T>
void QuickSort(T *start, T *end){
 if (start < end - 1){
  T x = *start;
  T *pi = start, *pj = end;
  while (true){
   while (x > *++pi);
   while (x < *--pj);
   if (pi >= pj) break;
   T tmp = *pi;
   *pi = *pj;
   *pj = tmp;
  }
  *start = *pj;
  *pj = x;

  QuickSort(start, pj);
  QuickSort(pj + 1, end);
 }
}