今天咱们来看一看「 插入排序 」。「 插入排序 」与「 冒泡排序 」一样都属于时间复杂O(n*n)的排序算法,并且也都是基于元素之间比较的方式来完成排序的。不过「 插入排序 」比「 冒泡排序 」在实际应用中更广泛一些,因为它的执行效率更高一点。
插入排序 是一种最简单的排序算法,它的思路是将一组待排序的数据,分成2段,一段是“已经排序”了的数据,另一段是“未排序”的数据。只要每次都从“未排序”的数据中取出一个元素,将这个元素插入到“已经排序”数据中的正确的位置(可能会涉及到原有元素的移动),那么插入后,“已经排序”区段中的数据依然是有序的,只要这样不停的循环,直到所有的“未排序”的数据都已取完,则整个排序完成。
这个原理很像大家平时娱乐时打的扑克牌,在每一局开始的取牌阶段,每取一张牌,就将这张牌插入到手中那些已排好的牌中的正确位置,直到所有的牌取完。
下面用一个整数数组做一个示例:
初始状态 | 8 | 3 | 6 | 2 | 7 | 9 | 移动次数 |
---|---|---|---|---|---|---|---|
第一遍 | 3 | 8 | 6 | 2 | 7 | 9 | 1 |
第二遍 | 3 | 6 | 8 | 2 | 7 | 9 | 1 |
第三遍 | 2 | 3 | 6 | 8 | 7 | 9 | 3 |
第四遍 | 2 | 3 | 6 | 7 | 8 | 9 | 1 |
第五遍 | 2 | 3 | 6 | 7 | 8 | 9 | 0 |
上述示例中,初始数组是 8,3,6,2,7,9,在初始状态时,我们将将数组分为2个段,第一个元素8当做是“已经排序”了的区段,后面所有的元素是作为“未排序”的区段。然后我们开始循环,依次拿出后面“未排序”的区段中的元素与“已经排序”了的区段进行比较,并找到合适的位置插入。
说再多都不与看代码来得直接,下面我们来看一个插入排序的代码:
算法题:对数组arr进行从小到大的排序,假设数组arr不为空,arr的长度为n思路:采用插入排序方法
public void inertSort(int[] arr){ int i,j; int n = arr.length; for(i=1; i<n; i++){ //位置0是“已经排序”区段,因此从位置1开始,依次取出“未排序”区段的元素 int needSort = arr[i]; //在“已经排序”区段中,从后往前循环,对比needSort for(j=i-1; j>=0; j--){ //如果needSort小于arr[j],则说明需要将arr[j]往后移动一位,以便留出空位 if(val < arr[j]){ arr[j+1] = arr[j]; }else{ break; } } //将元素放入到正确的位置 arr[j+1] = needSort; }}
我们按照之前文章中讲到的排序算法评估方法来对「 插入排序 」进行一下性能评估:
以上,就是对数据结构中「 插入排序 」的一些思考,您有什么疑问吗?