我尝试制作的这个版本的选择排序不能正常工作，但它对大型数组却出人意料地工作

Question

我昨天在做选择排序。我想知道每次迭代时是否可以将 min 和 max 值替换为未排序数组的开头和结尾。我只是编程的初学者，所以很明显这行不通。然而，令人惊讶的是，下面的代码确实对一个更大的数组 (~ 30k - 40k) 进行了排序。我通过从 rand()%2000 生成随机值进行实验，该函数在 30 次实验中成功对数组进行了 28 次排序。

但它无法对 {4,2,3} 这样简单的内容进行排序我认为某处存在错误，我无法弄清楚所以我来了。

我也很好奇它能成功地对如此大的数组进行排序。怎么样？

int *zigzag_sort(int arr[])
{
    // loop through array
    // find min and max
    // replace min at begining and max at end
    // keep doing until sorted

    int f_idx = 0, l_idx = n-1;
    int min_pos, max_pos;
    
    while( f_idx < l_idx ) {
        min_pos = f_idx;
        max_pos = l_idx;
        
        for(int i = f_idx+1; i <= l_idx; i++) 
        {
            if(arr[i] < arr[min_pos])
                min_pos = i;
            else if(arr[i] > arr[max_pos])
                max_pos = i;
        }           
        swap(&arr[f_idx], &arr[min_pos]);
        swap(&arr[l_idx], &arr[max_pos]);

        f_idx++; 
        l_idx--;
        }
        
    return arr;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Answer 1

Why doesn't it work for { 4, 2, 3 }?

    ... // f_idx = 0; l_idx = 2; min_pos = 1; max_pos = 0;
    swap(&arr[f_idx], &arr[min_pos]); // swap(&arr[0], &arr[1]) ==> { 2, 4, 3 }
    // ===> max_pos is "wrong" now <===
    swap(&arr[l_idx], &arr[max_pos]); // swap(&arr[2], &arr[0]) ==> { 3, 4, 2 }

Answer 2

你的掉期并没有你想象的那么简单，你进入内循环迭代的位置起点有一个洞。

首先，在完成段枚举并找到段 min-index 和 max-index 位置后，有些情况必须考虑在内。它们都处理你从哪里读取数据，以及你试图将数据写入哪里。可能存在部分重叠，或者在一种情况下完全重叠。

每次内部迭代后，可能会出现几个条件之一...

(min_pos == l_idx) && (max_pos == f_idx)。换句话说，最小值和最大值都在对方想要的地方。如果是这种情况，则需要（彼此）进行一次交换，并且您已完成该迭代。
(min_pos == l_idx) 或 (max_pos == f_idx) 之一是正确的，但不是两者都正确。即将发生的两次互换的顺序很重要，具体取决于哪些条件为真。简而言之，不要将某些东西交换到即将被交换的插槽中再次与第二次交换。例如：如果最大值位于低目标位置，则需要将其 out 交换到最大目标位置 before 交换最小值到低目标位置。不然东西放回家就会脱臼
以上都不是，在这种情况下仍然需要两次交换，但顺序无关紧要。

当您在外循环中将迭代 window 压缩得越来越深时，上述 (1) 和 (2) 中的特殊情况的概率会显着增加迭代。对于随机排序，迟早会发生。

其次，min_pos 和 max_pos 起点都应该是相同段中的位置，f_idx。它可能看起来并不重要，但它确实如此，因为内部循环开始了 f_idx+1。这意味着如果迭代的最大值最初是 f_idx 你从来没有考虑过它，也不会发现它，等等

固定例程如下，并在适当的地方加上注释。

int *zigzag_sort(int arr[], int n)
{
    int f_idx = 0, l_idx = n - 1;

    while (f_idx < l_idx)
    {
        // both should start at the same location
        int min_pos = f_idx;
        int max_pos = f_idx;

        for (int i = f_idx + 1; i <= l_idx; i++)
        {
            if (arr[i] < arr[min_pos])
                min_pos = i;
            else if (arr[i] > arr[max_pos])
                max_pos = i;
        }

        if (max_pos == f_idx)
        {
            if (min_pos == l_idx)
            {
                // swap each other
                swap(&arr[max_pos], &arr[min_pos]);
            }
            else
            {   // swap the max out before overwritine with min
                swap(&arr[l_idx], &arr[max_pos]);
                swap(&arr[f_idx], &arr[min_pos]);
            }
        }
        else
        {   // also handle the case of l_idx == min_pos
            swap(&arr[f_idx], &arr[min_pos]);
            swap(&arr[l_idx], &arr[max_pos]);
        }

        f_idx++;
        l_idx--;
    }

    return arr;
}

我尝试制作的这个版本的选择排序不能正常工作，但它对大型数组却出人意料地工作

This version of selection sort I tried to make doesnot work properly, but it works surprisingly for larger arrays

arrays

c

sorting

selection-sort