计数排序算法，无法完美排序

本文关键字：排序 完美 算法 | 更新日期: 2023-09-27 17:51:22

我一直在尝试实现Count Sort Algorithm。

每次我运行算法它给我错误的答案在索引0和1

已经连续20个小时了，我无法追踪我做错了什么…

Generated_Array 17  88  14  91  151 50  95  175 92  49  116 67  111 195 37  63  144 50  65  90  
Sorted_Array    0   14  17  37  49  50  50  63  65  67  88  90  91  92  95  111 116 144 151 175
Generated_Array 8   109 33  37  196 156 158 142 52  179 152 182 171 27  54  75  139 193 25  190 
Sorted_Array    0   8   25  27  33  37  52  54  75  109 139 142 152 156 158 171 179 182 190 193
Generated_Array 51  24  132 150 73  198 111 55  64  145 15  179 117 6   16  120 155 45  52  108 
Sorted_Array    0   198 15  16  24  45  51  52  55  64  73  108 111 117 120 132 145 150 155 179 
Generated_Array 15  119 162 199 104 104 71  69  40  141 50  119 32  6   155 75  150 140 164 6   
Sorted_Array    0   199 6   15  32  40  50  69  71  75  104 104 119 119 140 141 150 155 162 164 

Generated_Array 22  150 91  145 164 151 145 118 123 105 56  78  185 57  114 128 152 20  124 2   
Sorted_Array    0   185 20  22  56  57  78  91  105 114 118 123 124 128 145 145 150 151 152 164 

Generated_Array 132 191 44  185 116 186 107 195 104 55  107 48  45  109 38  76  45  143 31  58  
Sorted_Array    0   195 38  44  45  45  48  55  58  76  104 107 107 109 116 132 143 185 186 191 
Generated_Array 104 139 137 47  22  180 161 170 39  165 12  16  49  177 11  83  30  34  29  61  
Sorted_Array    0   180 12  16  22  29  30  34  39  47  49  61  83  104 137 139 161 165 170 177

下面是我使用的算法:

int[] Counting_sort(int[] Array, int Max)
{
    int No_Of_Elements = Array.Length;
    int[] Sorted_Array = new int[Array.Length];
    int[] C = new int[Max+1];
    for (int i = 0; i < Max; i++)
    {
        C[i] = 0; 
    }
    for (int j = 0; j <No_Of_Elements; j++)
    {
        C[Array[j]] = C[Array[j]] + 1;
    }
    for (int i = 1; i <Max; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = No_Of_Elements-1; j >= 0; j--)
    {
        Sorted_Array[C[Array[j]]] = Array[j];
        C[Array[j]] = C[Array[j]] - 1;
    }
    return Sorted_Array;
}

计数排序算法，无法完美排序

Try Following

I<=Max in 3rd LoopSorted_Array[C[Array[j]]-1] = Array[j] In 4th Loop

int[] Counting_sort(int[] Array, int Max)
{
    int No_Of_Elements = Array.Length;
    int[] Sorted_Array = new int[Array.Length];
    int[] C = new int[Max+1];
    for (int i = 0; i < Max; i++)
    {
        C[i] = 0; 
    }
    for (int j = 0; j <No_Of_Elements; j++)
    {
        C[Array[j]] = C[Array[j]] + 1;
    }
    for (int i = 1; i <=Max; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = No_Of_Elements-1; j >= 0; j--)
    {
        Sorted_Array[C[Array[j]]-1] = Array[j];
        C[Array[j]] = C[Array[j]] - 1;
    }
    return Sorted_Array;
}

假设您想对包含10个元素的数组进行排序:

int[] A = {5, 7, 6, 5, 3, 8, 8, 4, 3, 2};

那么你的计数数组，C是:

C == {0, 0, 1, 3, 4, 6, 7, 8, 10, 10, 10};
有两件事需要注意:你使用这个数组作为排序数组的索引，但是10不是一个有效的索引;该数组不包含下标，但包含小于或等于i的元素数。并且0和1项不会出现，所以在访问数组时必须注意这一点。

与从0开始计数循环并使计数数组C的上界为实际大小Max + 1一起，您应该像这样修复最后一个循环:

for (int j = No_Of_Elements; j--;)
{
    if (C[Array[j]] > 0) {
        Sorted_Array[C[Array[j]] - 1] = Array[j];
        C[Array[j]]--;
    }
}
相关文章：