排序之快速排序

快速排序采用了分治法的思想。快速排序先把大数组划分成两个数组，使得一边的数组关键字均大于另一边的数组关键字。然后分别对两个数组关键字递归排序。

图片来源：维基百科

• 快速排序是一种不稳定的排序。
• 快速排序的平均时间复杂度为 O(nlogn)，最坏的情况下时间复杂度为 O(n²)。
• 快速排序的空间复杂度为 O(logn)。

具体做法：

• 从数组中选择一个关键字，称为枢轴(pivot)。
• 划分：重新排序数组，使得所有小于枢轴的元素都在枢轴前面，所有大于枢轴的元素都在枢轴后面。最后，枢轴所在的位置就是它在数组中最终的位置。
• 递归：对划分好的两个数组递归调用上面的步骤。

快速排序的伪代码：

ALGORITHM quicksort(A, lo, hi)
  IF lo < hi THEN
    p ← partition(A, lo, hi)
    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)
  END IF
END ALGORITHM

ALGORITHM partition(A, lo, hi)
  pivot ← A[hi]
  i ← lo
  FOR j ← lo TO hi -1 DO
    IF A[j] < pivot THEN
      IF i != j THEN
        swap A[i] with A[j]
      END IF
      i ← i + 1
    END IF
  END FOR
  swap A[i] with A[j]
  return i
END ALGORITHM