算法数据结构C++实现6 - 行排序 列排序 Column sort

要用C++是实现起来是很困难的，因为需要用到几大块的小算法，才能实现。

第一是行间排序，第二是行列变换，第三是前后移动元素，这些算法都组合起来，整个过程就变得很复杂了。

这次我是用二维数组来实现的，也可以用vector实现同样的效果，感觉能用vector还是用vector吧。而且我把书中的列排序，改变成行排序了，因为C++的习惯还是行优先数组。

下面是整个程序，程序还是挺大的，相对于一个普通算法来说的话。所以写这个程序也要很耐心，要有时间。

 

#include<iostream>  
  
using namespace std;  
  
const int COLUMNS = 18;  
const int ROWS = 3;  
  
template<typename T>  
void compareExchange(T& a, int i, int j)  
{  
    if(a[i]>a[j])  
        swap((a[i]), (a[j]));  
    //cout<<a[i]<<" "<<a[j]<<endl;  
}  
  
template<typename T>  
void insertionSort(T& a, int n)  
{  
    for(int j=1; j<n; j++)  
        for(int i=j-1; i>=0; i--)  
        {  
            compareExchange(a, i, i+1);  
        }  
}  
  
template<typename T>  
void rowSort(T (&a)[ROWS][COLUMNS])  
{  
    int s=ROWS, c=COLUMNS;  
    //Handle the enter data, make sure it fit this algorithm requirements  
    bool flag = true;  
    if((c%2) != 0)  
    {  
        cerr<<"Error: Columns c must be even!"<<endl;  
        flag = false;  
    }  
    if((c%s) != 0)  
    {  
        cerr<<"Error: Rows s must be a divisor of columns c!"<<endl;  
        flag = false;  
    }  
    if(!(c>=2*s*s))  
    {  
        cerr<<"Warning: Columns c should be >= rows 2*s*s, "  
            <<"or you may not get the correct answer!"<<endl;  
    }  
    if(!flag) return;  
  
    //Sort the rows' elements, using insertion sort algorithm  
    for(int i=0; i<s; i++)  
    {  
        insertionSort(a[i], c);  
    }  
      
    //Change elements of row to column  
    int n = 0;  
    int m = 0;  
    T aTemp[ROWS+1][COLUMNS];  
    for(int i=0; i<s; i++)  
        for(int j=0; j<c; j++)  
        {  
            if(n<s)  
            {  
                aTemp[n][m] = a[i][j];  
                n++;  
            }           //或者也可以把j++放到这里面，n++对应到j++  
            else  
            {  
                n=0;  
                m++;  
                j--;        //非常容易忽略的地方，一不留神就没有考虑到要倒退一个数字了。  
                //一定要在脑子多走几次比较新的逻辑，否则非常容易忽略细节的地方，导致出错。  
                //会浪费很多时间的。  
            }         
        }  
  
    //Sort the aTemp rows' elements, using insertion sort algorithm  
    for(int i=0; i<s; i++)  
    {  
        insertionSort(aTemp[i], c);  
    }  
  
    //Change elements of row to column  
    n = 0;  
    m = 0;  
    for(int j=0; j<c; j++)  
        for(int i=0; i<s; )  
        {  
            if(m<c)  
            {  
                a[n][m] = aTemp[i][j];  
                m++;  
                i++;  
            }//把i和m放在同一个{}里面，这样保证两个下标同步，否则会出现掉值  
            else  
            {  
                m=0;  
                n++;  
            }         
        }  
  
    //Sort the rows' elements, using insertion sort algorithm  
    for(int i=0; i<s; i++)  
    {  
        insertionSort(a[i], c);  
    }  
  
    for(int i=0; i<s+1; i++)  
        for(int j=0; j<c; j++)  
            aTemp[i][j] = 0;    //Supposed 0 is our minimum value.   
                            //You can chenge to minus unlimit if need arise;  
  
    //move every elements back to half of columns position  
    int tempIndex = 0;  
    int halfC = c/2;  
    for(int i=0; i<s; i++)  
        for(int j=0; j<c; j++)  
        {  
            tempIndex = i*c+j+halfC;  
            n = tempIndex/c;  
            m = tempIndex%c;  
            aTemp[n][m] = a[i][j];  
        }  
  
    //Sort the rows' elements  
    for(int i=0; i<s+1; i++)  
    {  
        insertionSort(aTemp[i], c);  
    }  
  
    //move every elements half of columns position  
    for(int i=0; i<s; i++)  
        for(int j=0; j<c; j++)  
        {  
            tempIndex = i*c+j+halfC;  
            n = tempIndex/c;  
            m = tempIndex%c;  
            a[i][j] = aTemp[n][m];  
        }  
    for(int i=halfC; i<c; i++)  
        a[s-1][i] = aTemp[s][i];  
}  
  
void test()  
{  
    //初始化数组  
    double a[ROWS][COLUMNS] =   
    {{32., 12., 0.7, 5., 0.1, 0.7, 0.8,0.7, 99., 0.4, 1., 2.5, 3.6, 5., 9., 12., 19.,953},  
     {0.2, 0.8, 4., 8., 2., 0.8, 56.,0.3, 0.8, 0.4, 8., 7.5, 3.9, 5., 111., 52., 19.,39},  
     {0.25, 0.3, 2., 9., 0.2, 0.78, 0.6,0.37, 0.83, 0.3, 8., 6.5, 9.6, 5., 181., 72., 19.,351}};  
  
    //排序前  
    for(int i=0; i<ROWS; i++)  
    {  
        for(int j=0; j<COLUMNS; j++)  
        {  
            cout<<a[i][j]<<"\t";  
        }  
    }  
    cout<<endl<<endl;  
  
    //调用排序函数  
    rowSort(a);   
      
    //排序后  
    for(int i=0; i<ROWS; i++)  
    {  
        for(int j=0; j<COLUMNS; j++)  
        {  
            cout<<a[i][j]<<"\t";  
        }  
    }  
    cout<<endl;  
  
}  
  
int main()  
{  
    test();  
    return 0;  
}  

 

 

总结：

个人觉得能不用普通c数组还是不要用普通数组，因为下标，内存处理等都非常麻烦，非常耗时。还是用vector等STL的标准容器会大大减少出错的几率。

逻辑问题也很重要，一不留神逻辑上就会出错，即便是能运行，那么结果也是不正确的，这样debug会花费很多时间。

补充：软件开发 , C++ ,