最近编程的时候遇到了各种各样的排序问题,很多时候由于数据量不大,就选择了最好理解最容易写的冒泡排序。随着数据量的增大。发现某些时候还是必须使用快排的,特别是有些时候,还要对高维数组进行排序。下面是我最近写的一个关于二维数组进行排序的快速排序的程序。
程序的算法不是很规范。我就是对一维数组的排序进行了改变。思想不是在比较的时候进行两个数据的比较,而是讲二维的数据按照排序顺序的权重问题先进行了一个计算,转成了一个数字,从而使用一维数组的排序比较得出结果。
按照这种排序的思想则可以实现对多维(数字)进行快速排序。比如三维的数组。我们可以计算出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排序的结果。
分享到:
相关推荐
在main函数中,我们定义了一个数组并对其进行快速排序,并打印排序后的结果。 快速排序是一种高效的排序算法,它的实现相对简单但性能优秀。希望这个示例能帮助你理解如何在C语言中实现快速排序算法!
快速排序QuickSort.java
日本程序员norahiko,写了一个排序算法的动画演示,非常有趣...目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的
资源名:quicksort_matlab_快速排序 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定经验的...
QuickSort快速排序的实现 [Qsort类] 使用C++模版,可实现自定义类型的排序方式 同时通过折半查找检索元素 附带控制台演示 欢迎指正和建议 程序详细描述可见:...
快速排序是20世纪十大算法之一,可见其精妙之处,相较于其他复杂度为O(n^2),可以提高到n*logn.一般我们研究快速排序基本采用内置类型,如int型数据,本类为了更通用,采用了模板类,具体数据对象类型可根据用户自己...
快速排序(Quicksort)的Javascript实现
在VS 2008中,用C语言写的快速排序算法。不用多余的数组,直接对原数组进行排序(in place)。同时在递归调用中,对于【数组组就是数组首地址】的理解会更加通透。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为...
快速排序源代码,采用C++编写,经测试未发现BUG,供大家参考
void quicksort(int A[],int p,int r) { int q; if(p) { q=partition(A,p,r); quicksort(A,p,q-1); quicksort(A,q+1,r); } } /****************************************************/
分治法的应用,快速排序是其中一种。注释便于读者明白。
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
基本算法quicksort来对int型arr进行从小到大的排序。。
用分治的思想模拟快速排序的迭代过程,快速排序平均运行时间可以和Heapsort媲美
本算法使用MapBasic编写而成,文件类型为".MB"。如果没有装相关软件,可以使用记事本打开。希望对大家有所帮助。
`quickSort`函数则是使用递归的方式对划分后的数组进行快速排序。 在`main`函数中,定义了一个测试数组`arr`,并计算数组的长度`n`。然后,调用`quickSort`函数对数组进行排序,并打印排序后的结果。 执行程序,...
快速排序快速排序(Quicksort)是对冒泡排序的一种改进。适用很广,高效的排序方法。
用erlang语言实现的快速排序程序,简洁明了,能立即理解快速排序的核心思想