排序算法:插入排序

icy2003 程序 2020-05-12 18:38:56 118 0条

插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动

3.gif

算法评价

  • 平均时间复杂度:O(n^2)
  • 最好情况:O(n)
  • 最坏情况:O(n^2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

算法思想

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置。
  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤 2~5。

实例分析

现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

[5]   6   3   1   8   7   2   4
  ↑   │
  └───┘

[5, 6]   3   1   8   7   2   4
↑        │
└────────┘

[3, 5, 6]  1   8   7   2   4
↑          │
└──────────┘

[1, 3, 5, 6]  8   7   2   4
           ↑  │
           └──┘

[1, 3, 5, 6, 8]  7   2   4
            ↑    │
            └────┘

[1, 3, 5, 6, 7, 8]  2   4
   ↑                │
   └────────────────┘

[1, 2, 3, 5, 6, 7, 8]  4
         ↑             │
         └─────────────┘

[1, 2, 3, 4, 5, 6, 7, 8]

其中有一点比较有意思的是,在每次比较操作发现新元素小于等于已排序的元素时,可以将已排序的元素移到下一位置,然后再将新元素插入该位置,接着再与前面的已排序的元素进行比较,这样做交换操作代价比较大。还有一个做法是,将新元素取出,从左到右依次与已排序的元素比较,如果已排序的元素大于新元素,那么将该元素移动到下一个位置,接着再与前面的已排序的元素比较,直到找到已排序的元素小于等于新元素的位置,这时再将新元素插入进去,就像下面这样:

Insertion-sort-example-300px.gif

Javascript 代码示例

直接插入:

function insertionSort(array) {

    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    var length = array.length,
        i,
        j;
    for (i = 1; i < length; i++) {
        for (j = i; j > 0; j--) {
            if (array[j - 1] > array[j]) {
                swap(array, j - 1, j);
            } else {
                break;
            }
        }
    }
    return array;
}

减少交换次数:

function insertionSort(array) {

    var length = array.length,
        i,
        j,
        temp;
    for (i = 1; i < length; i++) {
        temp = array[i];
        for (j = i; j >= 0; j--) {
            if (array[j - 1] > temp) {
                array[j] = array[j - 1];
            } else {
                array[j] = temp;
                break;
            }
        }
    }
    return array;
}

利用二分查找法实现的插入排序,二分查找排序:

function insertionSort2(array) {
    function binarySearch(array, start, end, temp) {
        var middle;
        while (start <= end) {
            middle = Math.floor((start + end) / 2);
            if (array[middle] < temp) {
                if (temp <= array[middle + 1]) {
                    return middle + 1;
                } else {
                    start = middle + 1;
                }
            } else {
                if (end === 0) {
                    return 0;
                } else {
                    end = middle;
                }
            }
        }
    }

    function binarySort(array) {
        var length = array.length,
            i,
            j,
            k,
            temp;
        for (i = 1; i < length; i++) {
            temp = array[i];
            if (array[i - 1] <= temp) {
                k = i;
            } else {
                k = binarySearch(array, 0, i - 1, temp);
                for (j = i; j > k; j--) {
                    array[j] = array[j - 1];
                }
            }
            array[k] = temp;
        }
        return array;
    }
    return binarySort(array);
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。