经典插入排序的分析、实现、测试

经典插入排序的分析、实现、测试

1.插入排序过程分析

int arr[] = {3,9,-1,-10,-2};

首先假设一个有序列表{3}，一个无序列表{9,-1,-10,-2},每次从无序列表从左到右拿出一个数与有序列表的数进行比较，例如：拿出9,9大于3，所以有序列表为{3,9}，无序列表为{-1,-10,-2}；拿出-1，-1与9比，-1小，有序列表变为{3，-1,9}，再拿-1与3比较，-1小，有序列表为{-1,3，9}； … 说起来容易做起来难，看代码实现。

2.代码实现

package test1; import java.util.Arrays; import java.util.Random; /** * 插入排序 */ public class InsertSort { public static void main(String[] args) { //int arr[] = {3, 9, -1, -10, -2}; int arr[] = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i]= new Random().nextInt(80000); } long before = System.currentTimeMillis(); sort(arr); long after = System.currentTimeMillis(); System.out.println((after - before) +"毫秒！"); } public static int[] sort(int[] arr) { //假设第一个元素是有序列表，拿后面的元素进行比较，需要比较arr.length-1次 for (int i = 1; i < arr.length; i++) { //每次需要插入到有序列表的数字 int num = arr[i]; //每次需要插入的数字的前一个元素的下标，记录他是为了比较 int index = i - 1; //index=0时到达arr[0]，循环会使index==-1，出现下标越界，所以要进行判断index要大于=0 //用需要插入的元素与他的前一个元素进行比较，如果大，那么肯定比有序列表的所有数都大，所以直接排在后面 //如果小，则说明这个需要插入的元素在有序列表的某个位置，循环与有序列表的元素进行比较，找到自己的位置 while (index >= 0 && num < arr[index] ) { //如果小，使待插入元素的位置后移 arr[index+1] = arr[index]; //交换位置 arr[index] =num; //下标减一，继续向前查找 index--; } } //System.out.println(Arrays.toString(arr)); return arr; } }

3.插入排序测试

我的电脑测试了大约需要0.93秒的时间，比上上一篇冒泡的时间快了7秒多，顺嘴提一句选择排序的时间复杂度是O（n^2）