Clever Geek Handbook

按插入排序

你好。今天，我们继续我专为OTUS 开设“算法和数据结构”课程而撰写的系列文章。







介绍



排序数组是计算机科学专业经典课程“算法和数据结构”中研究的第一个严重问题。在这方面，作为实习生或初级开发人员，在面试中经常会遇到写作任务和相应的问题。



问题的提法



传统上，值得用其陈述开始介绍问题的解决方案。通常，排序任务涉及按升序对一些整数数组进行排序。但是实际上，这有点过分简单了。本节中描述的算法可用于对在其之间建立排序关系的任何对象的数组进行排序（即对于任何两个元素，我们可以说：第一个大于第二个，第二个大于第一个，或者它们相等）。您可以按升序和降序排序。我们将使用标准简化。



按插入排序



上次我们讨论了最简单的排序之一- 选择排序。今天，我们将重点介绍稍微复杂一些的算法-插入排序。



算法说明



通过插入对数组进行排序的方式如下：与选择排序一样，将数组分为两部分。一部分称为已排序，另一部分称为未排序。该算法假定遍历整个数组，以使排序部分的长度等于整个数组的长度。在每次迭代中，我们采用数组未排序部分的第一个元素，并对其执行以下操作：尽管我们的元素严格小于前一个元素，但我们交换了它们。然后，我们将数组排序部分的长度加一。因此，通过依次移动所研究的元素，我们实现了它落入适当位置。下面给出了一个迭代的示例：

1 3 5 | 2 9 6-> 1 3 2 5 9 6-> 1 2 3 5 9 6-> 1 2 3 5 | 9 6



实作



我建议在C中查看此算法的实现： 



void insertionSortFunction(double array[], int size) {
    int i, j, temp;
    // i     ,   1,         
    for (i = 1; i < size; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < temp) {
                break;
            }
  
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}




分析



我建议分析此算法。



开始分析的最简单方法是获得记忆的渐近性。无论提议用于排序的数组的长度和结构如何，内存仅分配给两个循环计数器和一个用于交换两个变量值的辅助变量。因此，总是如此：

M(n)=O(1)

...



随着时间的流逝，一切都会变得更加有趣。内部循环的主体本身为O（1），即它不依赖于要排序的数组的大小。这意味着要了解算法的渐近性，有必要计算该主体的执行次数。但是内部循环的迭代次数取决于要排序的数组元素的有序（无序）程度。需要分析几种情况进行分析。



如果要排序的数组已经排序，则达到最小迭代次数。实际上，对于外部for循环的每次迭代，都会发生内部循环的一次迭代。这就是所谓的最佳情况。

T(n)=(n−1)∗O(1)=O(n)

因此，排序是在线性时间内完成的。



在最坏的情况下，迭代次数被认为是最大的，也就是说，断绝不会触发。在外循环的第一次迭代中，执行内循环的一次迭代。在外循环的第二次迭代中，执行了内循环的2次迭代。继续进行进一步的推理，我们可以得出结论，将在外循环的最后（n-1）-th次迭代（n-1）执行内循环。我们得到：

T(n)=O(1)+2∗O(1)+3∗O(1)+...+(n−1)∗O(1)=O(1+2+3+...+(n−1))=O(n∗(n−1)/2)=O(n2)

为了进行计算，我们使用了O-表示法的属性和用于算术级数求和的公式。



在平均值的情况下，假定对于外循环的特定迭代，内循环的迭代次数等于其平均值，即数学期望。假设内循环触发的所有允许次数都相等。在这种情况下，内部循环的平均迭代次数为图片。假设我是外循环的迭代数。现在，要计算渐近线，您需要计算图片。也就是说，我们只计算内部循环的主体执行了多少次。因此，我们得到图片。



综上所述，该算法的记忆渐近性为

O(1)

最好及时

O(n)

平均和最坏的情况

O(n2)

因此，该排序属于二次排序的类。



同样重要的是要注意，选择排序在此实现中很可靠。让我提醒您，如果equals元素的顺序在执行期间不发生变化，则称为稳定排序。此属性对于诸如对数字数组进行排序这样的教育性任务不是很重要，但是如果我们要对一些具有确定的排序关系的更复杂的对象进行排序，则它可能很重要。下一次我们谈论基数排序时，我们可以考虑一个类似的示例。



结果



我们看了另一个二次排序：插入排序，看了它的健壮实现。排序主要是教育性的，尽管实际上最好是由于良好的渐近性而可以应用：如果您需要将新数据添加到足够大的有序数据量中，以便再次对所有数据进行排序，则内部for循环可以派上用场。因此可以支持

O(n)

数据量的有序性。





了解有关该课程的更多信息。





More articles:


All Articles