冒泡排序，插入排序，快速排序java兑现和效率比较

冒泡排序，插入排序，快速排序java实现和效率比较

从测试结果看，冒泡算法明显不是一般的慢，10万数组的时候冒泡要4秒多，所以就百万就没用冒泡继续测试。

插入排序在结果中看来是最优的，为了方便比较，插入排序分别用了数组和list

综合结果：

list插入排序 > 数组插入排序 > 快速排序 > >  冒泡排序

 

输出结果：

 

******万级测试******
快速排序耗时：
5
list插入排序耗时：
1
数组插入排序耗时：
1
冒泡排序耗时：
372

******百万测试******
快速排序耗时：
118
list插入排序耗时：
1
数组插入排序耗时：
12

import java.util.ArrayList;
import java.util.List;
import java.util.Random;


public class SortPractice {

	public static void main(String[] args){
		System.out.println("******正确性测试******");
		Random random = new Random();
		SortPractice  sp = new SortPractice ();
		int[] nums = new int[10];
		//生成随机整数数组
		for(int i = 0;i<nums.length;i++){
			nums[i] = random.nextInt();
		}
		//输出未排序的数组
		sp.println(nums);
		//输出排序后的数组
		sp.println(sp.sort(nums));
		sp.println(sp.insertSort(nums));		
		sp.println(sp.insertSort(sp.toList(nums)));	
		sp.println(sp.quickSort(sp.toList(nums)));	
		
		System.out.println("******万级测试******");
		//万级排序时间测试
		nums = new int[10000];
		//生成随机整数数组
		for(int i = 0;i<nums.length;i++){
			nums[i] = random.nextInt();
		}
		
		List<Integer> list = sp.toList(nums);
		long begin = System.currentTimeMillis();
		sp.quickSort(list);
		System.out.println("快速排序耗时：\r\n"+(System.currentTimeMillis()-begin));
		
		list = sp.toList(nums);
		begin = System.currentTimeMillis();
		sp.insertSort(list);
		System.out.println("list插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));
		
		begin = System.currentTimeMillis();
		sp.insertSort(nums);
		System.out.println("数组插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));
		
		begin = System.currentTimeMillis();
		sp.sort(nums);
		System.out.println("冒泡排序耗时：\r\n"+(System.currentTimeMillis()-begin));
		
		System.out.println("******百万测试******");
		//百万级，排序时间测试
		nums = new int[1000000];
		//生成随机整数数组
		for(int i = 0;i<nums.length;i++){
			nums[i] = random.nextInt();
		}
		
		list = sp.toList(nums);
		begin = System.currentTimeMillis();
		sp.quickSort(list);
		System.out.println("快速排序耗时：\r\n"+(System.currentTimeMillis()-begin));
		
		list = sp.toList(nums);
		begin = System.currentTimeMillis();
		sp.insertSort(list);
		System.out.println("list插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));
		
		begin = System.currentTimeMillis();
		sp.insertSort(nums);
		System.out.println("数组插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));
	}

	/**
	 * 冒泡排序
	 * @param nums
	 * @return
	 */
	public int[] sort(int[] nums){
		int temp = 0;
		for(int i = 0; i < nums.length-1; i++){
			for(int j = i+1 ;j < nums.length; j++){
				if(nums[j]>nums[i]){
					temp = nums[i];
					nums[i] = nums[j];
					nums[j] = temp;
				}
			}
		}
		return nums;
	}
	
	/**
	 * 插入排序
	 * @param nums
	 * @return
	 */
	public int[] insertSort(int[] nums){
		int temp ;
		for(int i = 1;i<nums.length;i++){
			int j = i-1;
			temp = nums[i];
			while(j>=0&&temp>nums[j]){
				temp = nums[j];
				nums[j] = nums[i];
				nums[i] = temp;
				j--;
			}
		}
		
		return nums;
	}
	/**
	 * list插入排序
	 * @param nums
	 * @return
	 */
	public List<Integer> insertSort(List<Integer> list){
		int temp ;
		for(int i = 1;i <list.size();i++){
			int j = i-1;
			temp = list.get(i);
			while(j >= 0 && temp > list.get(j)){
				temp = list.get(j);
				list.set(j,list.get(i));
				list.set(i,list.get(j));
				j--;
			}
			if(i>=1000) break;
		}
		
		return list;
	}
	
	/**
	 * 快速排序法
	 * @param nums
	 * @return
	 */
	public List<Integer> quickSort(List<Integer> list){
		Integer mid = list.get(new Random().nextInt(list.size()));
		mid = list.get(5);
		List<Integer> small = new ArrayList<Integer>();
		List<Integer> big = new ArrayList<Integer>();
		
		for(int i = 0; i < list.size(); i++){
			if(list.get(i)<=mid){
				small.add(list.get(i));
			}else{
				big.add(list.get(i));
			}
		}
		list.clear();
		if(list.size()>2){
			list.addAll(quickSort(big));
			list.addAll(quickSort(small));
		}else{
			list.addAll(big);
			list.addAll(small);
		}
		return list;
	}
	
	/**
	 * 数组转list
	 * @param nums
	 * @return
	 */
	public List<Integer> toList(int[] nums){
		List<Integer> list = new ArrayList<Integer>();
		for(int i = 0; i < nums.length; i++){
			list.add(nums[i]);
		}
		return list;
	}
	/**
	 * 打印数组
	 * @param nums
	 */
	public void println(int[] nums){
		System.out.println("-----");
		for(int i = 0;i<nums.length;i++){
			System.out.println(nums[i]);
		}
	}
	
	
	/**
	 * 打印list
	 * @param list
	 */
	private void println(List<Integer> list) {
		System.out.println("---------");
		for(Integer obj:list){
			System.out.println(obj);
		}
	}

}