排序算法-快速排序

快速排序算法的核心是在一个数组中，将第一个元素放置在中间位置使这个数组变为左边比这个元素都小，右边比这个组都大的一个数组。

代码实现这个过程如下

// 找出arr[l...r]的分界点j
// 使其分为arr[l,j] arr[j+1,r]两部分
func partition(arr []int, l, r) int {
    // j为当前找到的分界点
    // v为做为分界点的值
    j, v := l, arr[l]
    // i为当前正在考察的元素
    for i := l+1; i <= r; i++ {
        if arr[i] < v {
            arr[j+1], arr[i] = arr[i], arr[j+1]
            j++
        }
    }
    a[j], a[l] = a[l], a[j]
    return j
}

然后快速排序就是递归调用这个方法，将整个数组分为两部分，继续再分为四部分，直到每个数组只有一个元素就完成了排序
代码如下：

// QuickSort 快速排序
func QuickSort(arr []int) {
    quickSort(arr, 0, len(arr)-1)
}

// 对arr的[l,r]快速排序
func quickSort(arr []int, l int, r int) {
    if l >= r {
        return
    }
    p := partition(arr, l, r)
    quickSort(arr, l, p-1)
    quickSort(arr, p+1, r)
}

// 找出arr的[l,r]的标识点
func partition(arr []int, l int, r int) int {
    // arr[l+1:j] < v arr[j+1:i) > v
    // i为正在考察的元素
    v, j := arr[l], l
    for i := l + 1; i <= r; i++ {
        if arr[i] < v {
            arr[j+1], arr[i] = arr[i], arr[j+1]
            j++
        }
    }
    arr[j], arr[l] = arr[l], arr[j]
    return j
}