package source.datastruct_algorithm;
import java.util.Random;
public class SortUtil {
static int size =10000;
static VirtualObj[] persion ;
static long[] arr ;
//初始化测试数据
@SuppressWarnings("unchecked")
static synchronized void init(){
persion = new VirtualObj[size];
arr = new long[size];
Random ran = new Random();
for(int i=0;i<size;i++){
char num = (char)(Math.random() * 196 + 'A');
persion[i] = new VirtualObj("tom"+(char)num,num,num);
}
for(int i =0;i<size;i++){
arr[i] = ran.nextInt(10000);
}
Proxy.serviceProxy().initLongArr(arr);
Proxy.serviceProxy().initObjArr(persion);
}
//设置整形数组
public void setBaseArray(long[] array){
arr= array;
size= array.length;
}
//设置对现货数组
public void setObjArray(Object[] arr){
persion = (VirtualObj[])arr;
size= persion.length;
}
//冒泡排序
public static void bubbleSort(){
Proxy.serviceProxy().baseBubbleSort();
Proxy.serviceProxy().objBubbleSort();
}
//选择排序
public static void selectSort(){
Proxy.serviceProxy().baseSelectSort();
Proxy.serviceProxy().objSelectSort();
}
//插入排序
public static void insertSort(){
Proxy.serviceProxy().baseInsertSort();
Proxy.serviceProxy().objInsertSort();
}
//归并排序
public static void mergeSort(){
Proxy.serviceProxy().baseUnionSort();
Proxy.serviceProxy().objUnionSort();
}
//希尔排序
public static void shellSort(){
Proxy.serviceProxy().baseShellSort();
Proxy.serviceProxy().objShellSort();
}
//快速排序
public static void quickSort(){
Proxy.serviceProxy().baseQuickSort();
Proxy.serviceProxy().objQuickSort();
}
public static void main(String[] args) {
init();
System.out.println(System.currentTimeMillis());
bubbleSort();
System.out.println(System.currentTimeMillis());
System.out.println("bubble sort ..............................");
init();
System.out.println(System.currentTimeMillis());
selectSort();
System.out.println(System.currentTimeMillis());
System.out.println("select sort ..............................");
System.out.println(System.currentTimeMillis());
init();
insertSort();
System.out.println(System.currentTimeMillis());
System.out.println("insert sort ..............................");
init();
System.out.println(System.currentTimeMillis());
mergeSort();
System.out.println(System.currentTimeMillis());
System.out.println("merge sort ..............................");
init();
System.out.println(System.currentTimeMillis());
shellSort();
System.out.println(System.currentTimeMillis());
System.out.println("shell sort ..............................");
init();
System.out.println(System.currentTimeMillis());
quickSort();
System.out.println(System.currentTimeMillis());
System.out.println("quick sort ..............................");
}
}
//排序代理
class Proxy{
@SuppressWarnings("rawtypes")
private static SortService service = new SortService();
@SuppressWarnings("rawtypes")
public static SortService serviceProxy(){
return service;
}
}
//排序实现类
class SortService<T extends VirtualObj>{
private long[] longArr;//模拟整形数组
private T[] objArr;//模拟对象数组
private int size;
public void initLongArr(long[] arr){
longArr = arr;
size = arr.length;
}
public void initObjArr(T[] arr){
objArr = arr;
size = arr.length;
}
public void baseQuickSort(){
baseRecQuicSort(0, size-1);
displayLongArr();
}
//基本类型的快速排序
private void baseRecQuicSort(int left,int right){
if(right - left +1 <=10){
baseInsertSort(left,right);
}else{
long povit = baseGetPivot(left, right);
//long povit = longArr[right];
int compareIndex = basePartition(left,right,povit);
baseRecQuicSort(left,compareIndex);
baseRecQuicSort(compareIndex+1, right);
}
}
//快速排序时的插入排序
private void baseInsertSort(int left,int right){
int j=0;
for(int i=left+1;i<=right;i++){
long temp = longArr[i];
for(j =i;j>left&&longArr[j-1]>temp;j--){
longArr[j]=longArr[j-1];
}
longArr[j] = temp;
}
}
//3项取中，防止数据不随机
private long baseGetPivot(int left,int right){
int center = (left + right)/2;
if(longArr[left] <= longArr[center]){
swap(left, center);
}
if(longArr[left]<= longArr[right]){
swap(left, right);
}
if(longArr[center] > longArr[right]){
swap(center, right);
}
return longArr[right];
}
//快速排序
private int basePartition(int left,int right,long povit){
int leftindex = left;
int rightindex = right-1;
while(true){
while(longArr[++leftindex] < povit);
while((--rightindex)>0&&longArr[rightindex] > povit);
if(leftindex >= rightindex)break;
else{
swap(leftindex, rightindex);
}
}swap(leftindex, right -1);
return leftindex;
}
//交换
private void swap(int indexFrom,int indexTo){
long temp = longArr[indexFrom];
longArr[indexFrom] = longArr[indexTo];
longArr[indexTo] = temp;
}
//对象类型快速排序
public void objQuickSort(){
objRecQuickSort(0,size-1);
displayObjArr();
}
//对象类型快速排序
private void objRecQuickSort(int left,int right){
if(right - left <10){
objInsertSort(left,right);
}
else{
T compareObj = objGetPovit(left,right);
//T compareObj = objArr[right];
int compareIndex = objPartion(left,right,compareObj);
objRecQuickSort(left, compareIndex);
objRecQuickSort(compareIndex+1, right);
}
}
//对象快速排序
private int objPartion(int left,int right,T povit){
int leftindex = left;
int rightindex = right-1;
while(true){
while(objArr[++leftindex].getStr().compareTo(povit.getStr())<0);
while(objArr[--rightindex].getStr().compareTo(povit.getStr())>0);
if(leftindex >= rightindex)break;
else{
swapObj(leftindex, rightindex);
}
}swapObj(leftindex, right-1);
return leftindex;
}
//对象插入排序
private void objInsertSort(int left,int right){
int i=0;
for(int j =left+1;j<size;j++){
T temp = objArr[j];
for(i=j;i>left&&objArr[i-1].getStr().compareTo(temp.getStr())>0;i--){
objArr[i] = objArr[i-1];
}
objArr[i] = temp;
}
}
//3项取中 针对数组不大小不随机
private T objGetPovit(int left,int right){
int center = (right + left)/2;
T t_left = objArr[left];
T t_center = objArr[center];
T t_right = objArr[right];
if(t_left.getStr().compareTo(t_center.getStr()) >0){
swapObj(left,center);
}
if(t_center.getStr().compareTo(t_right.getStr()) <0){
swapObj(center, right);
}
if(t_left.getStr().compareTo(t_right.getStr()) >0){
swapObj(left, right);
}
return objArr[right];
}
//对象交换
private void swapObj(int from,int to){
T temp = objArr[from];
objArr[from] = objArr[to];
objArr[to] = temp;
}
//基本类型希尔排序 增量-3
public void baseShellSort(){
int h=1;
int in,out;
while(h<size/3){
h=h*3+1;
}
while(h>0){
for(out = h;out<size;out++){
long temp = longArr[out];
for(in=out;in > h-1&&longArr[in-h] >= temp;in-=h){
longArr[in] = longArr[in-h];
}
longArr[in] = temp;
}
h=(h-1)/3;
}
displayLongArr();
}
//对厦门和类型希尔排序 增量-3
public void objShellSort(){
int h=1;
int in,out;
while(h<size/3){
h=h*3+1;
}
while(h>0){
for(out = h;out<size;out++){
T temp = objArr[out];
for(in=out;in > h-1&&objArr[in-h].getStr().compareTo(temp.getStr())>0;in-=h){
objArr[in] = objArr[in-h];
}
objArr[in] = temp;
}
h=(h-1)/3;
}
displayObjArr();
}
//基本类型归并排序
public void baseUnionSort(){
long[] workspace = new long[size];
baseMergeSort(workspace,0, workspace.length-1);
displayLongArr();
}
//归并算法
private void baseMergeSort(long[] arr,int lower,int upper){
if(lower == upper)return;
int mid = (upper+lower)/2;
baseMergeSort(arr,lower,mid);
baseMergeSort(arr,mid+1,upper);
baseMerge(arr,lower,mid+1,upper);
}
//归并排序算法
private void baseMerge(long[] arr,int lower,int mid,int upper){
int i=0,middle = mid-1;
int low = lower;
int size = (upper - lower)+1;
while(lower <=middle&&mid<=upper){
if(longArr[lower] < longArr[mid]){
arr[i++] = longArr[lower++];
}
else{
arr[i++] = longArr[mid++];
}
}
while(lower<=middle){
arr[i++] = longArr[lower++];
}
while(mid<=upper){
arr[i++] = longArr[mid++];
}
for(int j=0;j<size;j++){
longArr[low+j] = arr[j];
}
}
//对象类型归并排序 ： 当有大量重复时，结果不准确
public void objUnionSort(){
VirtualObj[] t = new VirtualObj[size];
objMergeSort((T[])t,0,size-1);
displayObjArr();
}
//归并算法
private void objMergeSort(T[] arr,int lower,int upper){
if(lower == upper)return;
int mid = (upper+lower)/2;
objMergeSort(arr,lower,mid);
objMergeSort(arr,mid+1,upper);
objMerge(arr,lower,mid+1,upper);
}
//归并排序算法
public void objMerge(T[] arr,int lower,int mid,int upper){
int low = lower;
int i=0;
int size = (upper - lower)/2;
int middle = mid-1;
while(lower <=middle&&mid<=upper){
if(objArr[lower].getStr().compareTo(objArr[mid].getStr())<0){
arr[i++] = objArr[lower++];
}else{
arr[i++] = objArr[mid++];
}
}
while(lower <= middle){
arr[i++] = objArr[lower++];
}
while(mid<=upper){
arr[i++] = objArr[mid++];
}
for(int j=0;j<size;j++){
objArr[low+j] = arr[j];
}
}
//基本类型冒泡排序
public void baseBubbleSort(){
for(int i =size-1; i>1;i--){
for(int j = 0 ; j < i ; j ++){
if(longArr[j] > longArr[j+1]){
long temp;
temp = longArr[j];
longArr[j] = longArr[j+1];
longArr[j+1] = temp;
}
}
}
displayLongArr();
}
//对象类型冒泡排序
public void objBubbleSort(){
T temp;
for(int i =size-1; i>1;i--){
for(int j = 0 ; j < i ; j ++){
if(objArr[j].getStr().compareTo(objArr[j+1].getStr())>0){
temp = objArr[j];
objArr[j] = objArr[j+1];
objArr[j+1] = temp;
}
}
}
displayObjArr();
}
//基本类型插入排序
public void baseInsertSort(){
int j;
for(int i=1;i<size;i++){
long temp = longArr[i];
for(j=i;j>0&& longArr[j-1]>temp;j--){
longArr[j]=longArr[j-1];
}
longArr[j]=temp;
}
displayLongArr();
}
//对象类型插入排序
public void objInsertSort(){
int j;
for(int i=1;i<size;i++){
T temp = objArr[i];
for(j=i;j>0&& objArr[j-1].getStr().compareTo(temp.getStr())>0;j--){
objArr[j]=objArr[j-1];
}
objArr[j]=temp;
}
displayObjArr();
}
//基本类型选择排序
public void baseSelectSort(){
for(int i=0;i<size;i++){
for(int j=i;j<size;j++){
if(longArr[i]>longArr[j]){
long temp;
temp = longArr[i];
longArr[i] = longArr[j];
longArr[j] = temp;
}
}
}
displayLongArr();
}
//对象类型选择排序
public void objSelectSort(){
T temp;
for(int i=0;i<size;i++){
for(int j=i;j<size;j++){
if(objArr[i].getStr().compareTo(objArr[j].getStr()) > 0){
temp = objArr[i];
objArr[i] = objArr[j];
objArr[j] = temp;
}
}
}
displayObjArr();
}
public void displayLongArr(){
for(int i =0 ;i<size;i++){
System.out.print(longArr[i]+" ");
}System.out.println();
}
public void displayObjArr(){
for(int i =0 ;i<size;i++){
System.out.print(objArr[i].getStr()+" ");
}System.out.println();
}
}
//虚拟对象可以作为排序的转换类
class VirtualObj{
public VirtualObj() {
super();
}
public VirtualObj(String str, int age, float idCard) {
super();
this.str = str;
this.age = age;
this.idCard = idCard;
}
public String getStr() {
return str;
}
public void setName(String str) {
this.str = str;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public float getIdCard() {
return idCard;
}
public void setIdCard(float idCard) {
this.idCard = idCard;
}
private String str;
private int age;
private float idCard;
}
总结 ： 在次测试了数组在1000 和10000的情况 看出 冒泡，选择，插入这三个0(N平方)算法 冒泡最慢，插入稍微由于选择.不过大致相当
而归并和希尔表现出色 . 但是快速排序本以为很好的 表现不如前两者，但是有序前面简单派算法。 当然本数据具有很多的重复数据，只是在该环境下的效率大概如此.推荐在数据较多重复情况下优先选择 希尔和归并排序.
数组元素不重复情况
若将init 方法替换为如下代码：
static synchronized void init(){
persion = new VirtualObj[size];
arr = new long[size];
int[] ran_arr = randomInt();
for(int i=0;i<size;i++){
persion[i] = new VirtualObj("tom"+ran_arr[i],ran_arr[i],ran_arr[i]);
}
for(int i =0;i<size;i++){
arr[i] = ran_arr[i];
}
Proxy.serviceProxy().initLongArr(arr);
Proxy.serviceProxy().initObjArr(persion);
}
private static int[] randomInt(){
Random ran = new Random();
boolean[] bool = new boolean[size];
int rs[] = new int[size];
int temp,j=0;
for(int i=0;i<size;i++){
do{
temp = ran.nextInt(size);
}while(bool[temp]);
bool[temp] =true;
rs[j++]=temp;
}
return rs;
}
可是数据完全不重复。。
结论同上。 希尔和归并 随数据增大效率提高可在10倍及,快速排序仍略差.应该两-3倍于简单排序. [执行环境同上]