算法练习_插入排序

Posted on | Edited on | Comments: | Views:
插入排序的学习笔记以及代码实现

概念

问题描述

给定无序数组，将数组按从小到大的顺序排列。

算法思想

类比整理桥牌，将每一张桥牌插入到其他整理有序的牌中的适当位置。在数组中，当前索引左边的元素都是有序的，当需要对下一个元素进行排序时，将其插入到左边适当位置，其余元素在插入前向后移一位。可以使用辅助数组保存有序的元素。

图解

代码实现

clojure

1
2
3
4
5
6
7
8
9
10
(defn insert-sort [items]
  (letfn [(insert-item' [items x]
            (cond (empty? items) (list x)
                  (< x (first items)) (concat (list x) items)
                  :else (cons (first items) (insert-item' (rest items) x))))
          (insert-sort' [newItems items]
            (if (empty? items) newItems
                               (insert-sort' (insert-item' newItems (first items)) (rest items))))]
    (insert-sort' (list (first items)) (rest items))))
  )

java

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        for (int j = 0; j < i; j++) {
            int x = a[i];
            if (x < a[j]) {
                System.arraycopy(a, j, a, j + 1, i - j); //偏移j位
                a[j] = x;
                break;
            }
        }
    }
    return a;
}

特点

插入排序所需的时间取决于数组中元素的顺序，与选择排序不同的是，选择排序会遍历数组，与数组本身比较。而插入排序会取出元素之后，与已经排好序部分的元素比较。因此如果数组本身是有序的，或者部分有序，那么插入排序要快很多。同时，插入排序也很适合小规模数组。

参考文档

《算法》