插入排序

      在大多数情况下，插入排序算法时本章描述的基本的排序算噶中最好的一种，虽然插入排序算法仍然需要O(N2)的时间，但是在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点。尽管他比冒泡排序和选择排序算法都更麻烦一些，但他也并不很复杂，它经常被用在较复杂的排序算法的最后阶段，例如快速排序。

// insertSort.java	// demonstrates insertion sort	// to run this program: C>java InsertSortApp	//--------------------------------------------------------------	class ArrayIns	   {	   private long[] a;                 // ref to array a	   private int nElems;               // number of data items	//--------------------------------------------------------------	   public ArrayIns(int max)          // constructor	      {	      a = new long[max];                 // create the array	      nElems = 0;                        // no items yet	      }	//--------------------------------------------------------------	   public void insert(long value)    // put element into array	      {	      a[nElems] = value;             // insert it	      nElems++;                      // increment size	      }	//--------------------------------------------------------------	   public void display()             // displays array contents	      {	      for(int j=0; j
    
     0 && a[in-1] >= temp) // until one is smaller,	            {	            a[in] = a[in-1];            // shift item to right	            --in;                       // go left one position	            }	         a[in] = temp;                  // insert marked item	         }  // end for	      }  // end insertionSort()	//--------------------------------------------------------------	   }  // end class ArrayIns		class InsertSortApp	   {	   public static void main(String[] args)	      {	      int maxSize = 100;            // array size	      ArrayIns arr;                 // reference to array	      arr = new ArrayIns(maxSize);  // create the array		      arr.insert(77);               // insert 10 items	      arr.insert(99);	      arr.insert(44);	      arr.insert(55);	      arr.insert(22);	      arr.insert(88);	      arr.insert(11);	      arr.insert(00);	      arr.insert(66);	      arr.insert(33);		      arr.display();                // display items		      arr.insertionSort();          // insertion-sort them		      arr.display();                // display them again	      }  // end main()	   }  // end class InsertSortApp
    

插入排序的效率

       这个算法需要多少次比较和复制呢？在第一趟排序中，它最多比较一次，第二趟中最多比较两次，以此类推，最后一趟最多，比较N-1次，因此有1+2+3+4+...+N-1=N*(N-1)/2,然而，因为在每一趟排序发现插入点之前，平均只有全体数据项的一半真的进行了比较，我们除以2得到N*(N-1)/4,复制的次数大致等于比较的次数，然而一次复制与一次交换的时间耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。在任意情况下，和其他排序一样，对于随机顺序的数据进行插入排序也需要O(N2)的时间级。对于已经有序或者基本有序的数据来说，插入排序要好的多，当数据有序的时候，while循环的条件总是假，所以变成了外层循环的一个简单语句，执行N-1次，这种情况下，算法运行值需要O(N)的时间，如果数据基本有序，插入排序几乎只需要O(N)的时间，这对把一个基本有序的文件进行排序是一个简单而有效的方法。然而对于逆序的数据，每次比较和移动都执行，所以插入排序不比冒泡排序快。