二次排序

排序 - 按给定顺序重新排列数组(列表)的元素。

冒泡法(bubble sort),或简单交换排序。
该类型的不朽经典。操作原理很简单:我们从头到尾遍历数组,同时交换未排序的相邻元素。由于第一个传到最后一个地方,“弹出”最大元素。现在我们再次绕过数组的未排序部分(从第一个元素到倒数第二个元素)并沿途更改未排序的邻居。第二大元素将在倒数第二个位置。继续本着同样的精神,我们将绕过数组中不断减少的未排序部分,将找到的最大值推到最后。
 
来源

该算法的算法实现
<前> 循环 J=1 到 N-1 第 1 步 F=0 循环 I=1 到 N-J-1 第 1 步 如果 A[I] > A[I+1] 然后 交换 A[I],A[I+1] F=1 下一个 IF F=0 THEN EXIT THE LOOP // 如果在传递过程中没有交换,   // 这意味着所有元素   // 排列顺序 下一个J 该算法的复杂度: \(\displaystyle O(n^{2})\)


其他有用信息: 维基百科文章

 

插入排序

插入排序 (插入排序) —  ;一次查找输入序列的元素的排序算法,每个新的传入元素被放置在先前排序的元素中的适当位置。


插入排序 –这是一种非常简单但效率低下的算法,但具有几个特定的​​优点,即使在开发了许多其他通常更有效的算法之后,它仍具有相关性。

使用插入排序,您不必在排序前就拥有整个数组。该算法可以在排序过程中一次接收一个元素。如果我们需要在排序期间添加更多元素,这非常方便算法会在正确的位置插入新元素而不用“重新执行”对整个数组进行排序

由于插入排序在小型(约 10 个元素)数据集上的效率,因此可以在实践中使用。

问题是这样的:数组中有一部分已经排好了序,你想把数组剩下的元素插入排好序的部分,同时保持顺序。为此,在算法的每个步骤中,我们选择一个输入数据元素并将其插入数组中已排序部分的所需位置,直到对整个输入数据集进行排序。从输入数组中选择下一个元素的方法是任意的,但通常(并且为了获得稳定的排序算法),元素是按照它们在输入数组中出现的顺序插入的。

该算法的算法实现
<前> // null 元素被认为是一个已经排序的序列。 // 因此,循环从1开始 循环 I=1 到 N-1 第 1 步 X=A[我] J=我 WHEN J>0 AND A[J-1]>X //寻找插入的地方 交换 A[J],A[J-1] J=J-1 结束再见 A[J]=X 下一个 计算复杂度: \(\displaystyle O(n^{2})\)