什么是快速排序算法?

如题所述

快速排序过程即为如下三个步骤:
1. 选定序列中的一个元素,作为枢轴
2. 用该枢纽划分序列,依据指定的偏序规则使得位于枢轴左侧的序列都比枢纽小,位于枢轴右侧的数都比枢纽大
3. 对划分所得的序列重复1,2步,直到序列不可再分。
所以由上面的三个步骤可知:
1.快速排序每次都会将序列一分为二
2.划分完序列之后即确定了枢轴在最终有序序列所处的位置
快速排序划分的结果,受到枢轴选择的影响,假设算法选择序列的第一个元素作为枢轴。
则枢轴为数字503,小于503的数将位于其左边,大于503的数将位于其右边,所以序列为:
{462,87,275,61,170} , 503 , {897,908,653,512}
这个序列的由来按照严版数据结构中使用的移动元素算法,其经历了如下几个步骤:
1. 从右找到一个比枢轴小的数与其进行交换
2. 从左找到一个比枢轴大的数与其进行交换
3. 直到左右两个移动的查找指针已经相遇
1. 从右找到比503小的数462与503交换位置
{462,87,512,61,908,170,897,275,653,503}
2. 从左找到比503大的数512与503交换位置
{462,87,503,61,908,170,897,275,653,512}
3. 从右找到比503小的数275与503交换位置
{462,87,275,61,908,170,897,503,653,512}
4. 从左找到比503大的数908与503交换位置
{462,87,275,61,503,170,897,908,653,512}
5. 从右找到比503小的数170与503交换位置得到最终序列,此时503已经位于最终位置
{462,87,275,61,170, 503 ,897,908,653,512}
接下来重复的对划分后的序列{462,87,275,61,170}和 {897,908,653,512}重复上面的过
程则可以完成整个快速排序。
温馨提示:答案为网友推荐,仅供参考