測試了一下蚂蕴，當數(shù)據(jù)量為十萬的時候苛萎，快速排序 是冒泡排序的100倍左右
package com.cts.elt.sort;
import java.util.Arrays;
public class FastSortTest {
public int[] arr;
public void sort(){
quickSort(0,arr.length-1);
}
public void quickSort(int left,int right){
int size =right-left+1;
if (size<10){
insertSort(left,right);
return;
}
int compare =getMedium(left,right);
int pattion = pattionSort(left,right,compare);
quickSort(left,pattion-1);
quickSort(pattion+1,right);
}
public int pattionSort(int left,int right,int compare){
int leftPtr =left;
int rightPtr=right-1;
while (true){
while (arr[++leftPtr]<compare);
while (rightPtr>0&&arr[--rightPtr]>compare);
if (leftPtr>=rightPtr)
break;
if (arr[leftPtr]>arr[rightPtr])
swap(leftPtr,rightPtr);
}
swap(leftPtr,right-1);
return leftPtr;
}
public void swap(int left,int right){
int t =arr[left];
arr[left]=arr[right];
arr[right] =t;
}
public void insertSort(int left,int right){
int out;
int in;
for (out=left+1;out<=right;out++){
in =out;
int temp =arr[out];
while (in>left&&arr[in-1]>temp){
arr[in] =arr[in-1];
in--;
}
arr[in] =temp;
}
}
public int getMedium(int left,int right){
int center =(left+right)>>>1;
if (arr[left]>arr[center])
swap(left,center);
if (arr[left]>arr[right])
swap(left,right);
if (arr[center]>arr[right])
swap(center,right);
swap(center,right-1);
return arr[right-1];
}
public static void main(String[] args){
int size =1000;
int[] arr =new int[size];
for (int i=0;i<size;i++){
arr[i]=(int)(Math.random()*size);
}
FastSortTest fastSort =new FastSortTest();
fastSort.arr =arr;
// fastSort.arr =new int[]{7, 5, 5, 1, 7, 3, 1, 8, 9, 8};
System.out.println("原數(shù)組");
long startTime= System.currentTimeMillis();
System.out.println(Arrays.toString(fastSort.arr));
fastSort.sort();
long endTime= System.currentTimeMillis();
long time =endTime -startTime;
System.out.println("時間"+time);
System.out.println("排序以后數(shù)組"+(endTime-startTime));
System.out.println(Arrays.toString(fastSort.arr));
// System.out.println("次數(shù)="+fastSort.count);
// long startTime= System.currentTimeMillis();
// MaopaoSort maopaoSort =new MaopaoSort();
// maopaoSort.arr =arr;
// maopaoSort.sort();
//
// long endTime= System.currentTimeMillis();
//
// long time =endTime -startTime;
// System.out.println("時間"+time);
}
}
