过去 7 到 8 个月以来，我一直热衷于编程，每当我想对数组或结构进行排序时，我通常都会使用选择排序。所以我有了想法并实现了它。选择排序在每个循环中找到最大值或最小值并将其放置在边界之一(取决于最大值或最小值)并使其超出范围。所以我想为什么不在每个循环中找到 max 和 min 并将它们移动到边界(min-left 和 max-right)并将范围从两侧减少值 1。我猜它的时间复杂度是以前的一半。这是代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int *a;
    int n;
    scanf("%d", &n);
    a = malloc (n * sizeof (int));

    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int start = 0, end = n;

    int temp;
    while (start < end){
        int max_index;
        int min_index;

        int max_num = INT_MIN, min_num = INT_MAX;

        for (int i = start; start != end && i < end; i++){
            if (a[i] > max_num){
                max_num = a[i];
                max_index = i;
            }
            if (a[i] < min_num)  {
                min_num = a[i];
                min_index = i;
            }
        }

        if ((max_index == start && min_index == end - 1) || (max_index == end - 1 && min_index == start)){  
            temp = a[end - 1];      //if max and min numbers are at border they will swap two times resulting in same location
            a[end - 1] = a[max_index];
            a[max_index] = temp;
        } else {
            temp = a[end - 1];
            a[end - 1] = a[max_index];
            a[max_index] = temp;

            temp = a[start];
            a[start] = a[min_index];
            a[min_index] = temp;
        }

        start++;
        end--;
    }
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
}

我用 600 个 int 值测试了它，这里是 Output .它似乎工作正常。它比选择排序好还是一样。我想 qsort 在速度和效率方面都优于两者。我在谷歌上查找它，但没有找到与此类似的代码，这让我想知道，这是否足够有效，还是我应该坚持使用选择排序和 qsort。

最佳答案

It would have half of previous time complexity i guess.

O(0.5 * n^2) 仍然是 O(n^2)。一个好的 qsort() 预计 O(n* ln(n))。

Is this efficient enough or should I stick with selection sort and qsort.

许多程序员拥有数十年的经验。

请记住，qsort() 不必使用快速排序 算法。一个好的 qsort() 可能会使用算法的组合。

https://stackoverflow.com/questions/67973299/