快排（代码的实现）

//三数取中
int MidSizeof(int* a, int left, int right)
{
  int mid = (left + right) / 2;
 
  if (a[left] < a[mid]) 
  {
    if (a[mid] < a[right]) 
    {
      return mid; 
    }
    else if (a[left] > a[right]) 
    {
      return left; 
    }
    else
    {
      return right; 
    }
  }
  else // a[left] > a[mid]
  {
    if (a[mid] > a[right]) 
    {
      return mid; 
    }
    else if (a[left] < a[right]) 
    {
      return left; 
    }
    else
    {
      return right; 
    }
  }
}
 
 
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
 
  if (left >= right)
  {
    return;
  }
 
  int _left = left;//保存左右边界
  int _right = right;
 
  //随机值
  //int end = rand();//基准值 
  //end %= (right - left + 1); 
  //end += left;  
 
  //三数取中
  int end = MidSizeof(a, left, right); 
 
  swp(&a[_left], &a[end]);
  //升序
  while (left < right) //右边找小
  {
    while (left < right && a[right] >= a[_left]) 
    {
      --right; 
    }
 
    while (left < right && a[left] <= a[_left]) //左边找大 
    {
      ++left; 
    }
 
    swp(&a[left], &a[right]);  
  }
  swp(&a[left], &a[_left]); 
 
 
  PartSort1(a, _left, right - 1);
  PartSort1(a, left + 1, _right);
  
 
}

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
  if (left >= right) 
  {
    return;
  }
  //int per = rand();//基准值 
  //per %= (right - left + 1);
  //per += left;
 
  int per = MidSizeof(a, left, right);
 
  swp(&a[per], &a[left]);
 
  int end = left; // 遇到大就停
  int cur = end + 1;//遇到小就停
 
  while (cur <= right)
  {
    if (a[cur] <= a[left] && ++end != cur) 
    {
      swp(&a[end], &a[cur]); 
    }
    
    cur++;
  }
 
  swp(&a[left], &a[end]); 
 
  PartSort3(a, left, end - 1);  
  PartSort3(a, end + 1, right);  
}

//初始化
void STInit(ST* ps)
{
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
 
//销毁
void STDestroy(ST* ps)
{
  free(ps->a);
  ps->capacity = ps->top = 0;
}
 
//压栈
void STPush(ST* ps, STDataType x)
{
  //判断是否扩容
  if (ps->top == ps->capacity)
  {
    int nowcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
    ST* pec = (ST*)realloc(ps->a, nowcapacity * sizeof(ST));
    if (pec == NULL)
    {
      perror("realloc\n");
      return;
    }
    ps->a = pec;
    ps->capacity = nowcapacity;
  }
  //压入数据
  ps->a[ps->top] = x;
  ps->top++;
}
 
//出栈
void STPop(ST* ps)
{
  assert(ps);
  assert(ps->a);
  ps->top--; 
}
 
//查找栈顶元素
STDataType STTop(ST* ps)
{
  assert(ps); 
  assert(ps->a);
  return ps->a[ps->top - 1];
}
 
//元素个数
int STSize(ST* ps)
{
  assert(ps);
  assert(ps->a);
  return ps->top;
}
 
//栈是否为空
bool STEmpty(ST* ps)
{
  return ps->top == 0;
}

//非递归实现快排（栈）
void QuickSortNonR(int* a, int left, int right)
{
  ST st;
  STInit(&st);
 
  STPush(&st, right);
  STPush(&st, left);
 
  while (!STEmpty(&st))  
  {
 
    left = STTop(&st);
    STPop(&st);
    right = STTop(&st); 
    STPop(&st);
 
    int _left = left;//保存左右边界
    int _right = right;
 
    //基准值: left 
    
    //升序
    while (left < right ) //右边找小
    {
      while (left < right && a[right] >= a[_left]) 
      {
        --right; 
      }
 
      while (left < right && a[left] <= a[_left]) //左边找大  
      {
        ++left;
      }
 
      swp(&a[left], &a[right]);
    }
    swp(&a[left], &a[_left]);
 
    
    
    if (_left < right - 1)
    {
      STPush(&st, right - 1);
      STPush(&st, _left);
    }
 
    if (left + 1 < _right)
    {
      STPush(&st, _right);
      STPush(&st, left + 1);
    }
 
  }
 
 
 
  STDestroy(&st);
}