快速排序法就是用一个数作为基数，一次遍历，把小于基数的数放在基数的左面，把大于基数的数放在基数的右边，一次遍历之后第一个选中的基数放在了正确的位置。之后分别递归左边和右边的子数组。直到子数组的长度变成1，就是把每个数都放在了正确的位置。

例如排序  3 1 4 6 7 2 5 

将3作为基数，把3拿起，一次遍历之后，找到正确的位置，再放置3。（左游标在X，右游标在5）

                      X 1 4 6 7 2 5 

从右面开始找比3小的数，5>3,右游标左移，找到了2，把2放在X的位置，这时2的位置为空。（左游标在1，右游标在2）

                      2 1 4 6 7 X 5

从左面开始找比3大的数放在X的位置，找到了4。把4放在X，4原来的位置变为X（左游标在X，右游标在7）

                      2 1 X 6 7 4 5                

从右面找小于3的数，7>3,右游标左移，6>3，右游标左移。此时左右游标相等，都在X，把基数3放在X。一次遍历结束。

第一次排序后： 2  1     3      6  7 4  5

3的位置是正确的，左边数组2 1 ，右边数组6 7 4 5  继续重复上述方法。

左边排序   第一次基数为2     1  2   结束

右边排序   第一次基数为6     5  4  6  7        6在正确的位置

                   5 4 排序  4 5     7长度为1不用排序

                                   4 5 6 7      结束

递归结束  返回  1  2  3  4  5  6  7  

代码：

public int[] quickSort(int[] a, int l, int r) {

        if (l < r) {

            int i = l, j = r, v = a[l];//i:左边开始活动坐标，j:右边开始活动坐标，v：基数

            while (i < j) {//只要左边游标和游标不重叠的话那么就继续遍历               

          //每一轮遍历的时候只进行一轮，把右边的一个比基数小的数移动到左边，把左边比基数大的数移动到右边  

              while (i < j && a[j] > v)     // 找出右边比左边小的坐标 

                   j--;

            if (i < j)

               a[i++] = a[j];//进行移动，左边坐标移动一个数 

            while (i < j && a[i] < v)    // 找出左边比右边大的左边 

                   i++;

                if (i < j)

                    a[j--] = a[i];//进行移动，右边坐标移动一个数            }

            a[i] = v;//当游标重叠时填入基数 

             this.quickSort(a, l, i - 1);   // 左边递归

            this.quickSort(a, i + 1, r);  //右边递归

            return a; 

        }

        return a;

    }

各种排序的复杂度