这两种排序算法都采用了分治算法的思想。

1. 归并算法

将一个待排序数组从中间分成 2 部分，分别将这 2 部分排好序，然后再将之合并。这是一个递归的过程，左右两部分再用同样的方式排序，直至递归结束。用伪代码来理解：

mergeSort(array) {
    mergeSort(array, 0, array.size - 1)
}

mergeSort(array, p, r) {
     if (p >= r) 
         return
    q = (p + r) / 2
    //先将左半部分排序
    mergeSort(array, p, q)
    //再将右半部分排序
    mergeSort(array, q + 1, r)
    //将左右两边排好序的数据合并在一起
    merge(array[p, q],  array[p, q], array[q + 1, r])
}

代码如下（kotlin编写）：

fun mergeSort(array: IntArray?) {
    array ?: return
    if (array.isEmpty())
        return
    mergeSort(array, 0, array.size - 1)
}
fun mergeSort(array: IntArray, p: Int, q: Int) {
    if (p >= q)
        return
    var mid = p + (q - p) / 2
    mergeSort(array, p, mid)
    mergeSort(array, mid + 1, q)
    mergeArray(array, p, mid, q)
}

fun mergeArray(array: IntArray, p: Int, mid: Int, q: Int) {
    var tmpArr = IntArray(q - p + 1)
    var i = p
    var j = mid + 1
    var c = 0
    while (i <= mid && j <= q) {
        if (array[i] <= array[j]) {
            tmpArr[c++] = array[i++]
        } else {
            tmpArr[c++] = array[j++]
        }
    }
    while (i <= mid) {
        tmpArr[c++] = array[i++]
    }
    while (j <= q) {
        tmpArr[c++] = array[j++]
    }
    var k = p
    for (num in tmpArr) {
        array[k++] = num
    }
}

手写归并排序是很简单的，唯一复杂点的就在合并2个有序数组。

• 归并排序是稳定的
• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

2. 快排

快排是从数组中取出一个数据当做参照，经过一轮遍历比较之后，将所有比该数据小的数都在排它左边，将所有比该数据大的数都排在它右边。然后再将左右 2 部分的数据按同样的方式处理，依次递归下去，直至结束，这样就排好序了。

伪代码：

quickSort(array) {
    quickSort(0, array.size - 1)
}

quickSort(array, p, r) {
    //递归终止条件
    if(p >= r)
        return
    //找到分区点，经过 partition() 之后，array[q] 左边的都是比其小(或者相等)的数据，array[q] 右边都是比其大的数据
    q = partition(array, p, r)
    //一轮处理之后，再依次将分区点左右两部分数据排序
    quickSort(p, q - 1)
    quickSort(q + 1, r) 
}

代码如下（kotlin）：

fun quickSort(array: IntArray?) {
    array ?: return
    if (array.isEmpty())
        return
    quickSort(array, 0, array.size - 1)
}

private fun quickSort(array: IntArray, p: Int, q: Int) {
    if (p >= q)
        return
    //通过分区函数找到中点
    var mid = partition(array, p, q)
    //左边的继续递归排序
    quickSort(array, p, mid - 1)
    //右边的继续递归排序
    quickSort(array, mid + 1, q)
}

private fun swap(array: IntArray, i: Int, j: Int) {
    var tmp = array[i]
    array[i] = array[j]
    array[j] = tmp
}

接下来是快排的核心分区算法了，能手写出分区算法的代码，基本上快排就不用怕了。不同的书上讲快排的时候，可能讲的算法都不一样，我这里列出了3种分区函数的写法，理解了这3种写法，以后关于快排的各种算法都是信手拈来的事了。

2.1 快排分区函数写法一

第一种写法，取数组最右边的元素当做基准元素，定义 2 个指针从左往右遍历数组，具体步骤如下图所示：

快排分区1.png

从图中可以看到，定义了 2 个指针 i、j，array[j] 表示当前正在遍历的元素，array[i] 表示当前已遍历完的数组当中第一个大于基准元素的数据，也就是说 array[i] 左边的都是小于等于基准元素的数据。如果当前遍历元素 array[j] <= pivot，我们就交换 i、j 位置的元素，i 再向右移动，这样小的元素就被交换到左边了。

代码如下：

private fun partition(array: IntArray, p: Int, q: Int): Int {
    if (p == q) {
        return p
    }
    //取最后一个数作为参照
    var pivot = array[q]
    //指针 i 左边的都是 <= pivot 的数
    var i = p
    for (j in p until q) {
        //碰到 <= pivot 的数，则将其交换到左边来，之后指针 i 向右移动
        if (array[j] <= pivot) {
            swap(array, i, j)
            i++
        }
    }
    swap(array, i, q)
    return i
}

2.2 快排分区函数写法二

第一种写法的双指针都是从左向右移动，另外一种写法则是定义左右双指针 left、right，一个从左向右移动，一个从右向左移动，两个指针碰到则结束，最终将比较小的数交换到左边，较大的数交换到右边。

快排分区2.png

这个理解起来也很简单，left 指针先向右走，碰到大于基准元素的数时停下来，接着 right 指针向左走，碰到小于等于基准元素的数时停下来，这个时候我们可以断定：a[left] > pivot && a[right] <= pivot，仔细想想是不是这么回事呢。接着我们交换 left、right 指针所指向的值，交换必然有 a[left] <= pivot && a[right] > pivot，之后是不是又可以重复刚才的比较步骤了呢。最后左右指针相遇时，left 指针左边的都是 <= pivot 的元素了，我们最后再交换 left 指针与原来 pivot 指针所指向的元素就可以了。

private fun partition(array: IntArray, p: Int, q: Int): Int {
    if (p == q)
        return p
    var left = p
    var right = q - 1  //注意右指针为 q - 1，这里先将 pivot 排除在外
    var pivot = array[q]    //采用最右边元素为 pivot
    while (left <= right) {
        //注意这里循环条件是 left <= right，因为我们的 right 指针初始值不是数组右边界
        while (left <= right && array[left] <= pivot) {
            left++
        }
        while (left <= right && array[right] > pivot) {
            right--
        }
        if (left <= right) {
            //交换左右指针所指向的元素值
            swap(array, left++, right--)
        }
    }
    //交换 left 指针与 pivot 指针
    swap(array, left, q)
    return left
}

2.3 快排分区函数写法三

第3中写法基本上脱胎于第2种写法，前面2种写法里，会有很多的数据交换操作，这种写法则在这方面有一定的优化，可以看下具体执行过程：

快排分区3.png

在左指针右移停止时，左指针肯定指向的是一个 > pivot 值的元素，我们直接将数组右指针位置赋值为左指针指向的元素值。接着比较右指针，这个时候右指针位置的元素值肯定 > pivot，当右指针停止时，右指针指向的元素值肯定 <= pivot，我们再将数组左指针位置赋值为右指针指向的元素值。接着再重复上面的过程，到最后左右指针相遇时，我们将数组左指针位置赋值为 pivot 值。

private fun partition(array: IntArray, p: Int, q: Int): Int {
    if (p == q)
        return p
    var left = p
    var right = q  //注意这里 right 指针指向的是 q，与第2种写法有点区别
    var pivot = array[q]  
    while (left < right) {
        //这里循环条件是 <，而不是 <=，因为我们 right初始值为 q，即数组右边界
        //如果改成 left <= right，循环结束时 left 值可能为 right+1，如果此时 right = q 的话，这个时候就要处理数组越界的问题了
        while (left < right && array[left] <= pivot) {
            left++
        }
        array[right] = array[left]
        while (left < right && array[right] > pivot) {
            right--
        }
        array[left] = array[right]
    }
    //最后一定要记得将左指针位置赋值为 pivot
    array[left] = pivot
    return left
}

以上3种分区函数写法，个人觉得最好的是第三种，相对来说效率更高一点，但是理解起来还是稍微困难一点。

快排是不稳定的
最坏情况时间复杂度：例如数组 [1, 3, 5, 7, 9]，每次都选取最后一个为 pivot，那么就会退化为 O(n²)
平均情况时间复杂度：O(nlogn)
空间复杂度：O(1)

3. 找数组中第 k 大的元素

同样借用快排的分区思想，分区之后我们知道 pivot 在数组中的索引位置，我们只需要将 pivot 索引值与 k 进行比较，如果匹配成功则返回，否则我们只需在剩下的一半数组里再次查找。

fun findKElement(array: IntArray?, k: Int): Int? {
    array ?: return null
    if (k <= 0 || k > array.size)
        return null

    //找第 k 大的元素，就是找升序排列数组中索引为 [size - k] 的元素
    return findK(array, 0, array.size - 1, array.size - k)
}

fun findK(array: IntArray, p: Int, q: Int, index: Int): Int {
    if (p >= q) {
        return array[p]
    }
    var mid = partition(array, p, q)
    if (mid == index) {   //刚好命中
        return array[mid]
    } else if (mid > index) { //在左边找
        return findK(array, p, mid - 1, index)
    } else {    //在右边找
        return findK(array, mid + 1, q, index)
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

4. 算法比较