快速排序QuickSort 对于二维或者多维数组进行排序_C/C++_编程开发_程序员俱乐部

?? ?最近编程的时候遇到了各种各样的排序问题，很多时候由于数据量不大，就选择了最好理解最容易写的冒泡排序。随着数据量的增大。发现某些时候还是必须使用快排的，特别是有些时候，还要对高维数组进行排序。下面是我最近写的一个关于二维数组进行排序的快速排序的程序。


??? 程序的算法不是很规范。我就是对一维数组的排序进行了改变。思想不是在比较的时候进行两个数据的比较，而是讲二维的数据按照排序顺序的权重问题先进行了一个计算，转成了一个数字，从而使用一维数组的排序比较得出结果。


??? 按照这种排序的思想则可以实现对多维（数字）进行快速排序。比如三维的数组。我们可以计算出a[0]*100+a[1]*10+a[2]的结果来进行比较，确定是否进行交换。


??? 下面的示例是我写的对一些坐标进行排序。测试数据是：
14
2 1
6 6
4 2
2 5
2 6
2 7
3 4
6 1
6 2
2 3
6 3
6 4
6 5
6 7

参考程序如下：

?

#include <iostream>
using namespace std;

struct Zuobiao
{
	int x;
	int y;
}point[1000];

void QuickSort(Zuobiao a[],int low,int high)
{
	int i,j; 
	i=low; 
	j=high; 
	
	if(low>high)					//已经找完了
		return; 
	
	int temp = a[low].x*10+a[low].y;//将二维数组转换成一个能比较的数
	int temp_x = a[low].x;
	int temp_y = a[low].y;
	
	
	while(i!=j)						//找到要交换的位置 
	{ 
		while( (a[j].x*10+a[j].y)>=temp && j>i) 
			j--; 
		if(j>i) 
		{
			int pos=i++;
			a[pos].x=a[j].x;
			a[pos].y=a[j].y;
		}
		
		while((a[i].x*10+a[i].y) <=temp && j>i) 
			i++; 
		if(j>i)
		{
			int pos=j--;
			a[pos].x=a[i].x;
			a[pos].y=a[i].y;
		}
	} 

	a[i].x=temp_x; 
	a[i].y=temp_y;
	QuickSort(a,low,i-1);			//对左边进行递归
	QuickSort(a,i+1,high);			//对右边进行递归 
}

int main()
{
	int N;
	cin>>N;
	
	int i;
	for(i=1;i<=N;i++)
		cin>>point[i].x>>point[i].y;
	
	QuickSort(point,1,N);

	for(i=1;i<=N;i++)
		cout<<point[i].x<<' '<<point[i].y<<endl;
	
	return 0;
}

?

程序代码可读性不是太好，当时写的主要目的是为了得到答案。像示例的输出结果为：

2 1

2 3

2 5

2 6

2 7

3 4

4 2

6 1

6 2

6 3

6 4

6 5

6 6

6 7

这种就是先对x排序，如果x相同再对y排序的结果。

?