时间戳

首页 > 解决方案 > 为什么我的快速排序不能正常工作？

arrays - 为什么我的快速排序不能正常工作？

问题描述

我正在以多种方式对一组对象进行排序。这些对象是针对区域的，我将对这些区域的数据进行分类（更具体地说，人口、水污染物浓度，以及该区域是否违反了法律或基于健康的用水限制。我的分类结果几乎是准确的，它们只有 5满分 100 分。

t是一个字符串，其中包含如何对区域进行排序的键码。例如，如果t<-- "p"，那么它将测试两个区域之间的人口并返回真或假。

预先，

        statusL <-- True  statusH <-- True   high <-- length

代码：

Function partition(a() As Area, High As Long, Low As Long, t As String, progress As Boolean)
    Dim pivot As Area
    Dim i As Long, j As Long
    Set pivot = a(High)
    i = Low - 1
    j = Low
    For j = Low To High - 1
        If testAreas(a(j), pivot, t) Then
            i = i + 1
            Call swap(a(), i, j)
        End If
    Next j
    Call swap(a(), i + 1, High)
    If progress Then
        partition = i - 1
    Else
        partition = i + 1
    End If
End Function

Function QuickSort(a() As Area, High As Long, Low As Long, t As String, statusH As Boolean, statusL As Boolean, rounds As Long, oldPivot As Long, progress As Boolean)
    Dim pivot As Long
    If Low < High Then
        pivot = partition(a(), High, Low, t, progress)
        If rounds = 0 Then
            oldPivot = pivot
        End If
        rounds = rounds + 1
        If statusH = True Then
            If pivot >= High - 1 Then
                statusH = False
            End If
            Call QuickSort(a(), High, pivot - 1, t, statusH, statusL, rounds, oldPivot, progress)
        End If
        ''''''''''''''''
        If progress = False Then
            pivot = oldPivot
        End If
        progress = True
        ''''''''''''''''
        If statusL = True Then
            If pivot <= 1 Then
                statusL = False
            End If
            Call QuickSort(a(), pivot + 1, 0, t, statusH, statusL, rounds, oldPivot, progress)
        End If
    End If
End Function

Function swap(a() As Area, index1 As Long, index2 As Long)
    Dim x As Area
    Set x = a(index1)
    Set a(index1) = a(index2)
    Set a(index2) = x
End Function


Function testAreas(a As Area, b As Area, t As String)
    testAreas = False
    If t = "m" Then
        If a.max <= b.max Then
            testAreas = True
        End If
    End If
    If t = "p" Then
        Dim p1 As Double, p2 As Double
        p1 = a.pop
        p2 = b.pop
        If p1 <= p2 Then
            testAreas = True
        End If
    End If
    If t = "l" Then
        Dim L1 As Long, L2 As Long
        L1 = a.ll
        L2 = b.ll
        If L1 <= L2 Then
            testAreas = True
        End If
    End If
    If t = "h" Then
        Dim h1 As Long, h2 As Long
        h1 = a.hbl
        h2 = b.hbl
        If h1 <= h2 Then
            testAreas = True
        End If
    End If
    If t = "s" Then
        If a.state <= b.state Then
            testAreas = True
        End If
    End If
End Function

我得到的订单如下所示：

221351,30948,20602,12300,11702,8980,2342,2300,1395,1475,1005,993,852,775,935,904,975,654,650,600,794,650,740,493,795

...随着时间的推移，它变得越来越不准确，然后接近尾声变得更加准确。

标签： arraysvbaquicksort

解决方案

我不明白对progress参数的需求。对于快速排序，如果枢轴交换正在使用i+1，那么分区函数应该返回i+1。为避免堆栈溢出，请对较小的部分使用递归，然后对较大的部分进行循环。使用 Lomuto 分区方案的示例 C++ 代码：

void QuickSort(uint64_t a[], int lo, int hi)
{
    while (lo < hi){
        uint64_t p = a[hi];
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if(i - lo <= hi - i){
            QuickSort(a, lo, i-1);
            lo = i+1;
        } else {
            QuickSort(a, i+1, hi);
            hi = i-1;
        }
    }
}

推荐阅读