insert sort

插入排序将数据分为前面有序部分和后面无序部分,取无序部分的第一个元素插入到有序序列中.

注意与选择排序的区别.

// insert sort
void insertionSort(int arr[], int length) {
      int i, j, tmp;
      for (i = 1; i < length; i++) {
            j = i;
            while (j > 0 && arr[j ­ 1] > arr[j]) {
                  tmp = arr[j];
                  arr[j] = arr[j ­ 1];
                  arr[j ­ 1] = tmp;
                  --j­­;
            }
      }
}