算法：快速排序

算法演进

以数组中间索引的元素为中轴值，分组左右两边两个数组。

左边数组遍历找到一个大于中轴值的数，右边数组遍历找到一个小于中轴值的数，进行交换，遍历完成，左边数组都是小于中轴值的数，右边数组都是大于中轴值的数，但左右两边的数组内部还不是有序的。

左右两组分别以取中轴值方式进行递归，完成排序。

func QuickSortEvolutionDemo() {
    arr := []int{-9, 78, 0, 23, -567, 70}

    QuickSortEvolution(arr, 0, len(arr)-1)

    // 左边排序
    QuickSortEvolution(arr, 0, (0+len(arr)-1)/2-1)

    // 右边排序
    QuickSortEvolution(arr, (0+len(arr)-1)/2+1, len(arr)-1)
}

func QuickSortEvolution(arr []int, left, right int) {
    // 中轴值
    var pivot = arr[(left+right)/2]
    var l = left  // 数组第0位
    var r = right // 数组最后一位

    for l < r {
        for arr[l] < pivot { // 找到中轴左边比中轴值大的，暂停循环
            l++ // 往中轴靠近，右移一位
        }

        for arr[r] > pivot { // 找到中轴右边比中轴值小的，暂停循环
            r-- // 往中轴靠近，左移一位
        }

        if l >= r {
            break
        }

        // 左边的值和右边的值交换
        temp := arr[l]
        arr[l] = arr[r]
        arr[r] = temp
    }
}

快速排序代码

func main() {
    arr := []int{-9, 78, 0, 23, -567, 70}

    QuickSort(arr, 0, len(arr)-1)

    log.Println(arr)
}


func QuickSort(arr []int, left, right int) {
    // 中轴值
    var pivot = arr[(left+right)/2]
    var l = left  // 数组第0位
    var r = right // 数组最后一位

    for l < r {
        for arr[l] < pivot { // 找到中轴左边比中轴值大的，暂停循环
            l++ // 往中轴靠近，右移一位
        }

        for arr[r] > pivot { // 找到中轴右边比中轴值小的，暂停循环
            r-- // 往中轴靠近，左移一位
        }

        if l >= r {
            break
        }

        // 左边的值和右边的值交换
        temp := arr[l]
        arr[l] = arr[r]
        arr[r] = temp

        if arr[l] == pivot {
            r--
        }

        if arr[r] == pivot {
            l++
        }
    }

    if l == r {
        l++
        r--
    }

    // 左边
    if left < r {
        QuickSort(arr, left, r)
    }

    // 右边
    if right > l {
        QuickSort(arr, l, right)
    }
}