快速排序的优化

在快速排序中我们通常使用第一个元素作为分界点，但是当需要排序的序列基本是有序的时候，会导致一趟快速排序之后的两个序列长度极度不平衡，所以我们采用随机交换的方式来避免这个情况。

// 找出arr的[l,r]的标识点
func partition(arr []int, l int, r int) int {
    // 产生随机交换位置
    swapIndex := rand.Intn(r-l) + l
    arr[l], arr[swapIndex] = arr[swapIndex], arr[l]
    // 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
}

但是我们继续考虑另外一种情况，当序列的元素差别不太大时，例如十万个元素都在0-10之间，这样子会导致很多和作为分界点的元素大小相等的元素被分配到了一边，依然会导致两个序列长度差别很大。所以我们做如下改进。

// 改良后的算法，将等于v的值分散在两边
func partition2(arr []int, l int, r int) int {
    // 产生随机交换位置
    swapIndex := rand.Intn(r-l) + l
    arr[l], arr[swapIndex] = arr[swapIndex], arr[l]
    v := arr[l]
    // arr[l+1...i) <= v arr(j...r] >= v
    i, j := l+1, r
    for {
        for i <= r && arr[i] < v {
            i++
        }
        for j >= l+1 && arr[j] > v {
            j--
        }
        if i > j {
            break
        }
        arr[i], arr[j] = arr[j], arr[i]
        i++
        j--
    }
    arr[l], arr[j] = arr[j], arr[l]
    return j
}

针对上面的情况而言，等于v的元素数量十分多，但是我们依旧让它们继续参与了后序的排序，但是其实是不用的，等于v的元素在一趟快速排序之后它们的位置已经确定了，所以这就产生了下一种优化手段，叫做三路快速排序。

// QuickSort3Ways 三路快速排序
// 优化重复较多的数组
func QuickSort3Ways(arr []int) {
    quickSort3Ways(arr, 0, len(arr)-1)
}

func quickSort3Ways(arr []int, l int, r int) {
    if l >= r {
        return
    }
    p, q := partition3(arr, l, r)
    quickSort3Ways(arr, l, p)
    quickSort3Ways(arr, q, r)
}

func partition3(arr []int, l int, r int) (int, int) {
    // 产生随机交换位置
    swapIndex := rand.Intn(r-l) + l
    arr[l], arr[swapIndex] = arr[swapIndex], arr[l]
    v := arr[l]
    lt := l     // arr[l+1...lt] < v
    gt := r + 1 // arr[gt...r] > v
    i := l + 1  //arr[lt+1...i) == v
    for i < gt {
        if arr[i] < v {
            arr[lt+1], arr[i] = arr[i], arr[lt+1]
            i++
            lt++
        } else if arr[i] == v {
            i++
        } else {
            arr[gt-1], arr[i] = arr[i], arr[gt-1]
            gt--
        }
    }
    arr[lt], arr[l] = arr[l], arr[lt]
    return lt - 1, gt
}