插入排序 Insertion sort

插入排序 Insertion sort

###这个原理应该是最简单的,即假定存在一个有序序列,将另一个数放入其中并保持最终的有序;在插入过程中为顺序扫描整个序列,当发现位置正确时进行插入。
例如手中有一副排好顺序的扑克,摸一张放里面,则需要挨个进行比较才能确定能放置的位置。

插入排序

所以当数据结构为链表时操作比较简单,而为数组时则稍微复杂一些。下面以数组为例。

  1. 将数组分为两部分,前半部分是已排好的有序数组,后半部分都是待插入的数字;开始时前半部分只有序列的第一位,其余后面都是待插入的部分。
  2. 从第二位开始,将第二位的前一位,即第一位与当前位相比,如果比当前位大,则此比较位向后移,然后一直往前找,直到找到比当前位小的,则说明当前位应该放在比较位的后面。
  3. 然后再从当前位的下一位开始,再进行插入。

插入排序

int[] array = {3, 5, 7, 4, 2, 1, 6};
for (int currPos = 1; currPos < array.length; currPos++) {  // 从第二位开始,选取数字进行插入
    int comparePos = currPos - 1;  // 比较位是从前一位开始
    int current = array[currPos];
    while (comparePos >= 0 && array[comparePos] > current) {  // 如果比较位比当前位大,则需要后移
        array[comparePos + 1] = array[comparePos];
        comparePos--;
    }
    array[comparePos + 1] = current;  // 所有比当前位大的都移动完毕,则将当前位放在比较位的后面
}

发表评论