求解排序问题，这是哪种分治算法？

有志者，事竟成！如果你在学习Golang，那么本文《求解排序问题，这是哪种分治算法？》，就很适合你！文章讲解的知识点主要包括，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

这里是第一次发帖。

我正在用 go-lang 练习一些排序算法。我尝试编写一个快速排序算法。代码如下。

func DivideAndConquerSort(newArr []int,descending bool) []int {

    if len(newArr) == 1 || len(newArr) == 0{
        return newArr
    }
    pivotIndex := 0
    leftPivot := []int{}
    rightPivot := []int{}
    centerPivot := []int{}
    for idx1 := 0; idx1<len(newArr); idx1++{
        if newArr[pivotIndex] == newArr[idx1]{
            centerPivot = append(centerPivot,newArr[idx1])
            continue
        }
        
        if descending {
            if newArr[pivotIndex] < newArr[idx1]{
                leftPivot = append(leftPivot,newArr[idx1])
                continue
            }
            if newArr[pivotIndex] > newArr[idx1]{
                rightPivot = append(rightPivot,newArr[idx1])
                continue
            }
        }
        if newArr[pivotIndex] > newArr[idx1]{
            leftPivot = append(leftPivot,newArr[idx1])
            continue
        }
        if newArr[pivotIndex] < newArr[idx1]{
            rightPivot = append(rightPivot,newArr[idx1])
            continue
        }
    }
    leftPivot = DivideAndConquerSort(leftPivot,descending)
    leftPivot = append(leftPivot,centerPivot...)
    
    rightPivot = DivideAndConquerSort(rightPivot,descending)
    
    newArr = append(leftPivot,rightPivot...)
    
    return newArr
}

但是我看的越多。它看起来更像是合并排序..？我现在还不太确定。

我引用了pediaa.com 的算法定义和流程。

本质上，我认为这是一个快速排序，因为我正在使用pivot并比较它们。但奇怪的是，我认为代码没有进行任何交换（快速排序应该做的事情）。考虑到这一点，我倾向于说这是一个合并排序。但同样，我不确定，该网站没有声明合并使用枢轴。

你们能告诉我我写的是什么样的排序算法吗？另外，我愿意接受对我编写代码的方式的批评。

正确答案

该算法本质上是快速排序的一个版本。它选择一个主元，将输入数组分为三组项目（小于、等于和大于主元的项），然后递归地对小于和大于主元的项进行排序。

你是对的，算法没有进行任何交换。与就地修改数组的传统快速排序不同，该算法创建新数组来保存小于、等于和大于主元的元素。这使得它的效率低于标准快速排序实现。但从本质上来说，这确实是一种快速排序。

本篇关于《求解排序问题，这是哪种分治算法？》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！