算法:快速排序

算法 大约 1853 字

算法演进

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

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

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

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)
    }
}
阅读 36 · 发布于 2021-02-09

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批