快速排序核心思想是每趟调整基准值的位置，将小于基准值的数左移，将大于基准值的数右移，这样确保基准值左侧的数小于基准值，右侧的数大于基准值。 在下一趟时，调整上一趟分割的两个区域的基准值位置，直到最后完成所有基准值的调整。
调整基准值的前提是选择一个合理的基准值，一般是指定某个位置的数或者随机某个位置的数作为基准值( 我这里取每个区域的第一个数 ) 。
调整基准值的过程大概描述：
1、取第一个数作为基准值，声明从前往后搜索指针 i ,从后往前搜索指针 j ；
2、从后往前找，比基准值大则指针 j 减一，直到找到一个比基准值小的数，并和基准值交换（交换完后此时基准值的位置在 j ）；
3、从后往前查找结束再从前往后找，比基准值小则指针 i 加一，直到找到一个比基准值大的数，并和基准值交换（交换完后此时基准值的位置在 i ）；
4、当指针 i 等于 j 时，结束当前趟数基准值的调整。
待排序的数组如下：
image
调整基准值的过程我举个例子吧：
第一趟基准值key取72，i=0，j=8;
从后往前找，找到一个比72小的值48，与72交换，此时i=0，j=7;
image
从后往前找并交换之后确定了48是在72的左侧了，那么从前往后找的时候就不需要再判断i位置上的元素了，所以i=i+1=1。再从i的位置往后找，找到一个比72大的值88，与72交换，此时i=2，j=7;
image
从前往后找并交换之后确定了88是在72的右侧了，那么从后往前找的时候就不需要再判断j位置上的元素了，所以j=j-1=6。再从j的位置往前找，找到一个比72小的值42，与72交换，此时i=2，j=4;
image
从后往前找并交换之后确定了42是在72的左侧了，那么从前往后找的时候就不需要再判断i位置上的元素了，所以i=i+1=3。再从i的位置往后找，此时没有找到一个比72大的数，那么当前趟结束，找到基准值的位置i=j=4;
所以第一趟结束后的数组排列是：
image
查找基准值的思路大概是这样子，条理清晰之后，剩下的也就是重复上面的操作了，因此代码写起来就比较简单了。
调整基准值代码的具体实现：
image
每趟找到基准值的位置后，对基准值左边的数据和右边的数据进行基准值的调整 ，直到最后没有可调整的数据，那也就排完序了。
具体代码实现：
image
所以最后输出的数组就是排好序的数组了。
关注公众号 「吃菜长肉」，获取更多内容。
网友评论