快速排序

这个是排序
还有一个二分插入

虽然最坏情况下时间复杂度为

不过平均性能比较好 ，而且是原址排序

思路：
每次先取得中间值（取A[q]为哨兵，比哨兵小的值在左边，最后一个比哨兵小的值的位置+1（pos） 和A[q]交换）
然后sort

pos是比哨兵小的值
i遍历从p到q
出现需要交换的值的时候（哨兵大于等于A[i]）pos+1
pos是比哨兵小的值，pos+1是大于等于哨兵的值，
A[i]是需要交换的值。change A[i]和A[pos]
然后pos+1和哨兵的值交换。
伪代码如下：

QUICKSORT(A,p,r)
if p<r
q=DPARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)

PARTITION(A,p,r)
x=A[r]
i =p-1
for j=p to r-1
  if a[j]<=x
    i=i+1
    exchange a[i]? with A[j]?
exchange A[i+1] with A[r]?
return i+1

这个是算法导论中的实现方法
思路是：
选数组中最后一个元素作为基准进行划分，一次划分之后，返回一个位置（代码实现中的position字段）在这个位置之前所有的元素都比a[position]小，而在这个位置之后的元素都比这个元素大。然后用分治法把position左右两边的子问题在重新递归求解。
代码实现：

    @Test
    public void test01(){
        int[]a = { 2, 8, 7, 1, 3, 5, 6, 4 };
        sort(a, 0, a.length - 1);
        printArray(a);
    }
    public void sort(int[] a, int low, int height){
        
        if(low < height){
            int position = partition(a, low, height);
            sort(a, low, position - 1);
            sort(a, position + 1, height);
        }
    }
    public int partition(int[] a, int low, int height){
        //和这个中间值比较
        int x = a[height];
        //表示位置   需要被换的   这个位置开始比tmp大  后来被替换到后面
        int position = low - 1;
        //交换类排序
        //i不从0开始  要注意这几个不从0开始的
        for (int i = low; i < height; i++) {
            if(a[i] <= x){
                //如果小于   就和前面的position
                position ++;
//              int tmp = a[position];
//              a[position] = a[i];
//              a[i] = tmp;
                int tmp = a[position];
                a[position] = a[i];
                a[i] = tmp;
            }
        }
        //交换pos+1 和 x
        int tmp = a[position + 1];
        a[position + 1] = a[height];
        a[height] = tmp;
        return position +1;
    }
    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + "");
        }
    }

从代码里面看出来快速排序是不稳定排序，属于交换排序。
分析：
主要就是partition方法
这个方法是对数组从low到height之间的元素排序并返回划分左右两边的中间位置
需要注意的几个边界：

1. for循环不能从0开始 （因为要后面递归的不一定是从0开始的）
2. for循环中i < height 的height 不能用数组长度 因为有一个基准去掉了。

需要理解的几个问题：

1. 为什么需要a[i] == x的时候也交换？
   因为如果不交换，后面的比a[height] (基准)小的时候，要和前面的交换（会把和基准相等的交换到后面去）
2. 交换基准（或者定位position）
   基准是数组的分界，左边比基准小右边 比基准大
   因为当发生a[i] <= x的时候 就会发生（记录position后移），也就是i循环完之后position位置刚好是（从左到右）最后一个比基准小的数（包括position+1的后面元素都比基准要大），所以用基准把这个位置替换并返回这个位置