快速排序

快速排序是对冒泡排序的一种改进。

思想：

如上图所示，一趟快排后的结果就是：key,左边的都比key小，右边的都比key大；
接下来的步骤是如图：

代码实现

void QuickSort(int* a, int left,int right)
{
    assert(a);
    int mid = ThreeMid(a, left, right);
    swap(a[mid], a[right]);
    int last = right;         //[0,9]
    int key = a[right];
    if (left >= last)
    {
        return;
    }
    while (left < last)
    {
        while (left < last && a[left] <= key)
        {
            ++left;
        }
        while (left < last && a[last] >= key)
        {
            --last;
        }
        if (left < last)
        {
            swap(a[left], a[last]);
        }
    }
    if (a[left] >= key)
    {
        swap(a[left], a[right]);
    }
    if (left - 1 >= 0)    //防止下标越界
    {
        QuickSort(a, 0, left - 1);
    }
    QuickSort(a, left + 1, right);
}

有朋友要问了，ThreeMid是什么鬼？
解释如下：
快排的复杂度是期望O(nlogn)的，也就是平均情况下每次选取的基准值能把序列分成大小相近的两份，但是如果输入数据已经是一有序数据，或者接近于有序，每次选的key是接近于Max/Min的数据，那么每次分治就分得极为不平均(每次分出1 和 n- 1两块)，递归的深度不是O(logn)而是O(n)所以总复杂度就囧了。一个办法就是三数取中法。

一般快排最坏的情况时间复杂度为：O(N^2)

三数取中法：

关于这一改进的最简单的描述大概是这样的：与一般的快速排序方法不同，它并不是选择待排数组的第一个数作为中轴，而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说，主要优势：它使得最坏情况发生的几率减小了。

• 三数取中代码
• int ThreeMid(int* a, int left, int right)
  {

  assert(a);
  int mid = left + (right - left) / 2;
  if (a[left] > a[right])
  {
      if (a[right] > a[mid])
      {
          return right;
      }
      else if (a[mid] > a[left])
      {
          return left;
      }
      else
          return mid;
  }
  // (a[left] < a[right])
  else
  {
      if (a[right] < a[mid])
      {
          return right;
      }
      else if (a[mid] < a[left])
      {
          return left;
      }
      else
          return mid;
  }
  

  }

链接

百度百科上对他的介绍很全面，有兴趣的朋友可以看看，快速排序算法链接