近些天来，由于需要找工作，特将数据机构与算法中的快速排序温习总结了一下，希望对于大家学习有所帮助。
首先，快速排序的基本思想是基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换low和high位置的值，如此往复循环，直到low>=high,然后把基准点的值放到high这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
在快速排序算法中，最主要的就是基准元素的选取和元素的移动。
基准元素的选取最简单的就是选取数列中的第一个元素。但是对于这种情况下，如果选取的基准元素是数列的最大值个最小值，就会使得分治法无法发挥作用，使得快排得得时间复杂度倒退至0（N^2）。在选择基准元素的时候可以不选择数列的第一个元素，而随机选择一个元素作为基准元素。这样的话会使得，数列在完全逆序的情况下，也可以有效的将数列分为两部分。但是随机选择记基准元素也不能完全的避免上面所说的情况。
第二个主要的问题就是元素的移动情况。对于这个元素的移动，可以实现的方法有两种，第一种是挖坑发，第二种就是指针交换法。
对于挖坑法，对于一个给定的原始数列，要求从大到小的排序，首选我们选择一个基准元素Pivot,并记住这个Index,对于这样位置的就相当于是一个坑，并且设置有两个指针left和right。如下图所示：
在接下来，从right指针开始，把指针指向的元素和基准元素作比较，如果比基准元素大的话，则right指针向左移动，若比基准元素小的话，则将right指向的元素填入这个坑中。在这个例子中将1作为元素填入坑中，这样的话元素1原来所在的位置就成为了新的坑。这样的话，left向右移动一位。注意看此时的index在1所在的位置。此时left左边的区域就代表着比基准元素小的区域。
然后比较left指针指向的位置是7大于基准元素4，于是将7本来的位置成为了新的坑，并将right向左移动一位。此时的index在7原来的位置。
此时right右边的位置都是比基准元素大的区域。
right指向的元素8>4,于是right继续左移。
此时right指向了2,2<4，于是用2来填坑，就是将2放到了index指向的位置，更新之后的index指向了2所在的位置，left向右移动，切换到left。
left指向的元素是6>4,于是将6来填坑，放到了index指向的位置，并且将right向左移动。index指向6原先所在的位置。
right指向的元素3<4,于是用3来填坑，并且left向右移动一位，index更新到3原先在的位置。
left指向的位置5>4,于是用5来填坑，index指向了5所在的位置，right向左移动。
此时的right和left重合，这时候就将基准元素4放到了index所指向的位置，这时候排序基本完成。4左边的都是小于4的元素，右边的都是大于4的元素。
