为什么我实施选择排序比我实施冒泡排序快？

Question

我正在尝试用 c 实现选择排序算法。我不知道这是否是一个正确的实现，以及为什么我的算法比冒泡排序快得多。因此，我想问你是否可以告诉我是否正确以及我必须做出的任何改进。

main(){
    
    srand(time(NULL));
    system("color b");
    
    int A[NUM],i;
    
    for(i=0;i<NUM;i++){
        A[i] = rand()%30000;
    }
    
    displayArray(A);
    SelectionSort(A);   
    displayArray(A);
        
    system("pause");
}

void displayArray(int * A){
    
    int i;
    for(i=0;i<NUM;i++){
        printf("%6d ", A[i]);
    }
    printf("\n");
}


void SelectionSort(int * A){
    
    int i,j,k, pos; 
    for(i=0;i<NUM;i++){
    
        k = A[i];
        for(j=i+1;j<NUM;j++){
            if(k >= A[j]){
                pos = j;
                k = A[j];
            }
        }
        A[pos] = A[i];
        A[i] = k;
        
    }
    
}

Answer 1

你应该用 qsort() 的输出来检查它。
用这个循环填充 2 个数组

int A[NUM], B[NUM], i, n;

for(i=0;i<NUM;i++){
    n = rand()%99999*rand()%99999;
    A[i] = B[i] = n;
}

然后定义一个比较函数，像这样：

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

并使用它从标准库中调用 qsort() 并对 B

进行排序

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

最后一步是比较 A 和 B 以获得大量随机生成的数组。如果它们相等，则您的实施有效。
当然这不是数学证明，但是如果你在做选择排序，你可以通过经验测试

Answer 2

是的，在这种特殊情况下，您的函数是正确的，但总的来说，该函数至少存在三个或多或少的严重缺陷。

第一个是函数依赖于幻数NUM。因此，您不能将该函数用于任何具有不同数量元素的数组。

第二个是你不应该用相等的值交换数组的元素。那就是代替这个条件

if(k >= A[j]){

您应该使用以下条件

if(k > A[j]){

第三个是您不能使用该函数对数组进行降序排序或使用其他排序标准。

至少你的函数不应该依赖于幻数。

对于整数数组，我将按以下方式声明和定义函数。

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

void selection_sort( int a[], size_t n, int cmp( const void *, const void * ) )
{
    for ( size_t i = 0; i < n; i++ )
    {
        size_t pos = i;
        
        for ( size_t j = i + 1; j < n; j++ )
        {
            if ( cmp( a + j, a + pos ) < 0 )
            {
                pos = j;
            }
        }
        
        if ( pos != i )
        {
            int tmp = a[i];
            a[i] = a[pos];
            a[pos] = tmp;
        }
    }
}

int ascending_order( const void *p1, const void *p2 )
{
    int a = *( int * )p1;
    int b = *( int * )p2;
    
    return ( b < a ) - ( a < b );
}

int descending_order( const void *p1, const void *p2 )
{
    int a = *( int * )p1;
    int b = *( int * )p2;
    
    return ( a < b ) - ( b < a );
}

int main(void) 
{
    enum { N = 20 };
    int a[N];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < N; i++ )
    {
        a[i] = rand() % N;
    }
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    selection_sort( a, N, ascending_order );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    selection_sort( a, N, descending_order );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    return 0;
}

程序输出可能看起来像

2 10 1 2 14 8 0 17 13 11 5 12 9 3 13 13 3 12 4 1 
0 1 1 2 2 3 3 4 5 8 9 10 11 12 12 13 13 13 14 17 
17 14 13 13 13 12 12 11 10 9 8 5 4 3 3 2 2 1 1 0

当函数类似于标准 C 函数 qsort 可以应用于任何类型的数组时，可以用更通用的形式编写该函数。但这是一项更复杂的任务。

Answer 3

由于L.Grozinger已经，具有相同复杂度的两种算法并不意味着它们将同样快。这仅意味着如果您按某个因子缩放输入，运行两种算法的宁时间将按相同的比例增加。

例如，假设您首先运行对包含 100 个元素的输入进行 bubbleSort 和 selectionSort。例如，您可能会发现 bubbleSort 需要 4 毫秒，而 selectionSort 只需要 3 毫秒。如果现在将输入缩放为两倍，即 200 个元素，您会发现这两种算法花费的时间大约是原来的四倍：bubbleSort 的运行ning 时间从 4 毫秒跃升至 16 毫秒，而运行selectionSort 的宁时间从 3 毫秒跳到 12 毫秒。

BubbleSort 实际上比 selectionSort 慢。要了解为什么会出现这种情况，请考虑比较排序算法（bubbleSort 和 selectionSort 都是其成员的家族）需要做两种事情：比较和交换。两种算法都需要执行 O(N^2) 次比较才能对列表进行排序，这就是为什么它们的总体复杂度都是 O(N^2) 的原因。但是 selectionSort 只需要 O(N) 次交换，而 bubbleSort 需要 O(N^2) 次交换。大 O 表示法通常会隐藏这一事实，因为它抽象出有关特定操作的细节。

快速排序和堆排序也发生了类似的事情。它们都是 O(n log n)，但 heapSort 比 quickSort 造成更多的缓存未命中。这就是为什么 quickSort 非常，咳咳，更快。

BubbleSort 仅用于教育目的；它在所有方面都比插入排序和选择排序都差。事实上，这就是它服务于教育目的的原因。

为什么我实施选择排序比我实施冒泡排序快？

Why is my implementation of selectionSort faster than my implementation of bubbleSort?

arrays

c

sorting

integer

selection-sort