快速排序的再探究、优化与稳定性

• 下载源代码 - 42.3 KB

引言

快速排序旨在成为一种非常快速的排序算法，具有最小的执行时间、小巧的代码占用空间以及对大量数据进行排序的能力。我之所以被促使重新审视快速排序这个已经被反复探讨过的主题，是因为一些提交和实现为了灵活性而牺牲了速度，为了“一刀切”的复杂性而牺牲了简洁性。在此，我将提出一些解决这些不足之处的建议，并附带代码示例和多种实现方式。

在本文中，我将简要介绍几个大家普遍关心的问题，并附带一些代码示例。这些问题包括：

• 我最初的、非常简短的快速排序算法，用 VB.NET 实现。我并不声称发明了该算法。此实现非常快速且无冗余。
• 一种“按引用”排序的实现，而不是“原地”排序。与原地排序数据结构相比，该实现速度明显更快。
• 另一种“稳定”的实现，即保留相同数值项的原始顺序。
• 最后，一个通用的实现，提供了一个类和方法，可以满足您许多通用的快速排序需求。

起初

快速排序算法是由 C. A. R. Hoare 于 1960 年开发的，当时他在一家小型英国科学计算机制造商 Elliott Brothers 工作（Wikipedia, 2008）。

快速排序的目标是在最短的时间内对大量数据进行排序。所采用的算法是一种递归算法，它将数据分成两个分区，“高”（High）和“低”（Low），这两个分区被排序到“高”分区中没有“低”分区的数据项，也没有“低”分区的数据项在“高”分区中。为此，算法选择一个任意的“枢轴”值（Pivot）来划分数据。该算法不一定必须实现为递归，但它会递归地对“低”和“高”分区分别执行相同的逻辑，从而最终对整个数据集进行排序。

该算法最简单的形式有一个主要的缺点，就是它不是一个稳定的排序。在交换的过程中，具有相同“值”的项的原始顺序可能会被打乱。这意味着原始快速排序作为交易排序引擎的价值是有限的。然而，稳定的排序问题可以通过牺牲机器周期来轻松克服。

原始快速排序原地算法

下面的代码片段是我最初的整数快速排序原地算法。我不声称发明了该算法。此代码片段没有注释，以说明其简短程度，并作为一种心智练习，让读者能够理解它是如何以及为何能够工作的。文档化的代码包含在下载文件中。结果是一个已排序的 awIntArr as Int32() 数组。

Public Shared Sub QuickSortInt(ByRef awIntArr As Int32(), _
       ByVal aLoIdx As Int32, ByVal aHiIdx As Int32)
  Dim xTmp As Int32
  Dim xLo As Int32 = aLoIdx
  Dim xHi As Int32 = aHiIdx
  Dim xPivot As Int32 = awIntArr((xLo + xHi) \ 2)
  Do Until xLo > xHi
    Do While awIntArr(xLo) < xPivot
      xLo += 1
    Loop
    Do While awIntArr(xHi) > xPivot
      xHi -= 1
    Loop
    If xLo <= xHi Then
      xTmp = awIntArr(xLo)
      awIntArr(xLo) = awIntArr(xHi)
      awIntArr(xHi) = xTmp
      xLo += 1
      xHi -= 1
    End If
  Loop
  If (xLo < aHiIdx) Then QuickSortInt(awIntArr, xLo, aHiIdx)
  If (xHi > aLoIdx) Then QuickSortInt(awIntArr, aLoIdx, xHi)
End Sub

注释

我承认，应随机选择枢轴值，以避免最坏情况下的 O(n²) 排序，而不是预期的 O(nLog₂n)。然而，我顽固地继续选择中间索引，以避免这种已排序的情况。

此代码在我的“苦力”机器上，对一百万个整数进行十次排序（请参阅示例），执行时间不到两秒。其中一个包含在示例中的“臃肿”的通用版本，大约需要 50% 的额外时间。

快速排序按引用排序

快速排序按引用排序不会移动任何原始未排序的数据，它只是排序一个引用这些数据的索引数组。下面的代码片段接受一个 BigRecord 数组，根据 BigRecord.CustNo 进行排序，并避免移动任何记录。相反，它移动 32 位整数引用，这对于 32 位机器来说轻而易举。结果是一个已排序的 awRefArr as Int32() 数组，它引用了未排序的原始数据 awBigRecArr as BigRecord() 数组。一个额外的附带好处是，当您对索引数组进行排序后，您也反向排序了数据——您只需反向读取结果索引数组即可。

Public Shared Sub QuickSortBigRecord _
      (ByRef awBigRecArr As BigRecord(), ByRef awRefArr As Int32(), _
       ByVal aStartIndex As Int32, ByVal aEndIndex As Int32)
  Dim xTmp As Int32                     ' Temp integer.
  Dim xLo As Int32 = aStartIndex        ' Working lower bound index.
  Dim xHi As Int32 = aEndIndex          ' Working upper bound index.
  Dim xPivot As Int32 = awRefArr((xLo + xHi) \ 2) ' Pivot reference.

  ' QuickSort.
  Do Until (xLo > xHi)

    ' Bump our Low Index while items are already in place.
    Do While awBigRecArr(awRefArr(xLo)).CustNo < awBigRecArr(xPivot).CustNo
      xLo += 1
    Loop

    ' Bump our High Index while items are already in place.
    Do While awBigRecArr(awRefArr(xHi)).CustNo > awBigRecArr(xPivot).CustNo
      xHi -= 1
    Loop

    ' Swap the low and high index items, if swappable. Bump indices.
    If xLo <= xHi Then
      xTmp = awRefArr(xLo)
      awRefArr(xLo) = awRefArr(xHi)
      awRefArr(xHi) = xTmp
      xLo += 1
      xHi -= 1
    End If

  Loop

  ' QuickSort the top partition.
  If xLo < aEndIndex Then
      QuickSortBigRecord(awBigRecArr, awRefArr, xLo, aEndIndex)
  ' QuickSort the bottom partition.
  If xHi > aStartIndex Then
      QuickSortBigRecord(awBigRecArr, awRefArr, aStartIndex, xHi)

End Sub

注释

我通常使用引用快速排序。

稳定快速排序

在排序数据记录时，当项目在比较时返回相同的值时，保留数据记录的顺序通常很有用。向同一客户重复出售同一产品的交易，对于某些应用程序，可能需要“稳定”地按交易日期顺序保留。快速排序在其最高效的形式（“原始快速排序”）中并不这样做。对“快速排序按引用排序”（上面）代码的以下更改，通过很少的代码实现了这一点，而不会给处理过程增加过多的机器周期。

    ' Bump our Low Index while items are already in place.
    Do While (awBigRecArr(awRefArr(xLo)) < awBigRecArr(xPivot)) _
    OrElse ((awBigRecArr(awRefArr(xLo)) = awBigRecArr(xPivot)) _
             AndAlso (awRefArr(xLo) < xPivot))
      xLo += 1
    Loop

    ' Bump our High Index while items are already in place.
    Do While (awBigRecArr(awRefArr(xHi)) > awBigRecArr(xPivot)) _
    OrElse ((awBigRecArr(awRefArr(xHi)) = awBigRecArr(xPivot)) _
             AndAlso (awRefArr(xHi) > xPivot))
      xHi -= 1
    Loop

注释

我通常很少需要稳定快速排序；但是，它只消耗了少量额外的机器周期。

通用快速排序

我在 The Code Project 和其他地方看到过无数用于泛化快速排序以满足各种情况的示例。这些努力在许多情况下导致了臃肿、混乱且效率低下的代码。我的尝试在这里只是使用一个必须继承的基类，该基类实现了 IComparable。将您特定的数据类型添加到派生类，实现 IComparable.CompareTo，然后调用通用快速排序，这是相当简单的。

基类

''' <summary>
''' Base MustInherit class implementing
''' IComparable(Of clsBaseIComparable).
''' </summary>
''' <remarks></remarks>
Public MustInherit Class clsBaseIComparable
  Implements IComparable(Of clsBaseIComparable)

  Public MustOverride Function CompareTo(ByVal other As clsBaseIComparable) _
        As Integer Implements System.IComparable(Of clsBaseIComparable).CompareTo

End Class

一个派生类

''' <summary>
''' Employee data, inherited from clsBaseIComparable,
''' implementing IComparable.
''' </summary>
''' <remarks>
''' Devised for testing general QuickSort methods.
''' </remarks>
Public Class clsEmployee
  Inherits clsBaseIComparable

  Friend fFirstName As String
  Friend fLastName As String
  Friend fRole As String
  Friend fSalary as Int32

  Public Sub New _
        (ByVal aFirstName As String _
        , ByVal aLastName As String _
        , ByVal aRole As String _
        , ByVal aSalary as Int32)
    Me.fFirstName = aFirstName
    Me.fLastName = aLastName
    Me.fRole = aRole
    Me.fSalary = aSalary
  End Sub

  ''' <summary>
  ''' Implementing IComparable.CompareTo,
  ''' sorting Name within Salary within Role.
  ''' </summary>
  ''' <param name="other"> Compared with clsEmployee. </param>
  ''' <returns>
  ''' Negative 1 if Me less-than Other.
  ''' Positive 1 if Me greater-than Other.
  ''' Zero if Me equal-to Other.
  ''' </returns>
  ''' <remarks>
  ''' Devised for testing general QuickSort methods.
  ''' DirectCase is used because it is a compile-time cast,
  ''' i.e. does not incur run-time overhead. This is a
  ''' more complex than usual comparison.
  ''' </remarks>
  Public Overrides Function CompareTo(ByVal other As clsBaseIComparable) As Integer
    If Me.fRole < DirectCast(other, clsEmployee).fRole Then
      Return -1
    ElseIf Me.fRole > DirectCast(other, clsEmployee).fRole Then
      Return +1
    ElseIf Me.fSalary < DirectCast(other, clsEmployee).fSalary Then
      Return -1
    ElseIf Me.fSalary > DirectCast(other, clsEmployee).fSalary Then
      Return +1
    ElseIf Me.fLastName < DirectCast(other, clsEmployee).fLastName Then
      Return -1
    ElseIf Me.fLastName > DirectCast(other, clsEmployee).fLastName Then
      Return +1
    ElseIf Me.fFirstName < DirectCast(other, clsEmployee).fFirstName Then
      Return -1
    ElseIf Me.fFirstName > DirectCast(other, clsEmployee).fFirstName Then
      Return +1
    Else
      Return 0
    End If
  End Function

End Class

到目前为止还不算太难。现在，关于快速排序。添加到“稳定快速排序”实现中的只是一个 xComp 变量，以避免多次调用 CompareTo，以及使用 CompareTo 代替大于和小于。

Public Shared Sub QuickSortEmployee _
      (ByRef awEmpArr As clsEmployee(), ByRef awRefArr As Int32(), _
       ByVal aStartIndex As Int32, ByVal aEndIndex As Int32)
  Dim xTmp As Int32                     ' Temp integer.
  Dim xLo As Int32 = aStartIndex        ' Working lower bound index.
  Dim xHi As Int32 = aEndIndex          ' Working upper bound index.
  Dim xPivot As Int32 = awRefArr((xLo + xHi) \ 2) ' Pivot value.
  Dim xComp As Int32                    ' CompareTo value.

  ' QuickSort.
  Do Until (xLo > xHi)

    ' Bump our Low Index while items are already in place.
    ' Keep a stable order.
    xComp = awEmpArr(awRefArr(xLo)).CompareTo(awEmpArr(xPivot))
    Do While  (xComp < 0) OrElse ((xComp = 0) AndAlso (awRefArr(xLo) < xPivot))
      xLo += 1
      xComp = awEmpArr(awRefArr(xLo)).CompareTo(awEmpArr(xPivot))
    Loop

    ' Bump our High Index while items are already in place.
    ' Keep a stable order.
    xComp = awEmpArr(awRefArr(xHi)).CompareTo(awEmpArr(xPivot))
    Do While (xComp > 0) OrElse ((xComp = 0) AndAlso (awRefArr(xHi) > xPivot))
      xHi -= 1
      xComp = awEmpArr(awRefArr(xHi)).CompareTo(awEmpArr(xPivot))
    Loop

    ' Swap the low and high index items, if swappable. Bump indices.
    If xLo <= xHi Then
      xTmp = awRefArr(xLo)
      awRefArr(xLo) = awRefArr(xHi)
      awRefArr(xHi) = xTmp
      xLo += 1
      xHi -= 1
    End If

  Loop

  ' QuickSort the top partition.
  If xLo < aEndIndex Then QuickSortEmployee(awEmpArr, awRefArr, xLo, aEndIndex)
  ' QuickSort the bottom partition.
  If xHi > aStartIndex Then QuickSortEmployee(awEmpArr, awRefArr, aStartIndex, xHi)

End Sub

注释

通用快速排序的执行时间相当长。我的示例中包含的那个（在我的机器上）比“原始快速排序”慢了五倍多，原因可能有两个：

1. 它调用了一个外部方法；
2. 它是一个更复杂的比较。

这些缺点常常促使我转而实现多个定制的快速排序，这些排序通常只需要少量额外的编码，并且执行速度快很多倍。

摘要

显然，快速排序是一种简单、简洁的数据排序方式。其代码占用空间如此之小，以至于在考虑过度泛化它之前，应考虑为不同的“排序”复制快速排序代码。已经证明，它可以是稳定的排序，也可以是易于泛化的排序，可以直接原地排序数据，也可以间接按引用排序。无冗余的快速排序基本上（双关语）是一种优雅的逻辑——祝贺 C. A. R. Hoare (1960)。

历史

• 2008-01-10 - 原始文章。