选择排序算法和插入排序算法的性能对比

r囧r小猫 2021-06-24 15:58 423阅读 0赞

选择排序算法和插入排序算法都是O(n^2)复杂度的算法，但是两者的执行效率还是有较大差距的。

public class Sort {
    	private Sort() {};
    	
    	/*
    	 * 选择排序算法
    	 * */
    	public static void selectionSort(Comparable[] arr) {
    		for(int i=0; i<arr.length; i++) {
    			for(int j=i+1; j<arr.length; j++) {
    				if(arr[i].compareTo(arr[j]) > 0)
    					swap(arr, i, j);
    			}
    		}
    	}
    	
    	/*
    	 * 基础型插入排序算法
    	 * */
    	public static void insertSort(Comparable[] arr) {
    		for(int i=0; i<arr.length; i++) {
    			for(int j=i; j>0 && arr[j].compareTo(arr[j-1]) < 0; j--)
    				swap(arr, j, j-1);
    		}
    	}
    	
    	/*
    	 * 改进型插入排序算法
    	 * */
    	public static void insertSortAdvance(Comparable[] arr) {
    		for(int i=0; i<arr.length; i++) {
    			Comparable e = arr[i];
    			int j;
    			for(j=i; j>0 && arr[j-1].compareTo(e) > 0; j--) {
    				arr[j] = arr[j-1];
    			}
    			arr[j] = e;
    		}
    	}
    	
    	/*
    	 * 交换两数字的位置
    	 * */
    	public static void swap(Object[] arr, int i, int j) {
    		Object t = arr[i];
    		arr[i] = arr[j];
    		arr[j] = t;
    	}
    	
    	/*
    	 * 随机生成n个范围在[min, max]区间的Integer型的随机数
    	 * */
    	public static Integer[] randomArray(int n, int min, int max) {
    		Integer[] arr = new Integer[n];
    		for(int i=0; i<n; i++)
    			arr[i] = new Integer((int)(Math.random() * (max - min + 1) + min));
    		return arr;
    	}
    	
    	public static void main(String[] args) {
    		Integer[] a = randomArray(100000, 0, 100);
    		long startTime = System.currentTimeMillis();
    		//selectionSort(a);
    		//insertSort(a);
    		insertSortAdvance(a);
    		long endTime = System.currentTimeMillis();
    		System.out.println("");
    		System.out.println("当前基本插入算法花费时间为" + (endTime-startTime) + "ms");
    	}
    	
    
    }

上述三个算法进行100000个范围在0~100个随机数的排序，使用选择排序算法(selectionSort)所花的时间为33403ms，使用基本插入排序算法(insertSort)所花时间为18475ms，使用改进型插入排序算法所花的时间为15842ms，可见插入排序算法的执行效率要高于选择排序算法。

究其原因，是因为插入排序中有提前中断机制，即某一个数字到某一个合适的位置（前一个比它小，后一个比它大）就不再与其他的数字进行比较了，为了找到这个位置，算法可能要比较n次，也有可能只比较1次，而选择排序算法每次要遍历数组，才能找到合适的位置，插入排序比选择排序少比较的次数就是效率上的提高。在一些高度有序的数组中，插入排序的效率更加突出，只比较少数错序的数字就能完成排序，而选择排序还是要遍历所有数组。

在基础的插入排序中，每交换一次两数字的位置，就要执行一个swap置换函数，要执行三次赋值操作才能完成交换过程；在改进型插入排序中，使用了另一种交换算法，每次只需要执行一次赋值操作就能完成交换过程，所以改进型执行效率要更高一些。