快速排序(golang)

发明者为东尼霍尔，大部分情况下排序效率很不错。

算法原理也比较容易理解：

第一步：

从当前数列中随机选定一个值作为基准（pivot），然后将数列中小于该基准的值放在基准的左边，将大于该基准的值放在基准的右边，与基准的值相等的可随意放左边或者右边都可。当前基准将数列分成两部分，这个操作过程称为分区（partition）操作。

第二步：

递归地将所有分区进行第一步所进行的操作，直到无法进行分区操作为止。

为了简化随机选取基准的操作，就固定的从分区的最左测选取即可。

大致的代码就是这样的

func QuickSort(data []int) {
    quickSort(data, 0, len(data) - 1)
}

// 递归的进行分区以及排序
func quickSort(data []int, leftIndex, rightIndex int) {
    // 分区操作获取基准值
    partitionIndex := partition(data, leftIndex, rightIndex)
    
    // 左侧分区进行排序
    QuickSort(leftIndex, partitionIndex - 1)
    
    // 右侧分区进行排序
    QuickSort(partitionIndex + 1, rightIndex)
}

// 分区操作
func partition(data []int, leftIndex, rightIndex int) int {
    // 随机设置基准，这里图方便，就选 leftIndex 作为基准
    pivot := leftIndex
    
    // 从基准右侧开始挨个与基准进行对比
    curr := leftIndex + 1
    for i := curr; i <= rightIndex; i++ {
        // 这里如果是想从小到大排列，就将小于基准的值放在左边，
        // 如果想按从大到小排列，就将大于基准的值放在左边
        // 默认按照从小到大的顺序排列
        // 挨个将数据移动到基准的左侧会涉及到较多的操作，
        // 这里就干脆先移动该移动的数据，最后再把基准移过去较为方便。
        if data[i] < data[pivot] {
            swap(data, i, curr)
            curr ++
        }
    }
    
    // 对比完后，将基准移动到分区位置即可。
    swap(data, curr - 1, pivot)
    return curr - 1
}

// 交换
func swap(data []int, i, j int) {
    data[i], data[j] = data[j], data[i]
}