图解快排——快速排序算法(quick sort)

算法思想

快速排序算法是对冒泡排序算法的一种改进算法，在当前所有内部排序算法中，快速排序算法被认为是最好的排序算法之一。

快速排序的基本思想： 通过一趟排序将待排序的序列分割为左右两个子序列，左边的子序列中所有数据都比右边子序列中的数据小，然后对左右两个子序列继续进行排序，直到整个序列有序。

具体实现步骤是这样的，首先从序列中任意选择一个元素，把该元素作为枢轴，然后将小于等于枢轴的所有元素都移到枢轴的左侧，把大于枢轴的元素都移到枢轴的右侧。这样，以枢轴为界，划分出两个子序列，左侧子序列所有元素都小于右侧子序列。枢轴元素不属于任一子序列，并且枢轴元素当前所在位置就是该元素在整个排序完成后的最终位置。这样一个划分左右子序列的过程就叫做快速排序的一趟排序，或称为一次划分。递归此划分过程，直到整个序列有序。

算法图解

首先给出一个无序序列[21, 100, 3, 50, 1]，选取一个元素为基准元素，一般选择序列第一个元素21作为枢轴，然后设置两个指针，一个low指针指向左侧第一个位置，一个high指针指向右侧最后一个位置。

首先取出基准元素21，此时low指向的位置留出一个空位。我们规定，指向空的指针不移动。此时应该操作high指针，如果high指针指向的元素大于基准元素21，那么high指针左移；如果high指针指向的元素小于基准元素21，那么将high指针指向的元素放到low指针指向的空位处。显然，当前high指向的1小于21，所以把1放到low指向的位置，此时high指向为空。

high指针指向空，操作low指针，对low指针：如果low指针指向元素小于基准元素21，那么low指针右移；如果low指针指向元素大于基准元素21，那么把low指针指向的元素放到high指向的空位处。

此时，100大于21，元素放到high，在代码中实际上就是交换low和high指向的元素值。

此时，low指向空，操作high，100大于21，high指针左移。

high指针指向50，依然大于21，high指针继续左移。

当high指向3的时候，3小于21，应交换元素。

此时，high指针指向空，操作low指针，low指向3，小于基准元素21，low指针右移。右移后我们发现，low指针和high指针指向同一个位置，此时将基准元素插入。

最后得到的序列，21左侧全部是小于21的元素，21右侧全部是大于21的元素。并且在本例中，划分好左右序列后，整个序列直接有序了。

算法实现（C语言）

void qSortArray(int array[], int start, int last)
{
  int low = start;
  int high = last;
  if (low < high)
  {
    while (low < high)
    {
      while (array[low] <= array[start] && low < last)
      {
        low++;//满足小于基准的条件，指针右移
      }
      while (array[high] >= array[start] && high > start)
      {
        high--;//满足大于基准的条件，指针左移
      }
      if (low < high)
      {
        swap(array[low], array[high]);//交换两个不满足条件的元素
      }
      else
      {
        break;
      }
    }
    swap(array[start], array[high]);//插入基准元素
    qSortArray(array, start, high - 1);
    qSortArray(array, high + 1, last);
  }
}

性能分析

稳定性

由于在快速排序中，元素的比较和交换是跳跃进行的，所以快速排序是一种不稳定的排序算法。比如下图所示，在划分时就改变了序列中两个1原本的顺序，本来在后面的1跑到了前面。

复杂度分析

快速排序的平均时间复杂度是O(nlogn)，但是在实际排序中，时间复杂度和基准元素（枢轴）的选择有关。如果枢轴选取不好，那么快速排序有可能就会退化为冒泡排序，时间复杂度为O(n*n)。

由于快速排序是通过递归实现的，而递归又要依靠栈空间来实现，所以快速排序相对于其它排序更耗费空间资源。

通常来说，为了避免快速排序退化为冒泡排序，以及递归栈过深的问题，我们一般依据“三者取中”的法则来选取基准元素，“三者”即序列首元素、序列尾元素、序列中间元素，在三者中取中值作为本趟快速排序的基准元素。