学习算法-插入排序

排序

排序是与搜索算法同等重要的基本算法的概念之一。有很多算法可以对项目进行排序。为什么我们需要对元素进行排序？因为一旦对元素进行排序，问题就会变得更加容易。例如，当对数组进行排序时，您可以在恒定时间内找到中值，这意味着您可以使用二进制搜索。

插入排序

如果您想到最容易在脑中进行排序的方式，则可能类似于插入排序。基本上，它的工作方式是从左到右交换成对的元素，直到它们被排序为止。我们将有一个称为key的指针，该指针从1开始。

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i

上面的代码看起来像这样。

键将一直从1遍历到结尾（n），并j指向0（索引）。键一次将移动到右侧左元素的排序。该规则可以表示如下。

def insertion_sort(arr):
    n = arr.length
    for i from 1 to n:
        key = arr[i]    # start from arr[1]
        j = i - 1       # j is left element of pair of i
        # as long as j is greater than or equals to 0 and left 
        # element(arr[j]) of key is bigger than key, 

        while j >= 0 and arr[j] > key:
           # swap: its left item will move to key
           arr[j + 1] = arr[j]
           # j moves down to the left
           j = j - 1
        # once all sorted, move elements 
        # where j stopped lastly
        arr[j + 1] = key

我们换了9，7因为他们没有排序。因为7和9被排序，所以将键移到那里的右边4。然后比较9和4。9大于，4但4在左侧，则应交换它们。

4向下 移动到左侧，直到将其排序。一对交换后，j向左移动。在这种情况下，直到放置4为止arr[0]（特别是在代码中，当j变为-1时）。然后将钥匙移到右边的位置5。

现在，key = 5我们需要进行排序，5直到下降到为止arr[1]，让我们开始。

因为键（4）已排序，所以继续移动到元素，键变成1（arr[4]）。继续交换直到排序为1。然后结果将如下所示。

现在key = 3，我们将交换9和3。

继续进行相同的过程，直到3进入arr[1]

最后，我们到了！数组中的所有元素均已排序。

插入排序的时间复杂度

现在，该讨论算法的时间复杂性了。您可能会想到，我们花了很长时间才到达这里。简而言之，算法为O（n²）。让我们分析一下原因。

如您所见，（2）* O（1）和（2）* O（N）和（2）* O（N）。我们实际上可以忽略该系数。因此，时间复杂度将为1 * N * N =N²

总之，插入的时间复杂度是二次时间，不是很有效。不过，有一种更快的方式对元素进行排序。稍后再介绍。谢谢阅读！