时间戳

首页 > 解决方案 > 为什么没有对中间元素进行排序？

c - 为什么没有对中间元素进行排序？

问题描述

我正在实现一个排序算法是为了好玩，但由于我不知道的原因，到目前为止我已经实现的并没有对中间进行排序。下面是算法的步骤：

  1. 获取最小值和最大值的索引
  2. 将最小值移动到最小索引，将最大值移动到最大索引
  3. 增加最小索引并减少最大索引
  4. 从 1 开始重复。同时最小索引小于最大索引

我知道这不是最有效的排序算法，但这只是为了好玩。这是代码

#define ui64 uint64_t

void print(ui64* array, ui64 ArraySize);

ui64 random(void) 
{
  ui64 r = 0;
  for(int i = 0; i < 64; i++) r = r*2 + rand()%2;
  return r;
}

void generate(ui64* array, ui64 ArraySize);

Pair getMinMaxIndices(ui64* array, ui64 minIndex, ui64 maxIndex)
{
    Pair minmax, minmaxIndices;
    
    if(maxIndex == 0)
    {
        minmax.max = array[0];
        minmax.min = array[0];
        
        minmaxIndices.max = 0;
        minmaxIndices.min = 0;
        
        return minmaxIndices;
    }
    
    if(array[minIndex] > array[minIndex + 1])
    {
        minmax.max = array[minIndex];
        minmax.min = array[minIndex + 1];
        
        minmaxIndices.max = minIndex;
        minmaxIndices.min = minIndex + 1;
    }
    else
    {
        minmax.max = array[minIndex + 1];
        minmax.min = array[minIndex];
        
        minmaxIndices.max = minIndex + 1;
        minmaxIndices.min = minIndex;
    }

    for(int i = minIndex + 2; i < maxIndex + 1; i++)
    {
        if(array[i] > minmax.max)
        {
            minmax.max = array[i];
            minmaxIndices.max = i;
        }

        else if(array[i] < minmax.min)
        {
            minmax.min = array[i];
            minmaxIndices.min = i;
        }
    }

    return minmaxIndices;
}

void swap(ui64* array, ui64 index1, ui64 index2);

void closingCurtainsSort(ui64* array, ui64 ArraySize)
{
    Pair minmaxIndices, indexLimits;
    
    indexLimits.min = 0;
    indexLimits.max = ArraySize - 1;
    
    while(indexLimits.min < indexLimits.max)
    {
        minmaxIndices = getMinMaxIndices(array, indexLimits.min, indexLimits.max);
        
        swap(array, minmaxIndices.min, indexLimits.min);
        swap(array, minmaxIndices.max, indexLimits.max);
        
        indexLimits.min++;
        indexLimits.max--;
    }
}

这是程序为这个硬编码数组生成的一步一步：array2[10] = {0,2,4,6,8,1,3,5,7,9}

Array2
0
2
4
6
8
1
3
5
7
9
Current minimum value -> array[0]: 0
Current maximum value -> array[9]: 9
Current minimum index -> 0
Current maximum index -> 9

Loop 1
0
2
4
6
8
1
3
5
7
9
Current minimum value -> array[0]: 0
Current maximum value -> array[9]: 9
Current minimum index -> 1
Current maximum index -> 8

Loop 2
0
1
4
6
7
2
3
5
8
9
Current minimum value -> array[5]: 2
Current maximum value -> array[4]: 7
Current minimum index -> 2
Current maximum index -> 7

Loop 3
0
1
2
6
5
4
3
7
8
9
Current minimum value -> array[5]: 4
Current maximum value -> array[4]: 5
Current minimum index -> 3
Current maximum index -> 6

Loop 4
0
1
2
6
5
4
3
7
8
9
Current minimum value -> array[6]: 3
Current maximum value -> array[3]: 6
Current minimum index -> 4
Current maximum index -> 5

Loop 5
0
1
2
6
5
4
3
7
8
9
Current minimum value -> array[5]: 4
Current maximum value -> array[4]: 5
Current minimum index -> 5
Current maximum index -> 4

编辑：删除以下内容：

声明了具有明显实现而不是定义的函数

标签： csorting

解决方案

您的代码可以（并且确实）错误地进行双重交换。

示例：经过三次迭代后，您的序列将生成如下：

Loop 1 : 0 2 4 6 8 1 3 5 7 9 
Loop 2 : 0 1 4 6 7 2 3 5 8 9 
Loop 3 : 0 1 2 6 5 4 3 7 8 9

现在我们移动到分区 [3,6]。在这个分区中，我们发现“minval”索引为 6，“maxval”索引为 3。即极值需要相互交换，因为每个值都位于另一个目标位置。但是，您的算法会这样做：

swap(array, minmaxIndices.min, indexLimits.min);
swap(array, minmaxIndices.max, indexLimits.max);

因此，您将它们交换到正确的位置，然后将它们交换回来。

当着陆点的目标（当前分区的外边缘）实际上是被交换为相反极值的数据源时，您应该只交换一次。

swap(array, minmaxIndices.min, indexLimits.min);
if (indexLimits.min != minmaxIndices.max)
    swap(array, minmaxIndices.max, indexLimits.max);

推荐阅读