刚刚找到工作,但是发现自己虽然对数据结构的知识了解原理,但是实现的话,仍然有很大的麻烦。决定在大学的最后几个月对数据结构进行一个系统的详细的学习。好了,第一篇:快速排序的算法。由于我只是想实现一个简单的原理,所以类的构造就比较简单了,比较的原型都死int型的。
快速的排序的定义我不说了,直接贴源代码:
public class BaseQuickSort implements QuickSortExecutor{
private int[] arrays;
@Override
public void executor() {
if(arrays == null || arrays.length == 0)
{
throw new IllegalArgumentException("array can not be null or length is zero");
}
quickSort(0,arrays.length - 1);
}
private void quickSort(int low,int high)
{
int key = arrays[high];
int begin = low;
int end = high;
int position = high;
int temp ;
while(begin < end){
if(position == end){
if(arrays[begin] <= key)
begin++;
else {
temp = arrays[begin];
arrays[begin] = key;
arrays[position] = temp;
position = begin;
end--;
}
}else if(position == begin)
{
if(arrays[end] >= key)
{
end--;
}else{
temp = arrays[end];
arrays[end] = key;
arrays[position] = temp;
position = end;
begin++;
}
}
}
if(low < position - 1)
quickSort(low, position - 1);
if(position + 1 < high)
quickSort(position + 1,high);
}
public int[] getArrays() {
return arrays;
}
public void setArrays(int[] arrays) {
this.arrays = arrays;
}
public static void main(String[] args) {
BaseQuickSort sort = new BaseQuickSort();
int[] arrays = new int[]{128,137,1898989,55,532,99,12,3,1000,255};
sort.setArrays(arrays);
sort.executor();
for(int i = 0;i< arrays.length ;i++)
{
System.out.print(arrays[i] + " ");
}
}
}
这个的实现是使用的是递归结构,所以说还是比较简单的。下面是一个实现了不使用系统的递归函数,自己定义的一个栈,用来排序,也是快速排序的算法实现:
public class NoStackQuickSort implements QuickSortExecutor{
int[] arrays;
@Override
public void executor() {
if(arrays == null || arrays.length == 0)
{
throw new IllegalArgumentException("array can not be null or length is zero");
}
int[] stack = new int[arrays.length];
int stacktop = 0;
stack[stacktop] = 0;
stacktop++;
stack[stacktop] = arrays.length-1;
stacktop++;
while(stacktop != 0)
{
stacktop--;
int uhigh = stack[stacktop];
stacktop--;
int ulow = stack[stacktop];
if(uhigh > ulow)
{
// 进行排序 获得mid值
int mid = spitArrays(ulow, uhigh);
if(mid - ulow > uhigh - mid)
{
stack[stacktop] = ulow;
stacktop++;
stack[stacktop] = mid - 1;
stacktop++;
if(uhigh > mid)
{
stack[stacktop] = mid+1;
stacktop++;
stack[stacktop] = uhigh;
stacktop++;
}
}else{
stack[stacktop] = mid + 1;
stacktop++;
stack[stacktop] = uhigh;
stacktop++;
if(mid > ulow)
{
stack[stacktop] = ulow;
stacktop++;
stack[stacktop] = mid - 1;
stacktop++;
}
}
}
}
}
private int spitArrays(int low,int high){
int key = arrays[high];
int begin = low;
int end = high;
int position = high;
int temp ;
while(begin < end){
if(position == end){
if(arrays[begin] <= key)
begin++;
else {
temp = arrays[begin];
arrays[begin] = key;
arrays[position] = temp;
position = begin;
end--;
}
}else if(position == begin)
{
if(arrays[end] >= key)
{
end--;
}else{
temp = arrays[end];
arrays[end] = key;
arrays[position] = temp;
position = end;
begin++;
}
}
}
return position;
}
public int[] getArrays() {
return arrays;
}
public void setArrays(int[] arrays) {
this.arrays = arrays;
}
public static void main(String[] args) {
//设置十万个随机数
int length = 10 * 10000;
int[] arrays = new int[length];
int[] copyArrays = new int[length];
int[] bubbleArrays = new int[length];
//开始使用内存的算法
Random random = new Random();
for(int i = 0;i< length;i++)
{
arrays[i] = random.nextInt(Integer.MAX_VALUE);
}
System.arraycopy(arrays, 0, copyArrays, 0, length);
System.arraycopy(arrays, 0, bubbleArrays, 0, length);
//初始化进行测试
for(int i = 0;i<length ;i++)
{
if(arrays[i] != copyArrays[i])
throw new IllegalArgumentException();
}
for(int i = 0;i<length ;i++)
{
if(arrays[i] != bubbleArrays[i])
throw new IllegalArgumentException();
}
BaseQuickSort stackExecutor = new BaseQuickSort();
NoStackQuickSort noStackExecutor = new NoStackQuickSort();
BubbleSortExecutor bubbleExecutor = new BubbleSortExecutor();
stackExecutor.setArrays(arrays);
noStackExecutor.setArrays(copyArrays);
bubbleExecutor.setArrays(bubbleArrays);
long begin = System.currentTimeMillis();
stackExecutor.executor();
long end = System.currentTimeMillis();
System.out.println("运行时间:使用栈:" + (end - begin));
//--------------------------------------
begin = System.currentTimeMillis();
noStackExecutor.executor();
end = System.currentTimeMillis();
System.out.println("运行时间:不使用栈:" + (end - begin));
//-------------------------------------
begin = System.currentTimeMillis();
bubbleExecutor.executor();
end = System.currentTimeMillis();
System.out.println("运行时间,冒泡:" + (end - begin));
//测试是否排序正确
for(int i = 0;i<length ;i++)
{
if(arrays[i] != copyArrays[i])
throw new IllegalArgumentException();
}
for(int i = 0;i<length ;i++)
{
if(arrays[i] != bubbleArrays[i])
throw new IllegalArgumentException();
}
}
}
最后的main函数里面,我对算法进行了测试,发现,快速算法确实比冒泡算法实现快多了,
之所以不设置太多的随机数排序,是因为在冒泡算法的运行效率实在是太低了,在这个算法的测试中,我的冒泡算法的时间通常达到34秒,但是快速排序却是15ms,差距很大啊。
这个测试中,如果仅仅是区别快速排序的两种实现的话,我们可以发现,快速排序的递归函数的时间消耗是小于我们自己写的不是递归的构造快速排序算法。但是在十万的数据一下,二者的时间是相同的。只是在百万的数据量下,才能显示是也是微小的时间差距。
好了,快速排序写完了
分享到:
相关推荐
详细解释了快速排序的java实现.里面有代码,还有注释说明
主要介绍了java 算法之快速排序实现代码的相关资料,需要的朋友可以参考下
java实现的快速排序算法
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045
java 快速排序 折半查找的界面实现 (递归与分治法)
java中实现快速排序算法。随机产生几个数然后对其进行排序
这份资源提供了Java中如何实现快速排序的全面指南。文档中涵盖了快速排序的基本概念,包括如何对数组进行排序以及如何在Java中实现快速排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现快速排序,包括...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
一个简单的快速排序算法,用JAVA编写的
快速排序 * 1.i=left,j=right,将基准数挖出形成第一个坑a[i]; * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]; * 3.i++由前向后找比它大的数,找到后挖出此数填到前一个坑a[j]中 * 4.以i为中线,...
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
快速排序是一个知名度极高的排序算法,其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。这里采用简单的小例子实现快速排序。
快速排序的 Java 实现代码例子程序,需要的可以参考
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典...
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
快速排序算法java代码,内附运行结果,望对大家有帮助,谢谢!