这是快速排序还是合并排序？

Question

函数如下：

def sort(unsorted):
    less = []
    equal = []
    greater = []

    if len(unsorted) < 1:
        return unsorted

    pivot = unsorted[-1]

    for element in unsorted:
        if element < pivot:
            less.append(element)
        if element == pivot:
            equal.append(element)
        if element > pivot:
            greater.append(element)

    return sort(less)+equal+sort(greater)


unsorted = [7 ,2, 1, 8, 6, 3, 5, 4]
print sort(unsorted)

我很难将其定义为快速排序或归并排序。从概念上讲，我认为它符合快速排序的定义：它使用一个枢轴将元素分成比枢轴更小和更大的子集，然后递归地对它们进行排序。但另一方面，它让我想起了合并排序，因为它递归地将给定列表分解为更小的块，然后将它们重新组合在一起（尽管在 "pivot" 附近）。

这是快速排序还是归并排序？

Answer 1

合并排序总是在 len(list) / 2 的索引处划分列表。但是由于此代码根据 list[-1] 处的值划分 arr，因此这是快速排序

Answer 2

归并排序不需要在划分之前遍历整个数组进行比较。

Answer 3

Quicksort分区，MergeSort合并。

显然有一个分区过程（一侧是小键，另一侧是大键），并且显然没有合并（两个排序序列交织在一起）。

Answer 4

这显然是一个快速排序实现，而不是合并排序。想一想 Quicksort 是如何工作的：它在整个数组上选择一个主元并重新排列它，以便主元值左侧的所有内容都小于主元值，而右侧的所有内容都大于主元。因此，给定数组 [7 ,2, 1, 8, 6, 3, 5, 4] 和枢轴值 4，您将得到 [3,2,1,4,8,7,6,5].

接下来，它将子数组划分到主元的左侧和右侧。让我们使用 2 作为左侧站点的枢轴，使用 6 作为右侧站点的枢轴。先做左边，我们得到 [1,2,3,4,8,7,6,5]。然后递归地划分右边，你最终得到 [1,2,3,4,5,6,7,8].

快速排序是自上而下的。它对整个数组进行分区，然后对两个子数组进行分区，递归对每个子数组进行分区，直到子数组的长度为1。

归并排序是自下而上的。它首先遍历数组，"merging" 个相邻项。所以在第一遍之后，数组是[2 ,7, 1, 8, 3, 6, 4, 5]。接下来，它合并相邻的二元数组。第一个合并是子数组 [2, 7, 1, 8]，产生 [1,2,7,8]。第二次合并是 [3, 6, 4,5]，产生完整的数组 [1,2,7,8,3,4,5,6].

最后，它合并两个四元素子数组，生成排序数组。

您的代码显然是自上而下工作的：它对初始数组进行分区，然后递归地对左右子数组进行分区。不涉及合并，而是一个追加步骤，从排序的分区中重新组合子数组。

请注意，人们有时会谈论 "top-down" 或 "bottom-up" 归并排序。如果算法是迭代或递归编写的，这与实际排序工作的完成方式无关。无论实现如何，它总是从合并两个单元素子数组（相邻项）开始。

这是快速排序还是合并排序？

Is this Quick sort or Merge sort?

python

sorting

algorithm

mergesort

quicksort