快速排序

1.D&C(divide and conquer)

在说快速排序的时候我们先说一下分而治之的思想，字面意思就是一件事情把它分成能处理的小事情，然后处理小事情，处理好了，大事情也就完成了，这也是递归算法的思想，分成能处理的小事情就是递归找基线事件的过程。找到基线事件，处理，停止递归，然后依次从调用栈返回，最后解决我们最初的问题。下面举个很经典的例子。

• 用最大方块均分地图
  思路是 长边截出短边的整数倍，然后剩下的继续长边截出短边的整数倍，直到没有剩下的，那时候我们就找到了最大的方块。如下图

  
  以最大方块均分地图示意图.png

这就是一种分而治之的思想，那这和我们快速排序有什么关系呢？

2.快速排序

上面讲了D&C策略，一种递归式解决问题的方法。而我们所说的快速排序也是基于这种策略实现的。下面通过一个例子来简单的介绍下快速排序。
快速排序的步骤：
（1）选择一个基准值pivot
（2）将数组中比pivot小的放在[pivot]左边,大于等于pivot的放在[pivot]右边
（3）然后左边数组和右边数组回到第一步，直到触发基线事件，数组长度小于2
将原数组小于基准值的数组放左边和大于等于基准值的数组放右边，然后再分别进行相同的处理直到找到基线事件。这不就是我们的分而治之的思想么（分成小到能被处理的事件）。代码实现如下。
java版：

    private static int partition(int[] arr, int right, int left){
        int pivot = arr[right]; //选择一个基准值
        while (right < left){
            if(pivot <= arr[left]){ //寻找比基准值大的
                left--;
            }
            arr[right] = arr[left]; //将比基准值小的放右边
            if(pivot > arr[right]){ //寻找比基准值小的
                right++;
            }
            arr[left] = arr[right]; //将比基准值大的放左边
        }
        arr[right] = pivot; //设置基准值
        return right; //返回基准值的位置
    }

    public static void quickSort(int[] arr, int right,int left){
        if(right < left){
            int pivot = partition(arr,right,left);
            quickSort(arr, right,pivot - 1); //递归处理左边数组
            quickSort(arr, pivot + 1, left); //递归处理右边边数组
        }
    }

是不是感觉有点长并且并不是一目了然，我们来看看Python写的。

def quickSort(arr):
    if len(arr) < 2:
        return arr
    else:
        return quickSort([i for i in arr[1:] if i <= arr[0]]) + [arr[0]] + quickSort([i for i in arr[1:] if i >arr[0]])

是不是很清晰了，下面附上清晰版的

def quickSort(arr):
    if len(arr) < 2:  #基线条件，为空或只包含一个元素的数组是有序的
        return arr
    else:
        pivot = arr[0]  #选择基准值
        left = quickSort([i for i in arr[1:] if i < pivot])  #左边比基准小的数组
        right =  quickSort([i for i in arr[1:] if i >= pivot])  #右边比基准大于等于的数组
        return quickSort(left) + [pivot] + quickSort(right) 

这篇文章是看《算法图解》关于快排的读后感，挺不错的一本书。