用JAVA写了一个快速排序 大家帮我检查一下有没有错误 也太快了吧。。。

Question

import java.util.Calendar;/*
 * 时间：2011.9.22下午
 * 作用：快速排序
 * 作者：张鹏飞
 * 注意：如果打印输出  会非常慢
 * *///帮我看看有没有错误   设置 size就可以调整测试数据的数量   10000以上千万不要打印   不然很慢    
//不打印  即使10000000  也才几秒钟   如果用冒泡  估计得半小时 。也太快了吧   是不是我哪里写错了public class first { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
int size=1000;
int a[]=new int[size];
for(int i=0;i<a.length;i++)
a[i]=(int)(Math.random()*size);

for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
quickSort test=new quickSort(a);
Calendar cal=Calendar.getInstance();
System.out.println("排序前："+cal.getTime());//打印系统时间 来计算排序用时

test.sort(0,a.length-1); cal=Calendar.getInstance();//重新调用系统时间
System.out.println("排序后："+cal.getTime());

test.show();
}}
class quickSort{
private int a[]; quickSort(int a[]){
this.a=a; }

public void sort(int left, int right) { 
    int l = left; 
    int r = right; 
    if (l >=r) 
      return; 
while(l<r){
    while (l< r) { 
      if (this.a[l] >this.a[r]) { 
        //交换数字 
        int temp = this.a[l]; 
        this.a[l] = a[r]; 
        this.a[r] = temp; 
        l++;
        break;
      } 
      else r--;
      }
         while (l<r){
    
     if(this.a[l]>this.a[r]){
     int temp=this.a[l];
     a[l]=a[r];
     a[r]=temp;
     r--;
     break;
     }
     else l++;
    }}       
    sort(left, l-1); 
    sort(r+1, right);
}
    


void show(){
System.out.println("排序后为：");
for(int i=0;i<this.a.length;i++)
System.out.print(this.a[i]+" ");
}
}

Answer 1

你写的应该没有错如果使用Java的api的话，效果会更明显Arrays.sort()这个方法是一个经过优化过的快速排序，它排序10000000个数据只用了2秒多
import java.util.*;public class Test
{
public static void main(String[] args)
{
int size = 10000000;
int[] array = new int[size];
for (int i = 0; i < size; i++)
{
array[i] = (int) (Math.random() * size);
}
System.out.println("排列前：" + System.currentTimeMillis() + "毫秒");
Arrays.sort(array);
System.out.println("排列后：" + System.currentTimeMillis() + "毫秒");
}
}

Answer 2

就对你的代码提些建议吧1 类名最好大写字母开始，采用  MyClassName 的样子（具体叫什么名字不记得了） 而不是像你这样的 quickSort
2 我不觉得将快排封装成一个类是明智的

Answer 3

package com.quickSort;
import java.util.*;
/**
 * @author neil
 * @date 2011-9-23
 * @fileName QuickSort.java
 * @packageName com.quickSort
 */
public class QuickSort
{
public static void main(String args[])
{
Quick_order a1 = new Quick_order();
int num = 10000000;
int array[] = new int[num];
for(int i = 0;i < num; i++)
   array[i] = (int) (Math.random()*100000);

Calendar cal = Calendar.getInstance();
System.out.println("系统时间：" + cal.getTime());
a1.order(0, array.length-1, array);
cal=Calendar.getInstance();
System.out.println("系统时间：" + cal.getTime());
for(int i = 0;i < 100; i++)
System.out.print(array[i] + " ");
}
}
class Quick_order
{
public void order(int left,int right,int array[])
{
int l = left;
int r = right;
int key = array[(left+right)/2];
int temp = 0;
while(l < r)
{
while(array[l] < key) l++;
while(array[r] > key) r--;

if(l == r) break;

temp = array[l];
array[l] = array[r];
array[r] = temp;
if(array[l] == key) r--;
if(array[r] == key) l++;
}

if(l == r)
{
l++;
r--;
}
if(left < r)      order(left,r,array);
if(right > l)     order(l,right,array);
}
}

Answer 4

快速排序是冒泡排序要快2-3倍，而Arrays.sort()和Collections.sort()要比冒泡排序快几倍-几十倍。

Answer 5

Arrays.sort   貌似对于基本类型是 快排 实现吧？   不过很多优化