这是我参与更文挑战的第18天，活动详情查看：更文挑战

内容一排序算法

要求：

1.分别针对随机生成的若干组整数序列（比如规模为1000个数，10000个数，100000 个数）进行排序，排序算法使用四种方法，至少包括以下三种经典方法：插入排序算法、合并排序算法和快速排序算法。

2.在用不同的排序算法对多组整数进行排序时，统计各种情况下排序所耗费的时间，并对结果进行分析。

3.当要求为降序时，如何修改？并尝试实现。

4.如果随机生成了10个数，在使用快速排序进行排序时，尝试给出数组的演化情况。

5.排序算法的稳定性。

6.排序算法的空间性能。

实验过程：

一、生成随机数

借助java.util.Random类

	Random r=new Random();
        	a[i]=r.nextInt(100);//生成0-100内的随机整数，为了方便查看后续排序情况
复制代码

补充：Random常用用法

1.random.nextInt()

random.nextIn()的作用是随机生成一个int类型，因为int 的取值范围是 -2147483648——2147483647 ，所以生成的数也是处于这个范围。示例代码：

Random random = new Random();
System.out.println("int:"+random.nextInt());

输出：
int:-1849568817
复制代码

2.random.nextInt(int bound)

random.nextInt(int bound)方法的作用是生成一个0-参数bound范围内的随机数，但是要记住，参数bound必须是正数，不可为负数，否则在运行时会报java.lang.IllegalArgumentException: bound must be positive的错误，提示bound必须是正数。

3.random.nextLong()

random.nextLong()会随机生成一个Long类型，同理，因为Long的取值范围是 -9223372036854775808——9223372036854775807。

4.random.nextDouble()

random.nextDouble()会生成一个0-1的double类型，而不是生成double取值范围中的数，下附取值范围:

Random random = new Random();
System.out.println("double:"+random.nextDouble());

输出：
double:0.9059561641891956
复制代码

5.random.nextFloat()

random.nextFloat()会生成一个随机的0-1之间的浮点型，大体同double一样.

Random random = new Random();
System.out.println("float:"+random.nextFloat());

输出：
float:0.56538385
复制代码

6.random.nextBoolean()

random.nextBoolean()会生成一个true或false

Random random = new Random();
System.out.println("boolean:"+random.nextBoolean());

输出：
boolean:false
复制代码

二、四种排序算法的升序和降序（直接插入，冒泡，合并，快排）

package paixu;

public class Sort {
	//插入排序升序
    public void insertSortAsc(int arr[]){
    	for(int index=1;index<arr.length;index++){
    		int temp=arr[index];//记录待插入元素
    		int leftindex=index-1;//从有序数组最后一个数开始比较
    		while(leftindex>=0&&arr[leftindex]>temp){
    			arr[leftindex+1]=arr[leftindex];
    			leftindex--;
    		}
    		arr[leftindex+1]=temp;
    	}
    }
    //插入排序降序
    public void insertSortDesc(int[] arr){
    	for(int index=1;index<arr.length;index++){
    		int temp=arr[index];//记录待插入元素
    		int leftindex=index-1;//从有序数组最后一个数开始比较
    		while(leftindex>=0&&arr[leftindex]<temp){
    			arr[leftindex+1]=arr[leftindex];
    			leftindex--;
    		}
    		arr[leftindex+1]=temp;
    	}
    }
    //合并排序升序
    //合并操作
    public void mergeAsc(int arr[],int L1,int R1,int L2,int R2){
    	int[] temp;
    	temp=new int[R1-L1+R2-L2+2];
    	int n=L1;
    	int m=L2;
    	int i=0;
    	while(n<=R1&&m<=R2){//数组arr[]拆成左右两个区间，从第一个数开始比较两个区间数大小，小的放在temp[]中
    		if(arr[n]<arr[m]){
    			temp[i++]=arr[n++];
    		}
    		else{
    			temp[i++]=arr[m++];
    		}
    	}
    	while(n<=R1){
    		temp[i++]=arr[n++];
    	}
    	while(m<=R2){
    		temp[i++]=arr[m++];
    	}
    	for(int j=0;j<i;j++){//将排好序的temp[]复制到arr[]中
    		arr[L1+j]=temp[j];
    	}
    }
    public void mergeSortAsc(int arr[],int left,int right){
    	if(left<right){
    		int mid=(left+right)/2;
    		mergeSortAsc(arr,left,mid);//递归
    		mergeSortAsc(arr,mid+1,right);
    		mergeAsc(arr,left,mid,mid+1,right);//合并
    	}
    }
    //合并排序降序
    //合并操作
public void mergeDesc(int arr[],int L1,int R1,int L2,int R2){
	int[] temp;
	temp=new int[100];
	int n=L1;
	int m=L2;
	int i=0;
	while(n<=R1&&m<=R2){//数组arr[]拆成左右两个区间，从第一个数开始比较两个区间数大小，大的放在temp[]中
		if(arr[n]>arr[m]){
			temp[i++]=arr[n++];
		}
		else{
			temp[i++]=arr[m++];
		}
	}
	while(n<=R1){
		temp[i++]=arr[n++];
	}
	while(m<=R2){
		temp[i++]=arr[m++];
	}
	for(int j=0;j<i;j++){//将排好序的temp[]复制到arr[]中
		arr[L1+j]=temp[j];
	}
}
public void mergeSortDesc(int arr[],int left,int right){
	if(left<right){
		int mid=(left+right)/2;
		mergeSortDesc(arr,left,mid);//递归
		mergeSortDesc(arr,mid+1,right);
		mergeDesc(arr,left,mid,mid+1,right);//合并
	}
}
	//快速排序升序
public int PartitionAsc(int arr[],int low,int high){//确定基准元素的位置
	int pivot=arr[low];
	while(low<high){
	while(low<high&&arr[high]>=pivot)
		high--;
	    arr[low]=arr[high];
    while(low<high&&arr[low]<=pivot)
		low++;
	    arr[high]=arr[low];
	}
	arr[low]=pivot;
	return low;
}
public void QuickSortAsc(int arr[],int low,int high){
     if(low<high){
    	 int q=PartitionAsc(arr,low,high);
    	 QuickSortAsc(arr,low,q-1);
    	 QuickSortAsc(arr,q+1,high);
     }	
}
//快速排序降序
public int PartitionDesc(int arr[],int low,int high){//确定基准元素的位置
int pivot=arr[low];
while(low<high){
while(low<high&&arr[high]<=pivot)
	high--;
    arr[low]=arr[high];
while(low<high&&arr[low]>=pivot)
	low++;
    arr[high]=arr[low];
}
arr[low]=pivot;
return low;
}
public void QuickSortDesc(int arr[],int low,int high){
 if(low<high){
	 int q=PartitionDesc(arr,low,high);
	 QuickSortDesc(arr,low,q-1);
	 QuickSortDesc(arr,q+1,high);
 }	
}
//冒泡排序升序
public void BubbleSortAsc(int arr[],int n){
	for(int i=0;i<n;i++){//外层循环表示趟数
		boolean flag=false;//若未发生交换，则flag仍为false
		for(int j=0;j<n-i;j++){
			if(arr[j]>arr[j+1]){//不能写>=，否则不稳定
				int temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
				flag=true;
			}
		}
		if(!flag){//从头到尾没有发生交换，说明数组有序
			break;
		}
	}
}
//冒泡排序降序
public void BubbleSortDesc(int arr[],int n){
	for(int i=0;i<n;i++){//外层循环表示趟数
		boolean flag=false;//若未发生交换，则flag仍为false
		for(int j=0;j<n-i;j++){
			if(arr[j]<arr[j+1]){//不能写<=，否则不稳定
				int temp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
				flag=true;
			}
		}
		if(!flag){//从头到尾没有发生交换，说明数组有序
			break;
		}
	}
}
}
复制代码

列举其中一种输出结果：

System.out.println(Arrays.toString(a));
s.QuickSortDesc(a, 0, a.length-1);
System.out.println("快速排序降序结果为：");
System.out.println(Arrays.toString(a));	

[84, 15, 48, 23, 27, 79, 85, 63, 5, 32]
快速排序降序结果为：
[85, 84, 79, 63, 48, 32, 27, 23, 15, 5]
复制代码

三、计算各排序算法所用时间

补充：java计算程序运行时间：

(1) 以毫秒为单位计算

　long startTime=System.currentTimeMillis();   //获取开始时间
　　doSomeThing();  //测试的代码段
　long endTime=System.currentTimeMillis(); //获取结束时间
　　System.out.println("程序运行时间： "+(end-start)+"ms");
复制代码

(2)以纳秒为单位计算

　long startTime=System.nanoTime();   //获取开始时间
　　doSomeThing();  //测试的代码段
　long endTime=System.nanoTime(); //获取结束时间
　　System.out.println("程序运行时间： "+(end-start)+"ns");
复制代码

本次实验采取第二种方式针对1000个数比较四种排序算法的执行时间。为防止排序后数组对其它排序的影响，在一个排序算法允许时，将另三个排序算法注释掉。
由运行结果可知：

运行时间由小到大分别是：快速排序<合并排序<插入排序<冒泡排序