算法导论-插入排序

 

以前陆陆续续看了下书，但没有写代码，这次决定从头学起，一步一步实践，加深理解，希望能够坚持记录下这期间的苦与乐。

 

第一个算法是直接插入排序：

现实实例：

      原理类似打牌的时候，整理手中的牌。开始摸牌时，手是空的，接着从桌上摸起一张牌，并将它插入到手上一把牌中的正确位置，为了找到这张牌的正确位置，必须要与手中已有的牌进行比较。

 

伪代码描述：

 

直接插入排序java代码（升序）：

 

插入排序 1 public void insertSort( int [] a){ 2 if (a.length > 0 ) { 3 for ( int j = 1 ; j < a.length ; j ++ ){ 4 int key = a[j]; 5 int i = j - 1 ; 6 while (i >= 0 && a[i] > key ) { 7 a[i + 1 ] = a[i]; 8 i -- ; 9 } 10 a[i + 1 ] = key ; 11 } 12 } 13 }

 

其他形式：

插入排序-递归版 /* * 递归版 */ public void insertSortRec( int []a, int n){ if (n > 1 ){ insertSortRec(a, n - 1 ); // 把第n个元素插入已排好序的a[0,n-2]中 insert(a, n - 1 , n); } } private void insert( int [] a, int end, int n) { int temp = a[n - 1 ]; int i; for ( i = end - 1 ; i >= 0 ; i -- ) { if (a[i] > temp) a[i + 1 ] = a[i]; else break ; } a[i + 1 ] = temp; }

 

适用范围：       直接插入排序采用的是增量的方法，在数组前n-1个元素排好序后将第n个元素适当插入。算法适用于少量数据的排序，时间复杂度为O(n^2)。

转载于:https://www.cnblogs.com/afirefly/archive/2010/07/18/1780036.html

相关资源：数据结构—成绩单生成器