插入排序与希尔排序

参考资料：
http://www.cnblogs.com/jingmoxukong/p/4303279.html
http://www.cnblogs.com/jingmoxukong/p/4303279.html

在任意算法能够正常运行之前，必须，有一些前置条件；

1. 插入排序

算法导论中，插入排序的例子举得不错：
前置条件：

1. 假设整个扑克牌，是一个大数组，我们需要对扑克牌进行排序；
2. 先摸一张牌，这个时候，假设手上的第一张牌，是排序好的；
3. 然后，从桌上摸牌，从手中的牌中，找到合适的位置，并插入进去；
4. 重复第三步，直到没桌上的牌都被摸完；

java代码的实现：

/** * 插入排序 */
public static void sort3(int[] a) {   
// 类似于手中的扑克牌，假设是排序好的，每摸一张，我们得找个位置插入进去   
// 1.从下标1开始，遍历整个数组（桌上的牌），下标为0的为已排序好的 （手中的牌）   
// 2.不断获取数组中的数（类似于摸牌）用变量 key 记录其值，表示待插入的数据（摸到的牌）   
// 3.从后往前，遍历已排序好的数组（遍历手中的牌），找到要插入的位置，并插入   
// 4.重复上面的步骤 下标++   

int length = a.length;        // 牌的长度
int i = 1;          // 桌上牌的索引下标            
for (; i < length; i++) {      // 不断摸牌      
  int key = a[i];                 // 摸到的牌    
  int j = i - 1;                // 手中的牌，遍历的下标      
  // 从后往前遍历手中的牌,将手中的牌与 摸到的牌，对比      
  while (j >= 0 && a[j] > key) {         
       a[j + 1] = a[j];   // 元素向后移动        
       j--;      
  }         
  a[j + 1] = key;   // 插入 摸到的牌
 }
}

2. 希尔排序

希尔排序，是对插入排序的补充，通过分组并分组插入排序，来形成局部有序的数组，最后走的还是 原始的插入排序，不过此时的序列，差不多已排序的差不多了。所以，比较，交换次数就少。对比采用 插入排序 与 希尔排序，来说，用希尔的速度 随着待排序数组长度的 增大，而更快；
java代码：

public class SheellSort {   
  public static void main(String[] args) {      
    int[] array = {  10, 5, 3, -1, 88, 0, 2, 100, 22, 89,-9,78,34   };           
    sheellSort(array);   
  }

  public static void sheellSort(int[] list) {   
    // 相比插入排序，希尔排序引入了步长与分组   
    // 相邻步长长度的数，形成分组，并分组进行插入排序   
    // 当步长等于1时，排序整个数组，结束分组循环  
    System.out.print("排序前\t");   
    printAll(list);  

    int length = list.length;   
    int gap = length / 2;        // 初始化步长为数组长度的一半 
    while (gap >= 1) {      
      for (int i = gap; i < length; i++) {    // 步长为gap的编为1组，进行插入排序（分组并进行插入排序）         
        int key = list[i];        // 摸牌         
        int j = i - gap;          // 手中的牌，遍历的下标         
        for (; j >= 0 && list[j] > key; j = j - gap) {    // 从后往前遍历，步长为gap，排序手中的牌           
            list[j + gap] = list[j];        
        }         
        list[j + gap] = key;    // 插入摸到的牌     
      } 
     
      System.out.format("gap=%d\t", gap);      
      printAll(list);      
      gap = gap / 2;             // gap继续缩小，也就是进行下一次分组   
    }   
    System.out.print("排序后\t");   
    printAll(list);
  }

  public static void printAll(int[] list) {   
      for (int value : list) {         
        System.out.print(value + "\t");      
      }  
      System.out.println();  
    }   
  }