快速排序，面试必问题。面试百度时三次面试被问到快排，本以为掌握的很好，但细节方面还是不到位，发挥的不是很好，特此记录，勉励自己。
问题：为什么是nlog(n),n怎么来，log(n)怎么来
快速排序
快速排序是应用最广泛的排序算法，基本思路是：将一个数组分成两个子数组,将两部分独立排序,当两个子数组都有序时,整个数组也就有序了，这与归并排序有所不同，归并排序中，将一个数组分成两个数组后，需要对两个子数组进行归并，在归并的过程中排序，而快速排序是在将一个数组分成两个数组的过程中进行排序，当分到尽头的时候，数组就已经有序了，不需要再进行其它任何操作
快速排序中重点是找到将一个数组分为两个数组的切分点，在归并排序中，其实也是有这样的切分点的，就是 mid，也就是说归并排序默认将一个数组等分，而在快速排序中，对一个数组的切分，并不一定是等分，需要根据具体的切分点的位置来进行切分，所以，找到合适的切分点的位置是很重要的，直接影响到整个排序的性能。
寻找切分点
切分点需要满足三个条件：(假设切分点索引为 k)
对于某个索引 k,数组中对应索引的值 a[k] 是确定的
数组索引[lo,k-1] (即切分点左边的所有元素) 中的所有元素的值都不大于切分点元素的值( <= )
数组索引[k+1,hi] (即切分点右边的所有元素) 中的所有元素的值都不小于切分点元素的值( >= )
寻找切分点的过程是：(其中 lo 为数组最低位索引，hi 为数组最高位索引，从左往右遍历的指针为 i，从右往左遍历的指针为 j)
取 a[lo] 的值作为初始切分点元素的值，即切分点索引为 0，值为 16
从数组左端向右遍历[1,5]，当遇到一个大于等于切分点的元素，即索引为 2 的元素，停止遍历，此时 i=2
从数组右端向左遍历[5,0]，当遇到一个小于等于切分点的元素，即索引为 5 的元素，停止遍历，此时 j=5
从数组左端向右遍历[3,5]，当遇到一个大于等于切分点的元素，即索引为 5 的元素，停止遍历，此时 i=5
从数组右端向左遍历[4,0]，当遇到一个小于等于切分点的元素，即索引为 4 的元素，停止遍历，此时 j=4
当 i>=j 时停止循环，不会执行 i 和 j 的交换，而是将切分点元素和 j 元素交换，交换后:
到此，寻找第一个切分点完成，切分点索引为 4，对应的值为 16
找到切分点，接下来将数组按照切分点分成两部分，从上面的执行结果可以知道，数组将被分为 [0,3] 和 [5,5]，接下来就是对 [0,3] 部分重复寻找切分点的过程：
取 a[lo] 的值作为初始切分点元素的值，即切分点索引为 0，值为 14
从数组左端向右遍历[1,3]，当遇到一个大于等于切分点的元素，没有找到，遍历到数组尽头，此时 i=3
从数组右端向左遍历[3,0]，当遇到一个小于等于切分点的元素，即索引为 3 的元素，停止遍历，此时 j=3
当 i>=j 时停止循环，不会执行 i 和 j 的交换，而是将切分点元素和 j 元素交换，交换后:
到此，寻找第二个切分点完成，切分点索引为 3，对应的值为 14
同理，数组将按照切分点分为 [0,2] 和[3,3]，接下来对 [0,2] 部分重复寻找切分点：
取 a[lo] 的值作为初始切分点元素的值，即切分点索引为 0，值为 11
从数组左端向右遍历[1,2]，当遇到一个大于等于切分点的元素，即索引为 1 的元素，停止遍历，此时 i=1
从数组右端向左遍历[2,0]，当遇到一个小于等于切分点的元素，没有找到，遍历到数组起始位置，此时 j=0
当 i>=j 时停止循环，不会执行 i 和 j 的交换，而是将切分点元素和 j 元素交换，交换后:
到此，寻找第三个切分点完成，切分点索引为 0，对应的值为 11
此时，由于切分点位置为 0，所以只能切分出一个子数组，即 [1,2]，继续寻找切分点
取 a[lo] 的值作为初始切分点元素的值，即切分点索引为 1，值为 13
从数组左端向右遍历[2,2]，当遇到一个大于等于切分点的元素，没有找到，遍历到数组尽头，此时 i=2
从数组右端向左遍历[2,1]，当遇到一个小于等于切分点的元素，即索引为 2 的元素，此时 j=2
当 i>=j 时停止循环，不会执行 i 和 j 的交换，而是将切分点元素和 j 元素交换，交换后:
到此，寻找第四个切分点完成，切分点索引为 2，对应的值为 12
数据已经有序了，整个过程中寻找了四次切分点
网友评论