快排的思想

    选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
    递归的将p左边和右边的数都按照第一步进行，直到不能递归。

分而治之，以求时间最快。

public static void quickSort(int[]a,int left,int right)
{
    if(left>right)
        return;
    int pivot=a[left];//定义基准值为数组第一个数
    int i=left;
    int j=right;

    while(i<j)
    {
        while(pivot<=a[j]&&i<j)//从右往左找比基准值小的数
            j--;
        while(pivot>=a[i]&&i<j)//从左往右找比基准值大的数
            i++;
        if(i<j) //如果i<j，交换它们
        {
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
    a[left]=a[i];
    a[i]=pivot;//把基准值放到合适的位置
    quickSort(a,left,i-1);//对左边的子数组进行快速排序
    quickSort(a,i+1,right);//对右边的子数组进行快速排序
}

代码有很多种，但是就单是这样看代码，是很不容易看懂的，网上有很多这类说法，大的放右边，小的放左边，实际上，很多人的基准值都是第一个，这样读起来，就很不好理解代码逻辑了，所以我来复现下实际执行步骤

有一组数：

7,0,8,3,2,3,5,2,9 a，最大的while循环第一遍 第一个为基准值为7, i=2，j=7 内部交换
7,0,2,3,2,3,5,8,9 b，最大的while循环第二遍 右往左找到比基准值小的 即 j=6时，这时候从左往右找最后一个比基准值大的 因为没有所有i=6时停止，
                        如果有，重复上一步，直到i>=j停止。此时将基准值与最后比基准值小的数交换；
5,0,2,3,2,3,7,8,9 c，接下来递归左边此时递归的参数为 0 ，6-1，所以只处理  5,0,2,3,2,3 这部分
5,0,2,3,2,3,7,8,9 d，因为先从右到左遍历，j找到的小值为最后一个j=5，即a[j]=3，i无法找到大的所以在i=5时停止 无法交换,跳出大循环交换
3,0,2,3,2,5,7,8,9 第三次左边递归 3,0,2,3,2，重复c，d，因为从左到右可以找到一个不比基准值小的数，所以得
3,0,2,2,3,5,7,8,9 第四次左边递归 3,0,2,2 此时无内部替换 
2,0,2,3,3,5,7,8,9 第五次左边递归 2,0,2，此时无内部替换
0,2,2,3,3,5,7,8,9 此时i=1 ，右边递归，但是事实上以及排序完成，所以右边递归大多数是自己和自己交换，可以忽略，递归完就完成了排序

因为文字不定可以看清晰，所以网上找了一个符合我的这份代码的图，有些人的图，真不知道他在做什么，

放上图片地址：http://blog.csdn.net/vast_sea/article/details/8113422

说不定，看他的比我这份要清晰。

上面我也是一路debug下来得到的，至于右边递归部分，就像是一种保证一样，避免出错。数据小，所以右边没递归就排完了

另外快排的时间复杂度

平均为：

最坏为：

你也可以看维基百科了解相关资料：快速排序