快速排序详解

快速排序介绍

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（分治法）

第一趟快速排序

在数组中找一个支点(任意),经过一趟排序后，支点左边的数都要比支点小，支点右边的数都要比支点大

现在我们有一个数组：int arr[]={1,4,5,67,2,7,8,6,9,44};
经过一趟排序之后，如果我选择数组中间的数作为支点：7(任意的)，

那么第一趟排序后的结果是这样的：{1,4,5,6,2,7,8,67,9,44}
那么就实现了支点左边的数比支点小，支点右边的数比支点大

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归分析与代码实现

现在我们的数组是这样的：，既然我们比7小的在左边，比7大的在右边，那么我们只要将”左边“的排好顺序，又将”右边“的排好序，那整个数组是不是就有序了？想一想，是不是？

又回顾一下递归：”左边“的排好顺序，”右边“的排好序，跟我们第一趟排序的做法是不是一致的？

只不过是参数不一样：第一趟排序是任选了一个支点，比支点小的在左边，比支点大的在右边。那么，我们想要”左边“的排好顺序，只要在”左边“部分找一个支点，比支点小的在左边，比支点大的在右边。