快排

一、(1)
假如有一个数组 [8,10,2,3,6,1,5] ，我们拿出5作为参考，将小于5的数放到它的左边，大于5的数放到它的右边，经过这一轮操作之后，数组就变成了[2,3,1,5,6,8,10]。

接下来我们可以运用上面的方法对左右两边进行操作了。
左边：[2,3,1] 拿出来1，小的放左边，大的放右边，[1,2,3]
右边：[6,8,10] 拿出来10，小的放左边，大的放右边，[6,8,10]

其实每一轮操作就相当于让这个参考数字回到正确位置的操作，它的前面有几个数，后面有几个数，在后面的操作中是不会变的。

(2)
实际操作中，为了节省内存，在将元素拿到参考数字两边的时候会采用交换元素的方式。分别从两边开始找符合条件的元素，等两边都找到之后进行交换。

[8,10,2,4,3,6,1,5]  --> 符合条件的，左：8，右：1，进行交换--> [1,10,2,4,3,6,8,5]
[1,10,2,4,3,6,8,5]  --> 符合条件的，左：10，右：3，进行交换--> [1,3,2,4,10,6,8,5]
....

二、代码：

    public static void sort(int a[], int low, int hight) {
        int i, j, index;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        index = a[i]; // 用子表的第一个记录做基准
        while (i < j) { // 从表的两端交替向中间扫描
            while (i < j && a[j] >= index) {
                j--;
            }
            if (i < j) {
                // a[i++] = a[j];// 用比基准小的记录替换低位记录
                a[i] = a[j];
            }
            while (i < j && a[i] < index) {
                i++;
            }
            if (i < j) { // 用比基准大的记录替换高位记录
                // a[j--] = a[i];
                a[j] = a[i];
            }
        }
        a[i] = index;// 将基准数值替换回 a[i]
        sort(a, low, i - 1); // 对低子表进行递归排序
        sort(a, i + 1, hight); // 对高子表进行递归排序

    }

    public static void quickSort(int a[]) {
        sort(a, 0, a.length - 1);
    }

三、通过稳定性、时间复杂度、空间复杂度三个方面分析一下归并排序：
1、稳定性
显然，在进行元素交换的时候，相同元素的前后顺序会发生变化，所以快排是不稳定的。

2.时间复杂度
https://www.jianshu.com/p/6cf2cf701c57
和归并算法都采用了分治思想，所以他们的复杂度是一样的，都为O(nlogn)

3.空间复杂度
前面已经论述过为了降低空间复杂度采用了交换的方法，之后的复杂度为O(1)