java源代码实现:
//快速排序法 public class QuickSort { public void sort(int left,int right,int []arr){ int l=left; int r=right; int temp=0; //取中间一个数 int pivot=arr[left+(right-left)/2]; //分割 while(l<r){ //默认左边是小的,右边大的-->即左边的所有数小于右边的所有数 //找到左边大的数 while(arr[l]<pivot){ l++; }//当不循环的时候,必定是找到了那个大的数 //找到右边小的数 while(arr[r]>pivot){ r--; } if(l<=r){ //将左边大于pivot的那个数记录下来 temp=arr[l]; //把右边小于pivot的这个数和左边大于pivot的数交换 arr[l]=arr[r]; arr[r]=temp; l++; r--; } }//while循环结束后,arr这个数列被分割了[分割的原理是:依次找到左边大于pivot的数,依次放到右边小于pivot的数的地方,直到l>=r结束] if(l<right){ sort(l,right,arr); } if(r>left){ sort(left,r,arr); } } //显示 public void show(int []arr){ for(int i:arr){ System.out.print(i+" "); } } }
测试代码:
public static void main(String[] args) { final int COUNT=100000000;//一亿 int []arr=new int[COUNT];//={1,6,0,-1,9,-2,12,-90}; for(int i=0;i<COUNT;i++){ arr[i]=(int)(Math.random()*COUNT);//Math.random产生一个0~1的小数,且速度比Random快,因为Random需要实例化;随机生成一亿个数 } long start=System.currentTimeMillis(); //创建一个快速排序法类 QuickSort qs=new QuickSort(); qs.sort(0,arr.length-1,arr); // qs.show(arr);//数据量有点大,不能输出 long end=System.currentTimeMillis(); System.out.println("排序使用的时间是:"+(end-start)/1000+"s"); }
运行结果:
排序使用的时间是:22s
这是我目前为止学的最喜欢的一个排序方法,速度实在是太快了,只有快速排序法才敢测试一亿的数据量,冒泡,选择,插入等排序方法只能测试10万的数据量