数据结构（快速排序）
最近学习数据结构，学习到了快速排序。利用BLOG记录一下自己的学习。免去纸面记录的麻烦。
快速排序又称为：分划交换排序或分治法。
分治的原理：
（1）分解：将原来的问题分解为几个子问题。
（2）求解：递归的解决各个子问题，当规模足够小的时候便可以直接进行求解。
（3）组合：将子问题的解组合为原问题的解。
快排的算法思想：
快排需要一个基准点（枢轴/支点/基准记录），就是算法开始的参考，一般来说取数据点的第一个作为基准。每一趟排序的目的就是使得基准点到达一个逻辑归中的位置，就是说左边的记录全部都小于基准，右边全部大于基准，然后再处理左边和右边的子序列，直到所有序列规模很小时候可以直接进行排序。至于如何实现得到子序列，在序列的两端分别进行从左向右寻找比基准大的数和从右向左找比基准小的数，直到左边和右边寻找相遇，视为第一趟结束。直到所有的数都归到了所在的基准位，则快速排序结束，数据也变成了有序的。
快速排序快的原因在于他的交换是跳跃的而不是顺序的，和冒泡法不同的是，快排中更加强调先查询后再进行交换，而不是一味的莽夫一样的交换，因此快速排序的最差时间复杂度是O(N2)，平均时间复杂度为O(NlogN)。
投递饿了么等公司7个岗位 >