快速排序(Quick Sort)是对冒泡排序的一种改进,通过一趟排序将数据序列分成两部分,其中一部分的所有数据比另一部分的所有数据都要小,然后按此方法对两部分数据分别进行快速排序,整个排序过程递归进行,最终使整个数据序列变成有序的序列。
快速排序算法的原理
快速排序算法的原理是：选择一个关键值作为基准值(一般选择第一个元素为基准元素),将比基准元素大的都放在右边的序列中,将比基准值小的都放在左边的序列中。具体的循环过程如下:
(1)从后面向前比较,用基准值和最后一个值进行比较。如果比基准值小,则交换位置;如果比基准值大,则继续比较下一个值,直到找到第一个比基准值小的值才交换位置
(2)在从后面找到第一个比基准值小的值并交换位置后,从前向后开始比较,如果有比基准值大的,则交换位置;如果没有,则继续比较下一个,直到找到第一个比基准值大的值才交换位置。
(3)重复执行以上过程,直到从前向后比较的缩影大于等于从后向前比较的索引,则结束一次循环。这时对于基准值来说,左右两边都是有序的数据序列。
(4)重复循环以上过程,分别比较左右两边的序列,直到整个数据序列有序。