当数组具有两个相同值的实例时，Quicksort 算法中的无限循环

Question

我一直在尝试在 Visual Basic 中编写一个快速排序函数作为练习。这很简单，而且对于没有出现两次相同数字的数组也能很好地工作。但一旦发生这种情况，将左指针向右指针推进的循环的第二次迭代就会陷入无限循环，我终究无法弄清楚为什么会发生这种情况。

如果有人知道它卡住的原因，我将不胜感激。这是代码：

Public Function Partition(ByVal a As Integer(), ByVal left As Integer, ByVal right As Integer)

    Dim temp As Integer

    Do While left <> right

        Do While (a(left) < a(right)) And (left <> right)
            left = left + 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        Do While (a(left) < a(right)) And (left <> right)
            right = right - 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

    Loop

    Return left
End Function

Sub QuickSort(ByVal a As Integer(), ByVal left As Integer, ByVal right As 
Integer)

    If left < right Then
        Dim position As Integer = Partition(a, left, right)
        QuickSort(a, left, position - 1)
        QuickSort(a, position + 1, right)
    End If

End Sub

Answer 1

只要 a(left) 和 a(right) 相同，就会发生这种情况。在你交换它们之后，它们仍然是一样的，所以你一次又一次地交换。
为避免这种情况，您需要

1.Replace 下面的循环：

Do While (a(left) < a(right)) And (left <> right)
            left = left + 1                
        Loop

有了这个：

Do While (a(left) <= a(right)) And (left <> right)
            left = left + 1                
        Loop

为了让元素等于枢轴，放在它的左边

2.Add 第二次循环后的一步（但仅适用于迭代器未指向同一元素的情况，这意味着分区结束）：

  Do While (a(left) < a(right)) And (left <> right)
            right = right - 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        If left <> right
           left = left + 1
        End if

所以修改后的函数如下所示：

Public Function Partition(ByVal a As Integer(), ByVal left As Integer, ByVal right As Integer)

    Dim temp As Integer

    Do While left <> right

        Do While (a(left) <= a(right)) And (left <> right)
            left = left + 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        Do While (a(left) < a(right)) And (left <> right)
            right = right - 1                
        Loop

        temp = a(left)
        a(left) = a(right)
        a(right) = temp

        If left <> right
           left = left + 1
        End if
    Loop

    Return left
End Function

PS。它可以进一步优化以避免交换相等的元素或交换元素与自身，我会留给你

当数组具有两个相同值的实例时，Quicksort 算法中的无限循环

Endless loop in Quicksort algorithm when array has two instances of the same value

vb.net

arrays

sorting

quicksort

infinite-loop