软设之快速排序

快速排序是冒泡排序的改进算法

它采用的是分治法，基本思想是把原问题分解为若干规模更小但结构与原问题相似的子问题，通过递归解决这些子问题，然后将这些子问题的解组合成原问题的解。

它的步骤是

1.在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数。

2.采用相同方法对左右两组分别进行排序，直到所有记录都排到相应位置。

以数组57，68，59，52为例

选择57作为基准数组

57和52比较，52小，57和52交换位置

52，68，59，57

选择68和57比较，57小，57和68交换位置

52，57，59，68。

由于元素数量小，已经完成排序了。同样初始顺序数组，需要操作的次数比冒泡排序少多了。

快速排序的基准元素:一般是第一个元素，也可以是中位数。

快速排序是一种不稳定的排序方法，平均和最优情况下时间复杂度是O(nlog(2)n)

最差的情况，此时数组基本有序，以第一个时间复杂度是O(n^2)。以中位数为基准情况，时间复杂度是O(nlog(2)n)

空间复杂度是O(1)

需要辅助空间存储左侧数据和右侧数据，空间复杂度为O(n)

需要记录所有基准元素时，空间复杂度为O(log(2)n)