如何在 C++ 中基于第 3 列（索引除以 3）对一维数组进行快速排序

Question

我有一个一维数组 a[9]={33888,32567,3,32678,31967,2,32333,32456,0}。它不能转换为二维数组，因为二维数组是不允许的。实际上这个一维数组中有三列，如下所示：

A         B          C
33888     32567      3
32678     31967      2
32333     32456      0

因此基于一维数组中 C 列的排序输出将是：

此数组需要根据 C 列排序，即一维数组中所有索引除以 3。但是这个数组不能表示为二维数组。我需要使用一维数组对其进行快速排序。我已经实施了冒泡排序，但速度很慢。任何人都可以通过在 C++ 中实现此问题的快速排序来提供帮助吗？如果任何人都可以通过使用一维数组的内置排序函数来做到这一点，那么它也对我有用。谢谢

Answer 1

你是指以下吗？

#include <iostream>
#include <iomanip>
#include <cstdlib>

int cmp( const void *a, const void *b )
{
    const int *p1 = ( const int * )a;
    const int *p2 = ( const int * )b;

    return ( p2[2] < p1[2] ) - ( p1[2] < p2[2] );
}

int main() 
{
    int a[]  = { 33888, 32567, 3, 32678, 31967, 2, 32333, 32456, 0 };
    const size_t N = sizeof( a ) / sizeof( *a );
    const size_t M = 3;

    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

    std::qsort( a, N / M, sizeof( int[M] ), cmp );


    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

    return 0;
}

程序输出为

33888 32567     3 
32678 31967     2 
32333 32456     0 

32333 32456     0 
32678 31967     2 
33888 32567     3

实际元素的个数应该是3的倍数。一般来说，如果实际元素的个数是N那么qsort的调用看起来像

std::qsort( a, N / 3, sizeof( int[3] ), cmp );

前提是数组中有3个"columns"。

至于你的评论

Thanks. Can you test this array a[]={32678,32567,3,32678,32567,2,32678,32456,0,32567,32678,0,32067,32078,1}. Your code crushes when i increases the array size. If it works with any size then it will be accepted answer.

那你来了。

#include <iostream>
#include <iomanip>
#include <cstdlib>

int cmp( const void *a, const void *b )
{
    const int *p1 = ( const int * )a;
    const int *p2 = ( const int * )b;

    return ( p2[2] < p1[2] ) - ( p1[2] < p2[2] );
}

int main() 
{
    int a[]  = 
    {
        32678, 32567, 3, 
        32678, 32567, 2, 
        32678, 32456, 0, 
        32567, 32678, 0, 
        32067, 32078, 1 
    };

    const size_t N = sizeof( a ) / sizeof( *a );
    const size_t M = 3;

    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

    std::qsort( a, N / M, sizeof( int[M] ), cmp );


    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

    return 0;
}

program 输出是

32678 32567     3 
32678 32567     2 
32678 32456     0 
32567 32678     0 
32067 32078     1 

32678 32456     0 
32567 32678     0 
32067 32078     1 
32678 32567     2 
32678 32567     3

如何在 C++ 中基于第 3 列（索引除以 3）对一维数组进行快速排序

How to quick-sort a 1D array based on 3rd column (index divided by 3) in C++

c++

sorting

algorithm

qsort