七大排序算法——快速排序

一、快速速排序采用了一种叫分治的思想　

　　分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

二、快速排序的原理

        1、选择一个关键值作为基准值，比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边序列（一般是无序的），一般选择序列的第一个元素作为基准值。

        2、第一次循环：

                （1）从后往前比较，用基准值和最后一个值比较，如果比基准值小，就交换位置，如果没有继续向前遍历，直到找到第一个比基准值小的值才交换。

                （2）找到这个值后，从前往后遍历，如果比基准值大的，交换位置，如果没有向后遍历，直到找打第一个比基准值大的值才交换。

                （3）直到从前往后的比较索引 > 从后往前比较的索引，结束第一轮次循环，此时，对于基准值来说，左右两边就是有序的了。        也就是当start == end时，第一轮排序完成

三、快速排序图解

 

 

 

 

 

 

 

 

 

 

 

 

 

 

注意：上边的循环之后就得到了基准值左右两边的序列了，交换的是起始和结束的值，不是基准值

            start是从前往后遍历的基准值的索引值

            end是从后往前遍历的基准值的索引值

四、代码实现

五、完整代码