|
|
|
|
快速排序（Quick Sort）的主要思路为：通过对线性表序列的一趟扫描使某个结点移到中间的某个位置，且使其左边序列各结点的关键字都比该结点的关键字小，而其右边序列各结点的关键字都不比该结点的关键字小，常称这样的一次扫描为"划分"。然后，对左、右序列进行同样的处理，直到所有序列均只包含一个结点为止，这样便可将原线性表排好序。
|
|
|
|
快速排序可以看作是冒泡排序的改进，冒泡排序可以看作是快速排序的退化，即每趟划分总是在同一端进行。
|
|
|
|
若设待排序的记录序列{R1，R2，…，Rn}为R[1…n]，则对其按关键值的非递减序列进行快速排序的算法如下：
|
|
|
|
|
|
可见，快速排序可能会破坏两个相等记录的原来次序，因而快速排序算法是不稳定的。
|
|
|
|
|
|
|
|
| |
|
|
|
