时间戳

首页 > 解决方案 > 如何在 C++ 中基于第 3 列（索引除以 3）快速排序一维数组

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

问题描述

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

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

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

32333
32456
0
32678
31967
2
33888
32567
3

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

标签： c++algorithmsortingqsort

解决方案

你的意思是以下吗？

#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 个“列”。

至于你的评论

谢谢。你能测试这个数组 a[]={32678,32567,3,32678,32567,2,32678,32456,0,32567,32678,0,32067,32078,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[]  = 
    {
        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;
}

程序输出为

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

推荐阅读