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

Introduction to Algorithm 算法导论第八章的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会花费很多时间。