type
status
date
slug
summary
tags
category
icon
password
快速排序是在八大排序算法中用的频率比较高的一种，希望大家都能熟练掌握。
一、原理
升序：假设有一个数组array[10]，其中的元素为{ 5, 3, 9, 16, 28, 0, 4, 7, 29, 44 }。
1.首先我们需要选择一个元素作为分界值key，例如选首元素5；然后我们可以用两个变量i=0，j=9去记录数组的首尾下标。
2.从array[j]开始和key比较，如果比key大，则j自减，直到找到比key小的数（array[6]），此时判断i是否小于j（不是直接跳出循环到步骤5），如果是则将array[j]赋值给array[i]（数组变成了{ 4, 3, 9, 16, 28, 0, 4, 7, 29, 44 }），然后i自增（自增只是为了少比较一次）。
3.然后我们从array[i]开始和key比较，比key小，i自增，直到找到比key大的数（array[2]），此时判断i是否小于j（不是直接跳出循环到步骤5），如果是则将array[i]给array[j]（数组变成了{ 4, 3, 9, 16, 28, 0, 9, 7, 29, 44 }），然后j自减（自减只是为了少比较一次）。
4.重复以上步骤直到i==j时结束（数组变成了{ 4, 3, 0, 16, 28, 16, 9, 7, 29, 44 }，此时i和j都是3）；
5.循环结束后把key值赋给array[i]（数组变成了{ 4, 3, 0, 5, 28, 16, 9, 7, 29, 44 }）；做到这里我们是不是可以发现，分界值key左边的数都比他小，而分界值key右边的数都比他大，这样我们的第一轮快排就完成了。
6.此时的5把数组分成了两个未排序数组，我们对两边继续重复上述步骤即可（递归思想）。
二、代码
三、结果
快排的总体思路其实不难，只要理解了第一轮排序，基本上就掌握了快排的思想，但是还是要多上手实践几遍才能熟悉使用。
- Author:lzzd
- URL:https://lazy-zed.com/article/c%2B%2B_4
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
.png?table=block&id=19785e12-7d7c-8078-a881-fba941a4e6d9&t=19785e12-7d7c-8078-a881-fba941a4e6d9)
.png?table=block&id=19885e12-7d7c-80e0-9466-ccfdb68a297f&t=19885e12-7d7c-80e0-9466-ccfdb68a297f)
.png?table=block&id=19885e12-7d7c-8090-b2f9-d59fd470ae2a&t=19885e12-7d7c-8090-b2f9-d59fd470ae2a)
