对快速排序的总结（面试常考算法）

今天看到了同学给我看的快速排序，写一下自己的思考过程还有理解

其实快速排序就是将一趟排序的记录划分为独立的两部分，称为前半区和后半区，前半区记录的关键字均不大于后半区记录的关键字，然后再分别对这两部分记录进行快速排序，从而使整个序列变得有序。

原理：
1.首先你要找出一个值：p（基准数，就是一个用来和头尾指针比较的值，也就是参照值，它可以是数组的头元素，也可以是数组的尾元素，可以是数组的中间元素）
2.分别用i和j当做指针指向数组的头部和尾部，通过i和j对数组进行遍历（自然是i向后遍历，j向前遍历）。最后把比p大的放p的右边，比p小的放p的左边
3.i去找比p大的数，j去找比p小的数，找到后将data[i]和data[j]交换
4.一直遍历下去重复第3步，直到遍历结束
（ps：序列越接近有序效率越低，越接近无序效率越高）

public class partition {
    int partition(int data[], int low, int high){
        //用data[low]作为比较元素p来进行划分
        int i = low, j = high; //把i当做头指针，把j当尾指针
        int p;
        p =data[i];
        while(i < j){
            while(i < j && data[j] >= p)
                j--;
            data[i] = data[j];
            while(i < j && data[i] <= p)
                i++;
            data[j] = data[i];
        }
        data[i] = p;
        return i;
    }
}

拆分开来理解：

假设上面表格是data的数据：i和j对应的则是左边的指针，p对应的是右边的值，很明显现在这个表格现在是无序的。基准数p是3

在快速排序中，因为我们是拿基准数当做参照值来比较，，所以我们先当做i=0的值不存在（其实还是存在的）

2.j从右向左移动，找到小于等于基准数3的数，找到了0

3.我们把0放进i=0里面去（相当于把data[4]的值放进了data[1]里面去），并将i从左向右移动，找到一个大于等于基准数3的数，找到了4

4.我们把4放进j=4里面去，并将j从右向左移动，再找一个小于等于3的数，找到了2

5.我们把2再放到i=2里面去

6.i=2,j=3,遍历条件是i<3，很明显这是最后一次循环，而我们j=3的值还是空着的，上面说了其实那个p值3还是一直存在的，那么这个空出来的地方显而易见就是这个3，排序完成